<< 返回本书主页
 << Back to the afterword page

4 博弈论基础概念

吕汶桧 Wenhui Lyu

Jan. 2022

4 博弈论基础概念4.1 背景问题博弈问题作为理论抽象博弈问题的求解4.2 计算实践：多人重复囚徒困境（IPD）博弈循环赛4.2.1 作业描述与算法思路4.2.2 编程实现与要点说明策略函数博弈循环赛4.2.3 结果与分析

codes

4.1 背景问题

博弈问题作为理论抽象

博弈论是社会科学经典理论，同图论一样，博弈论可以用于对现实世界的一类现象进行抽象。

李老师先从最经典的“囚徒困境”讲起。两疑犯被警察抓住，分开关押。警察怀疑他们和一抢劫案有关，但没充足的证据。然而，他们都拒捕的事实也是可判刑的。开始审问，两疑犯被分别告知以下后果：

如果你坦白，而他抵赖，则马上把你释放，他将承担全部罪行，将被判刑10年。
如果你们都坦白，你们的罪行也就证实了。但由于你们有认罪表现，将都判刑4年。
如果你们都不坦白，那么没有证据证明你们的抢劫罪，但我们也会以拒捕罪起诉你们，将被判刑1年。

同时也告知：另一方也正在被告知这样的后果及你也知道这些。

两个囚徒之间的博弈可以由以下的收益矩阵表示：

		囚徒1
		抵赖	坦白
囚徒2	抵赖	-1, -1	-10, 0
囚徒2	坦白	0, -10	-4, -4

这里的要点是，每个人的收益不仅受自己的选择影响，而且受对方的选择影响。收益矩阵的不同赋值（关键是不同选择的收益的序数），决定了博弈的结果。

除了囚徒困境以外，博弈有多种类型。按照收益矩阵的不同赋值，博弈还有协调博弈和零和博弈（定义在此处略过），等等。除了两个参与者之间的博弈，博弈还可能在多个人之间发生。例如，在拍卖活动中，我的收益也取决于别人的出价。

总而言之，博弈有以下三个要素：

参与人（玩家/局中人）：至少两个，独立
策略（战略，选项）：每人可能的选择
回报（收益）：不仅取决于自己，还取决于别人

对于任意一个博弈，我们关心：

作为参与人，我怎么能得到较大回报？
作为观察者（社会），总体来看，结果会如何？

博弈问题的求解

求解博弈问题有多种方法。一种普遍的关注是找出博弈的均衡：对每个参与人而言，单方面更换策略已不能更好。根据纳什的研究，任何有穷博弈都至少有一个均衡，它有可能是纯策略均衡，也有可能是混合策略均衡（以给定的概率分别采取多种策略）。

要进行简单博弈推理，我们首先有以下几个理论假设：

个人收益是参与人关注的唯一对象。
参与人都是利己理性的（rational）：追求自己的收益最大化（尽量大）——给定其他人的策略，若自己能通过改变当前策略获得更大收益，则不会采用当前策略。
每个参与人都对博弈结构（收益矩阵）有充分了解，即信息完整。
每个参与人都知道其他参与人也了解上述要点——共有知识（common knowledge）。

在前面囚徒困境的例子中，

		囚徒1
		抵赖	坦白
囚徒2	抵赖	-1, -1	-10, 0
囚徒2	坦白	0, -10	-4, -4

$-1,-1$ $0$ $-4,-4$ 达到均衡。

除了双方都有严格占优策略的情况之外，达成均衡有多种方式。李老师在课上给我们举了几个例子，我们还做了几个求解练习。由于这些内容与本节课的计算作业关系不大，故仅列举在此。

一方有严格占优策略，另一方能推测出对方的严格占优策略，从而采取“最佳应对策略”。
双方没有严格占优策略，但都有“占优策略”。可以通过排除“严格劣策略”来找出这种均衡。
双方都没有占优策略和严格劣策略，但“互为最佳应对策略”的情况仍然存在，如果某种外界因素促使这一情况实现，那么双方都没有动机改变自己的策略，达到稳定状况。

4.2 计算实践：多人重复囚徒困境（IPD）博弈循环赛

codes

4.2.1 作业描述与算法思路

$m$ $\dfrac{m(m-1)}{2}$ $n$ （无穷，很大，事先不确定）轮。

$n$ 轮做完，再换两人。

		玩家k
		合作C	背叛D
玩家j	合作C	3, 3	0, 5
玩家j	背叛D	5, 0	1, 1

$n(m-1)$ 次）的得分之和。

$n$ ，分别算出每个人的总分，并进行讨论。

