| Name | Description |
|---|---|
| CSP Discretization for Graphical Games | Uses some sort of CSP formulation to find epsilon-nash |
| Inner Ray Approximation | For infinitely repeated games with perfect monitoring and public randomization. Computes Equilibrium actions and strategies. May not be useful to us at all. |
| Iterative Method for Solving Zero Sum Games | Iteratively finds a minimax solution. Algorithm is proved in this paper, but not explained.. Originally suggested in "Some Notes on Computation of Games Solutions" (Brown, 1949) |
| KLS Algorithm for Graphical Games | Solves tree-structure graphical games via message passing of some sort. |
| Lemke-Howson | |
| Littman-Stone Repeated NE | Polytime algorithm for finding NE in repeated bi-matrix games (Limit of the means payoff) Output is a FSA or a "counting node" representation (DFA with counting allowed?) Looks like a generalized tit-for-tat thing, with computation of "attack" and "defense" strategies. Computes tit-for-tat for prisonner's dilemma Equilibria computed are subgame perferct Mentions Unbalanced and Exponential games Cannot be generalized to finite-horizon or discounted payoffs, unless discount factor is set very close to 1 in a game-specific way |
| Local Search for epsilon Nash | Obvious from description. |
| LP For zero-sum Games | |
| Monotone Inner Hyperplane Approximation | For infinitely repeated games with perfect monitoring and public randomization. Produces inner and outer approximations of the equilibrium value set. May not be useful to us at all. |
| Myopic best response | Each player best-responds to the fixed strategies of other agents. Convergence occurs when no agent wants to update his strategy, which by definition is a PSNE. There is no guantee of convergence. |
| NashProp | Does loopy message passing on graphical games. Seems to find epsilon-equlibria. Doesn't always converge. |
| Regret Matching | Start with some strategy. Switch to another strategy with probability proportional to regret of not not playing it in the past. Converges to the set of epsilon-equilibria almost surely. No empirical results seem to be available, but should be very easy to implement. |
| Simulated Annealing | By Piero and Mark - do simulated annealing to find set of all NE's (in infitine time) of normal form games. Converges with probability 1, no timing guarantees, suggest that it's nice, because can be implemented as a decentralized adaptive procedure. Say not a bad heuristic. |
| Wilson-Govindan Continuation Method | A strict generalization of Lemke-Howson, follows path in Kohlberg-Mertens spaces to get to an equilibrium. Good experimental results. |