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

Abstract

我們考慮一以正整數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.