【练习】Twenty Lectures on Algorithmic Game Theory

这里主要是一些习题的做。之前读TLAGT的时候没怎么做题，现在做一些巩固认识。也顺便写点有的没的。

Chapter 1

习题Jump，做了，不想写。

这章最好玩的是那个Braess’s paradox，在我脑海里牵出了“模拟计算”这个东西。这玩意现在因为AI挺火的，而且和物理学和信息论能建立起联系。

Chapter 2

2.1 比方说三个人的估价是50、60、70，那60的人可以谎报80，然后以50的价格拿下商品。

2.2 让中的最高报价者取即可。

2.3 给前个，以第名的价格。

2.4 二价拍卖，但支付金额至少要为。

2.5 最低的胜出，以第二低的报价支付。

2.6 ？（没去了解ebay）

2.7 不断跟拍，直到有报价超出你的估价。

2.8 若分配为，

则显然，

故还是大的和大的匹配，小的和小的匹配更好，

所以最大的一定要和最大的在一起，然后用归纳法归纳即可。

P 2.1

(a)本质就是扮演了二价的角色，就不用证了。

(b)只要证明总有一个敌对序列从头到尾卖不出去就行了，这样收益肯定是，也就不会有正常数了。假设存在一个敌对序列使得前的轮都没卖出去。因为算法的deterministic，所以是一定的某个数，那只要序列的下一个报价是某个即可。由归纳法可以构造出任意长的、针对任意确定性算法的敌对序列。这题大概就是这个意思。

(c)这道题有点意思，我想把我的完整思考过程写下来。

首先，肯定是要从前面的报价序列获取信息，但具体是前面几个呢？是什么信息呢？

一开始先试了下这个方案：。

随便想一个情形先，比如除了最高报价以外别的报价全是零。（这个应当就是这个方案下的最差情形）

可以计算得到此情形下的“实际福利/最高可能福利”比率为

不趋向正常数，失败。

那再试试用一半的序列来获取信息。

首先想到使用前面一半报价的平均数（当然，前面一半报价全部不接受），以该平均数作为的值。

很容易构造出敌对序列，一大堆接近0的报价和一个超级大的报价就会使得这个超级大的报价只有极小的概率被选到，数学期望的大部分都是0，比率就可以任意小。

这里可以看到，我们的目标应该是盯紧最高的报价，同时不应该考虑“平均数”这种数值关系，而应该考虑“序”关系，比如中位数。

这里直接引入一些概率论的直觉，不严格证明。

前面一半的中位数（记为）如果拿到后面一半去排序，大概率也是后面一半的中位数（或附近的数）。

最高报价有可能在前一半，那就砍掉。

最高报价在后一半时（概率为），它必须比所有介于它自己以及间的那些“较大的数”排在更前面，否则商品就来不及卖给它，而“较大的数”在时是超级多的，所以几乎不可能发生它们全排在最高报价后的情况。

因此，又变成0了。

但是我们此处已经可以看到答案在招手，那就是使用前面一半报价中的最高报价作为。

同样的，直觉上，左边一半的最大报价（记为）在右边大概率也是最高报价（或几乎最高报价）。

我们还是把全体的最高报价单拎出来，

最高报价有可能在前一半，无法贡献数学期望。

最高报价在后一半时（概率为），它必须比所有介于它自己以及之间的那些“超大的数”排在更前面，而这类“超大的数”平均来讲极少，有超过一半的概率（这个是严格的）这类数的数量为0，那么此时最高报价必然获得商品。

因此至少，。

有一个问题就是，是最优答案了吗？怎么证明？我暂时没找到参考文献。

另一个问题是，取不同大小的“信息段落”（即全都不接受、只用来获取信息的序列部分），以及取“信息段落”中的不同位置，分别会造成什么影响？（即使有大量策略会导致趋向于零，它们趋向于零的速度或者说具体函数有什么规律？）

P 2.2

一开始想的是：

设外的最高报价为，内的最高和次高报价分别为，则充要条件为：
.

然后发现不对，上面只是一个充分条件，应该是：

设全体报价中第二高的报价为，充要条件为：

.

然后把下调到跟第三高报价一样的价格，把中除外的某个报价上调到第一高（如果原本第一高就在里那就不用调），这样就能以比更低的价格买到商品，而这对于的报价者来说是正收益的，为，这也就是联盟增加的收益。

得次高者得天下（不是

（但这好像也意味着二价拍卖的结盟风险很大，或者说结盟很容易，那就是找出可能的二价者，与其结盟）

P 2.3

要保持说真话是主导策略，那就看看在推出说真话是主导策略时用到了哪些性质。

在他人固定的情况下，只有两类情形会导致收益改变

一是虚高报价，获得了商品；

二是虚低报价，失去了商品。

要想保证说真话，就要保证这两种改变都不会使得收益上升，也即：

其中相当于“无事发生”。