为了设计出得分高的策略，我的函数要分析自己和对手到当前为止已给出的行为，预测对方的下一次行为。给出自己的反应时，我们还要考虑到，自己如此行动会成为此后博弈的已知信息，这会不会影响未来的合作？总之，我们需要预测对方的行动，做出最有利于多次博弈总收益的回应。最好是能猜出对方的策略函数。比如说，“一报还一报”策略可能被很多人采纳，那么我可以在我的策略函数中设置一些判断条件。如果对方真的采用“一报还一报”策略，最有利于我的策略就是永远选择合作。模拟循环赛的程序并不难，只有判断最佳应答策略时程序稍微有些复杂，具体的算法见后。

4.2.2 编程实现与要点说明

策略函数

每个人的策略函数，输入自己到当前为止已给出的行为me和对手到当前为止已给出的行为him，返回下一次的行为合作C或背叛D。

一个最典型的策略函数是“一报还一报”。如果对方上一次选择合作，亦即if him[i-1]=='C'，我这一次就选择合作'C'；否则就选择背叛。


xxxxxxxxxx
8
1
def p7(i,me,him):
2
    if i == 0:
3
        return 'C'
4
    else:
5
        if him[i-1]=='C':
6
            return 'C'
7
        else:
8
            return 'D'

老师提供了一个devil策略。如果对方上一次选择合作，devil就选择背叛；对方上一次背叛，devil就合作。


xxxxxxxxxx
8
1
def devil(i,me,him):
2
    if i==0:
3
        return 'D'
4
    else:
5
        if him[i-1]=='C':
6
            return 'D'
7
        else:
8
            return 'C'

我的策略函数则稍微复杂一些。我在函数里加入了一些判断条件，试图预测对方的策略，从而给出自己的反应。


xxxxxxxxxx
1
1
def p10(i, me, him):

前四次我都选择合作，从而获取对方的四次反应数据。


xxxxxxxxxx
2
1
    if i in [0,1,2,3]:
2
        return 'C'

接着，我开始预测对方的策略函数。

如果对方第三次以后总是选择合作，我就认为ta采取的是“天真策略”（'innocent'）。当然，我前四次都选择合作，对方也选择合作很正常，这个判断条件会让我第五次选择背叛。但这只会损害我在一轮里的收益，这是获取对方反应数据的必要成本。如果我第五次选择了背叛，对方仍然不选择背叛，认为对方采取的是“天真策略”（'innocent'）就比较合理了。


xxxxxxxxxx
5
1
    else:
2
        if 'D' not in him[2:]:
3
            flag = 'innocent'
4
        if flag == 'innocent':
5
            return 'D'

接着，我开始验证对方是否采取了“一报还一报”策略。关键在于分析对方采取合作时的情景：对方为什么愿意信任我，选择合作？

一个可能的原因是，我上一轮也选了合作。我选择合作的次数存储在cnt1_1，当我上一轮选择合作时对方下一轮选择合作的次数存储在cnt1_2，当cnt1_2 / (cnt1_1 - 1) > 0.9时，我认为我上一轮选择合作能够触发对方下一轮选择合作。这个策略被我称为's-retri'（短时报复策略）。
另一个原因是，我过去经常选择合作，对方就会选择合作。对方选择合作的次数存储在cnt2_1，ta选择合作时，有cnt2_2次，我过去行为的众数也是合作。当cnt2_2 / cnt2_1 > 0.9时，我认为，我过去经常选择合作能够触发对方下一轮选择合作。这个策略被我称为'l-retri'（长时报复策略）。


xxxxxxxxxx
20
1
        flag = None
2
        cnt1_1 = 0
3
        cnt1_2 = 0
4
        cnt2_1 = 0
5
        cnt2_2 = 0
6
        for j in range(i-1):
7
            if me[j-1] == 'C':
8
                cnt1_1 += 1
9
                if me[j-1] == him[j]:
10
                    cnt1_2 += 1
11
            elif him[j] == 'C':
12
                cnt2_1 += 1
13
                if j > 2 and max(set(me), key = me.count) == him[j]:
14
                    cnt2_2 += 1
15
    
16
        elif cnt1_2 / (cnt1_1 - 1) > 0.9 and cnt1_2 >= 2:
17
            flag = 's-retri'
18
        elif cnt2_1 > 0:
19
            if cnt2_2 / cnt2_1 > 0.9:
20
                flag = 'l-retri'

如果我无法判断对方的策略，保险起见，我选择背叛。


xxxxxxxxxx
2
1
        if flag == None:
2
            return 'D'

如果我判断对方的策略是报复策略（不论是长时还是短时），我都选择合作，以期ta下回也会和我合作。


