论文标题
顺序调度游戏中理性的诅咒
The curse of rationality in sequential scheduling games
论文作者
论文摘要
尽管对算法游戏理论研究中的可计算性问题有重视，但玩家的计算能力有限，但注意力的关注程度要少得多。这项工作研究了不同级别的玩家的计算能力（或“理性”）如何影响顺序调度游戏的结果。令人惊讶的是，我们的结果表明，较低的参与者的理性水平可能会提高平衡。更具体地说，我们在两种不同的有限合理性模型下，即具有$ k $ lookahead and Simple Imbince的玩家的玩家，我们表征了无政府状态（SPOA）的顺序价格（SPOA）。玩家在“完美理性”（$ k = n-1 $）和“在线贪婪”（$ k = 0 $）之间具有$ k $ - lookahead interpolate的模型。我们的结果表明，平衡（SPOA）的效率低下$ k $增加了lookahead的程度：两台机器的$ \ mathrm {spoa} = o（k^2）$ for两台机器和$ \ mathrm {spoa} = o \ left（2^k \ min \ min \ \ \ \ \ \ {mk {mk {mk {mk，n \ right）$ $ $ s $ mach $ mach此外，当玩家头脑简单时，SPOA正是$ M $，这与“在线贪婪”的表现相吻合。
Despite the emphases on computability issues in research of algorithmic game theory, the limited computational capacity of players have received far less attention. This work examines how different levels of players' computational ability (or "rationality") impact the outcomes of sequential scheduling games. Surprisingly, our results show that a lower level of rationality of players may lead to better equilibria. More specifically, we characterize the sequential price of anarchy (SPoA) under two different models of bounded rationality, namely, players with $k$-lookahead and simple-minded players. The model in which players have $k$-lookahead interpolates between the "perfect rationality" ($k=n-1$) and "online greedy" ($k=0$). Our results show that the inefficiency of equilibria (SPoA) increases in $k$ the degree of lookahead: $\mathrm{SPoA} = O (k^2)$ for two machines and $\mathrm{SPoA} = O\left(2^k \min \{mk,n\}\right)$ for $m$ machines, where $n$ is the number of players. Moreover, when players are simple-minded, the SPoA is exactly $m$, which coincides with the performance of "online greedy".
