算法的なゲーム理論

今回は二つの課題について書きます。一つはComputational complexity of computing Nash equilibriaです。もう一つは「将来の研究」です。
Traditional complexity theory studies tend to involve the notions of P and NP. P refers to a problem which can be solved in polynomial time by a deterministic Turing machine, while NP refers to that which can be solved in polynomial time by a non-deterministic Turing machine. Algorithmic game theory makes use of two new complexity classes: PLS (polynomial local search) and PPAD (polynomial parity argument, directed). Just as traditional computer science theory states that a problem is NP complete if there exists a polynomial time reduction to any NP problem (i.e. solving that problem allows us to solve any problem in NP), algorithmic game theory uses the descriptors "PLS complete" and "PPAD complete".
PLS problems involve finding a pure Nash equilibrium (PNE)(single strategy) using a search mechanism which attempts to find a local minimum/maximum. An example of a problem in this space is the search for a PNE in an atomic selfish network routing game. Polynomial Local Search consists of three separate algorithms, each of which runs in polynomial time.
1. generate a candidate solution (equilibrium)
2. evaluate its potential (objective)
3. either verify that the candidate is the optimal solution or return a neighbor that provides a better potential value. A neighbor is a set of users and paths such that all but one player in this set chooses the same path as the corresponding player in the candidate solution. The algorithm for finding and verifying the candidate solution in an atomic selfish network routing game is known as Best Response Dynamics (BRD). In this algorithm, a player who is not using a minimum cost path updates his path to be the one with minimal cost. Another player using a sub-optimal path (previous update may have changed optimal paths for some players)is then chosen, and the process continues until all players are using a min-cost path (i.e. PNE reached).
PPAD is the complexity class which applies to problems of finding an MNE (Mixed-strategy Nash Equilibrium). A mixed-strategy Nash equilibrium arises when each player selects a mixed strategy, which is a probability distribution over the pure strategies of each player. I am not sure whether the distribution for player X's mixed strategy refers to the probability of all other players' strategies or of X's strategies. Actually, each player's mixed strategy input is an m by n matrix of payoff values. Given player one opts for strategy A, he knows player two selects strategy A (resulting in payoff p1 for him) with probability prob1 and strategy B (resulting in payoff p2) with prob2. Then he can compute his expected payoff for strategy A. However, how can player one know which distribution player two selected? In fact, he does not, knowing only the payoff resulting from the combination of his strategy and his opponent's. Once player one selects a distribution, for himself, though, player two can select a distribution using expectations computed from player one's. Mixed-strategy Nash equilibriums can be found by three polynomial-time algorithms in a manner analogous to that used to find the PNE for PLS problems. The guided search algorithm which is analogous to Best Response Dynamics in this case is called the Lemke-Howson (LH) algorithm. The difference between these two types of problems is that the LH algorithm does not use an objective or potential function to measure the solution. Thus, the problems of finding MNE are said to be in PPAD, not in Polynomial Local Search.
Future directions in mechanism design include:
1. bounds of approximation for combinatorial auctions via polynomial time algorithms.
2. multi-parameter domains admitting only affine maximizers
3. how randomization affects polynomial implementability. Does this refer to randomization of bidding?
Future directions of equilibrium efficiency analysis:
1. price of anarchy in atomic selfish routing networks with fractional routing (fraction of user's payload sent on one path)
2. price of stability in Shapley cost allocation games
3. technique to extract efficiency loss bounds form potential functions
4. how to distribute delays to minimize worst-case POA in selfish routing networks.
Future directions of equilibrium computation are:
1. complexity of approximate MNE computation
2. complexity of computing market equilibria (price where market clears for a good) with concave utility function.
3. complexity (expression for the time/memory cost in terms of the problem size) of computing equilibrium in stochastic games in NP intersect coNP.
Unit-recall games are mentioned as a case of algorithmic game theory where novel behavioral models are examined. I am not sure what these are.