xxxxxxxxxx
2
1
        elif flag in ['s-retri','l-retri']:
2
            return 'C'

博弈循环赛

11位同学和devil的策略函数集合在strategy.py里，先跨文件调用：


xxxxxxxxxx
2
1
import strategy
2
strategies = [strategy.p1, strategy.p2, strategy.p3, strategy.p4, strategy.p5, strategy.p6, strategy.p7, strategy.p8, strategy.p9, strategy.p10, strategy.p11, strategy.devil]

首先定义一个函数game_dual。给定两个玩家，模拟二者之间的多轮重复博弈，按照收益矩阵计算两个人各自的分数。


xxxxxxxxxx
27
1
def game_dual(n,i,j):
2
    me = []
3
    me_score = 0
4
    me_str = strategies[i-1]
5
    him = []
6
    him_score = 0
7
    him_str = strategies[j-1]
8
    for k in range(n):
9
        # actions
10
        me_react = me_str(k,me,him)
11
        him_react = him_str(k,him,me)
12
        me.append(me_react)
13
        him.append(him_react)
14
        # scores
15
        if me_react == 'D' and him_react == 'D':
16
            me_score += 1
17
            him_score += 1
18
        elif me_react == 'C' and him_react == 'D':
19
            me_score += 0
20
            him_score += 5
21
        elif him_react == 'C' and me_react == 'D':
22
            him_score += 0
23
            me_score += 5
24
        else:
25
            him_score += 3
26
            me_score += 3
27
    return me_score, him_score

game $n$ 和有无devil）时多次调用。让所有玩家两两进行博弈，把每一组的结果存储在score_dict里。例如，i和j博弈的结果就是score_dict[i][j]。

首先，统一计算所有玩家相互博弈后的总分数（存储在scores里），输出结果。


xxxxxxxxxx
24
1
def game(n, devil=False):
2

3
    score_dict = {}
4
    print('Game on... (%i rounds in all)' % n)
5
    if devil == False:
6
        end = 12
7
    else:
8
        end = 13
9

10
    scores = [0 for i in range(end)]
11

12
    for i in range(1, end):
13
        for j in range(i+1, end):
14
            me_score, him_score = game_dual(n,i,j)
15
            score_dict[i,j] = [me_score,him_score]
16
            print('%i v.s. %i: %i – %i' % (i,j,me_score,him_score))
17
            scores[i] += me_score
18
            scores[j] += him_score
19
    outputF.write('devil = %s and n = %i\n' % (str(devil), n))
20
    outputF2.write('*** devil = %s and n = %i ***\n' % (str(devil), n))
21

22
    for i in range(1,end): # total scores of each one
23
        outputF.write('%i,%i\n' % (i, scores[i]))
24
        print('%i: %i' % (i, scores[i]))

score_dict $i$ 处赚得的分数存储在score_individual[i]里。


xxxxxxxxxx
11
1
    scores_individuals = {} 
2
    for i in range(1,end):
3
        scores_individuals[i] = {} # store how many points each one get from i
4

5
    for key,value in score_dict.items():
6
        for i in range(1,end):
7
            if i in key:
8
                i_index = key.index(i)
9
                j = key[1 - i_index]
10
                j_score = value[1 - i_index]
11
                scores_individuals[i][j] = j_score

$i$ 处赚得最多分数的人，具有最佳应答策略。


xxxxxxxxxx
6
1
    best_reacted_dict = {} 
2
    for key, value in scores_individuals.items():
3
        best_reacted = [0,0] # [j, j_score] (j reacted best against key, with a score of j_score)
4
        for j, j_score in value:
5
            if j_score > best_reacted[1]:
6
                best_reacted = [j, j_score]

$i$ 赚得的分数一样。


xxxxxxxxxx
3
1
            elif j_score == best_reacted[1]:
2
                best_reacted.append(j)
3
                best_reacted.append(j_score)

考虑不存在最佳应答策略的情况，删除用来占空的[0,0]。


xxxxxxxxxx
2
1
        if best_reacted[0:2] == [0,0]:
2
            del best_reacted[0:2]

输出分析结果


xxxxxxxxxx
4
1
        best_reacted_dict[key] = best_reacted
2
        print('* 对%i，p%s是最佳应答策略。' % (key, best_reacted[0:-1:2]))
3
        outputF2.write('* 对%i，p%s是最佳应答策略。\n' % (key, best_reacted[0:-1:2]))
4
    print()

非严格占优策略dominant对于所有玩家都是最佳占优策略。


xxxxxxxxxx
4
1
    dominant = [1] + best_reacted_dict[1][0:-1:2]
