课程简介

算法、激励和数据 aka Algorithms, Incentives, and Data

Prof. Ioannis Caragiannis (Ιωάννης Καραγιάννης)

课程内容实际上就是算法博弈论（algorithmic game theory）

Week 35 - Week 49，共 14 周（除去秋假一周）

第一周（Week 35）内容：Introduction and examples

A example: badminton scandal in London 2012 Olympic Games

女子双打，16 强进 8 强时

8 强的分组是 16 强的某两个小组 A 和 B

A 组胜者和 B 组负者比赛，A 组负者和 B 组胜者比赛

头号种子田&赵意外爆冷成为 A 组负者

此时 B 组是由王&于对阵 Jung&Kim

Incentives?

for teams: to get as prestigious a medal as possible
for Olympic Committee: to have all teams do their best to win

但是由于田&赵太强了，如何遇到了极有可能被淘汰。因此王&于、Jung&Kim 两个小组都不想赢，故意消极比赛。两组最终被处罚，disqualified。

问题出在哪？

不是不道德、违反体育精神的行为
而是糟糕的比赛机制

如何解决糟糕的比赛机制？（课后讨论题）

首先尝试保留循环赛和锦标赛阶段，但更改锦标赛树叶子上的团队交叉点
每一组的不管是胜者和负者匹配随机化

An ML-ish example

deciding the room temperature

有一个空调，可以设置 16 到 30 度。

有一群学生和老师 Ιωάννη，每个人都有一个最舒服的温度。当温度越接近某人的温度，某人就会越舒服。

问题是，如何决定这个房间的温度？

问所有人的最舒服温度，然和计算平均值。空调温度设定为平均值。（看起来最公平）
Ιωάννης 想设多少，就设多少（独裁哈哈哈）
平均值的变体：中位数

思考：

**平均值是会被操纵的。**对某人来说，如果平均值比他最舒服的温度最高，那么下次他就会倾向于把自己“最舒适温度值”往小了报，因为这样可以整体将温度平均值拉低。而多次演化博弈的均衡结果，则是所有一开始最适宜温度就比平均值高的人，通通报 30 度，而一开始适宜温度比平均值低的人，通通报 16 度。
**独裁不会被其他人操纵。**因为 Ιωάννης 谎报自己“最适宜温度”不会使自己的收益增加。
**中位数也不会被其他人操纵。**因为比中位数低的人随便怎么报，都不会影响中位数的大小。比中位数高的人同理。而比中位数低的人不可能报比中位数高的值，因为这样反而使得自己的收益减小。

Inefficiency of equilibrium

The Braess Paradox

布雷斯悖论

从 S 地到 T 地有两条路（上路 SAT 和下路 SBT）

SA 是窄短路（耗时 x），AT 是宽长路（耗时 1）

SB 是宽长路（耗时 1），BT 是窄短路（耗时 y）

x 是走上路的流量， $x\in[0,1]$

y 是走下路的流量， $y\in[0,1]$

所有人的激励：从 A 到 B 耗时越短越好

此时，均衡值对应 SAT 和 SBT 分配相等（x = y = 0.5）的流量，用时 1.5

但是，如果从 A 到 B 建立一个传送点，耗时 0 的话……

原本走 SAT 的人，会走 SABT。因为 BT 耗时 ≤ AT 耗时
原本走 SBT 的人，也会走 SABT。因为 SA 耗时 ≤ SB 耗时

这样，最终均衡的结果是：所有人都走 SABT。此时 x = 1，y = 1，因此所有人的耗时为 2

Price of anarchy (PoA):

刻画个体追求最佳利益时引发的系统性效率的损失
= 个体都最优时，系统的成本÷集中协调规划，整体系统达到最优状态的成本
= $\frac{2}{1.5}$

A view of algorithm design

已知输入 x，得到输出 y=f(x)

f(x) 未知

通常 f 非常难以计算得到

因此将问题转化为：设计一个算法来近似 f

有限若干个 x 和对应的函数输出

解决办法通常有：分布式、并行多核、流式算法……

博弈的视角

在一个博弈环境下，input is provided by different parties that have their own interests in the outcome of the algorithm

比如：投票、拍卖、网络路由问题……

当一个输入 input 的实体发现，改变 input 会使得函数的 output 有利于自己的时候，incentive 就会激励该实体改变输入。然后该实体就改变 input， deviate 了。

因此问题继续转化：设计一个算法，考虑到所有输入的 agent 都会采取某种有利于自己的策略，输出就是 game solution

Course Overview

决策中的战略方面（算法）
通过理论分析我们可以保证什么样的性能？
数据有何帮助？

算法博弈论的两个部分

机制设计 algorithms that incentivize truthful behavior 设计鼓励诚实行为的算法
非诚实行为激励算法导致的均衡 equilibrium of games induced by non-truthful algorithms (PoA, dynamics, learning)