组合优化答案2023

第四章测试

1.若博弈的某个策略组合不是Nash均衡，则每位参与者均可通过单方面改变自身的策略使其费用减少。（ ）
A:对 B:错
答案:B
2.考虑背包问题的在线形式。背包容量事先已知，物品一个个相继出现，物品出现后方知其价值和大小。具体地，第个物品在第个物品是否放入背包已被确定后才出现，且此前已作出的前个物品是否被放入背包的决定不可更改。该在线问题的下界为（ ）。
A:3
B:
C:2
D:4

答案:B
3.设一博弈的社会费用为极小化目标，记分别为实例的社会费用最大的Nash均衡的社会费用，社会费用最小的Nash均衡的社会费用和最优社会费用。以下说法准确的有（ ）。
A:。
B:
C:。
D:。

答案:ABC
4.设是一个在线问题，以下说法准确的有（ ）。
A:若是的一个下界，则可能存在竞争比大于的在线算法。
B:若存在的竞争比为的在线算法，则问题的下界至少为。
C:若是的一个下界，则可能存在竞争比小于的在线算法。
D:若存在的竞争比为的在线算法，则问题的下界至多为。

答案:AD
5.一寝室住有四名同学。一日学园举行某项活动，有至少两名同学参与该项活动的寝室将获得奖励。每位同学有参加或不参加两种选择。他们都希望寝室能获得奖励，同时倾向于自己不参加活动。当然在自己参加活动而寝室获得奖励与自己不参加活动而寝室未获奖励之间更偏好前种情况。该博弈的Nash均衡有（ ）。
A:任一名同学参加活动或任一名同学不参加活动。
B:四名同学均不参加活动。
C:两名同学参加活动。
D:四名同学参加活动。

答案:BC