2
    for i in range(2, end):
3
        next_range = best_reacted_dict[i][0:-1:2] + [i]
4
        dominant = [x for x in dominant if x in next_range]

两个人互相是对方的最佳占优策略，也值得分析。


xxxxxxxxxx
7
1
    reciprocal = []
2
    for key, value in best_reacted_dict.items():
3
        for j in range(0, len(value), 2):
4
            if value[j] > key:
5
                for k in range(0, len(best_reacted_dict[value[j]]), 2):
6
                    if key == best_reacted_dict[value[j]][k]:
7
                        reciprocal.append([key,value[j]])

为了方便重复调用，以上分析都被包含在game函数中。game函数最后返回score_dict。


xxxxxxxxxx
1
1
  return score_dict

以下是主程序。循环次数不同时、有无devil时，计算比赛的不同结果。


xxxxxxxxxx
7
1
score_dict_whole = {0:{}, 1:{}}
2

3
for n in [1,10,100,1000]:
4
    print('无devil, n = %i' % n)
5
    score_dict_whole[0][n] = game(n)
6
    print('有devil, n = %i' % n)
7
    score_dict_whole[1][n] = game(n, True)

4.2.3 结果与分析

n=1000, devil=True时，输出结果如下：


xxxxxxxxxx
15
1
>>> *** devil = True and n = 1000 ***
2
>>> * 对1，p[10]是最佳应答策略。
3
>>> * 对2，p[1, 3, 4, 5, 6, 7, 8, 9, 11]是最佳应答策略。
4
>>> * 对3，p[1, 2, 4, 5, 6, 7, 8, 9, 11]是最佳应答策略。
5
>>> * 对4，p[1, 2, 3, 5, 6, 7, 8, 9, 11]是最佳应答策略。
6
>>> * 对5，p[1, 2, 3, 4, 6, 7, 8, 9, 10, 11]是最佳应答策略。
7
>>> * 对6，p[1, 2, 3, 4, 5, 7, 8, 9, 11]是最佳应答策略。
8
>>> * 对7，p[1, 2, 3, 4, 5, 6, 8, 9, 11]是最佳应答策略。
9
>>> * 对8，p[1, 2, 3, 4, 5, 6, 7, 9, 11]是最佳应答策略。
10
>>> * 对9，p[1, 2, 3, 4, 5, 6, 7, 8, 11]是最佳应答策略。
11
>>> * 对10，p[12]是最佳应答策略。
12
>>> * 对11，p[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]是最佳应答策略。
13
>>> * 对12，p[5]是最佳应答策略。
14
>>> （非严格）占优策略：无。
15
>>> 互为最佳应答策略：2 – 3 | 2 – 4 | 2 – 5 | 2 – 6 | 2 – 7 | 2 – 8 | 2 – 9 | 2 – 11 | 3 – 4 | 3 – 5 | 3 – 6 | 3 – 7 | 3 – 8 | 3 – 9 | 3 – 11 | 4 – 5 | 4 – 6 | 4 – 7 | 4 – 8 | 4 – 9 | 4 – 11 | 5 – 6 | 5 – 7 | 5 – 8 | 5 – 9 | 5 – 11 | 6 – 7 | 6 – 8 | 6 – 9 | 6 – 11 | 7 – 8 | 7 – 9 | 7 – 11 | 8 – 9 | 8 – 11 | 9 – 11 |

1	2	3	4	5	6	7	8	9	10	11	devil
69100	68918	69136	75545	71928	68622	69136	69129	69136	61366	68695	27003

我的策略函数（编号10）的分数并不好，在p4与devil面前失分最多。

在p4面前失分是由于对方的严格设置，即每次都遵循“一报还一报”的策略，p4才会选择与我合作。我虽然倾向于与一报还一报者合作，却没有设置得那么严格，有的时候甚至会试探性地采取背叛，因此对方不愿意和我合作。
在devil面前失分，是由于devil策略被我判断成了“长时报复策略”。尽管恶魔选择与我合作仅仅是为了调戏我，但这被我判断成了，由于我过去多是合作，他才与我合作。我的判断的重点在于，合作的选择是难的，不像背叛那么安全，我要理解一个人为什么下定决心合作。但devil选择合作的理由恰恰相反——他不care丢分，只要能激怒对方就行。我的预测算法没有考虑到这种奇葩的存在。

对于p4和devil以外的策略，我丢分的原因在于，我设置的“一报还一报”的比例门槛是0.9，这就意味着，当别人并没有完全按照一报还一报的策略进行时，我仍然在选择合作，这损伤了我的分数。

<< 返回本书主页
 << Back to the afterword page