On the Computational Power of Players in Two-Person Strategic Games
Date Issued
2006
Date
2006
Author(s)
Chang, Ching-Lueh
DOI
en-US
Abstract
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.
Subjects
賽局
計算複雜度
game theory
circuit
computational complexity
Type
thesis