Question

1) Discuss the complexity of building efficient algorithms in Game Theory (+150 words)

Answer 1

The existence of an equilibrium in a game is typically established using non-constructive fixed point theorems. There are no efficient algorithms known for computing Nash equilibria. The problem is complete for the complexity class PPAD even in 2- player games. In contrast, correlated equilibria can be computed efficiently using linear programming, as well as learned via no-regret strategies.

strategy profile is a Nash equilibrium if no player can do better by unilaterally changing her/his strategy. To see what this means, imagine that each player is told the strategies of the others. Suppose then that each player asks themselves: "Knowing the strategies of the other players, and treating the strategies of the other players as set in stone, can I benefit by changing my strategy?"

If any player could answer "Yes", then that set of strategies is not a Nash equilibrium. But if every player prefers not to switch (or is indifferent between switching and not) then the strategy profile is a Nash equilibrium.

PPAD ("Polynomial Parity Arguments on Directed graphs") is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument. The class attracted significant attention in the field of algorithm game theory because it contains the problem of computing a Nash equilibrium.

Welfare Maximization: Lower bound for general valuations- We begin with a result of Nisan showingthat, alas, computing even a very weak approximation of the welfare-maximizing allocation requires exponential communication. To make this precise, it is convenient to turn the optimization problem of welfare maximization into a decision problem. In the Welfare-Maximization (k) problem, the goal is to correctly identify inputs that fall into one of the following two cases:
(1) Every partition (T1, . . . , Tk) of the items has welfare at most 1
(0) There exists a partition (T1, . . . , Tk) of the items with welfare at least k.
Arbitrary behavior is permitted on inputs that fail to satisfy either (1) or (0). Clearly, communication lower bounds for Welfare-Maximization(k) apply to the more general problem of obtaining a better-than-k- approximation of the maximum welfare.