玩家在雙人賽局中所需計算能力之研究

On the Computational Power of Players in Two-Person Strategic Games

張經略(Ching-Lueh Chang)

指導教授 ： 呂育道

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2006年)

https://doi.org/10.6342/NTU.2006.01704

摘要

我們考慮一以正整數n為索引的雙人策略性賽局序列，其中兩玩家都有2^n種純粹策略，並且被允許使用混合策略。我們也假設賽局中的獲利函數以一個n的多項式為上界，這表示賽局的輸贏並不大。我們定義一個玩家在對付一類玩家時所能保證的期望獲利值，為他對付該類中每個玩家時，所得期望獲利值的最大下界。在我們的主要結果中，我們假設第一個玩家可以知道第二個玩家的混合策略，但卻無法得知其隨機投擲的銅板結果。大致上來說，在此情況下只要第二個玩家的計算能力稍微降低，第一個玩家便可以大幅減少其所需要使用的純粹策略，而幾乎不降低其能保證的期望獲利。不論假設第一個玩家可以知道第二個玩家的混合策略，或者假設第一個玩家只能夠得知O(log n)位元關於第二個玩家的資訊，我們都得到一些關於第一個玩家欲保證一個夠好的期望獲利值所需要的計算能力。

關鍵字

賽局 ； 計算複雜度

並列摘要

We consider families of two-person strategic games parameterized by a positive integer n. We assume that each of the players, the row player and the column player, has 2n strategies to choose from and can take mixed strategies.
We also assume that the games are not too “risky” in that the payoffs are at most polynomial in n in absolute value. The row player is said to guarantee an expected payoff of t 2 R against all column players of a certain class when his expected payoff is at least t against all column players of that class. This thesis studies the expected payoff the row player could guarantee against all column players of a certain computational power. In our main result we consider the case where the row player is informed of how the column player chooses his action but is not allowed to see the internal coin tosses of the column player. Roughly speaking, we show that when the computational power of the column player shrinks polynomially, the row player can have his number of pure strategies shrunk exponentially without harming his guaranteed expected payoff too much. We obtain several corollaries regarding the computational power needed by the row player to guarantee a good expected
payoff against computationally bounded column players in situations where the row player is aware of the output strategy of the column player, the mixed strategy of the column player, or only O(log n) bits of information about the column player.

並列關鍵字

game theory ； circuit ； computational complexity

參考文獻

Statistics 23 (1952), 493–507.

complexity of computing a nash equilibrium, Tech. Report TR05-

115, Electronic Colloquium on Computational Complexity, 2005.

complexity of succinct zero-sum games, Proceedings of the 20th

IEEE Conference on Computational Complexity, 2005, pp. 323–