Name
Abstract | ||
|---|---|---|
We present a polynomial-time algorithm for finding one extensive form correlated equilibrium (EFCE) for multiplayer extensive games with perfect recall. This the first such algorithm for an equilibrium notion for games of this generality. The EFCE concept has been defined by von Stengel and Forges [1]. Our algorithm extends the constructive existence proof and polynomial-time algorithm for finding a correlated equilibrium in succinctly representable games by Papadimitriou and Roughgarden [2,3]. We describe the set of EFCE with a polynomial number of consistency and incentive constraints, and exponentially many variables. The algorithm employs linear programming duality, the ellipsoid algorithm, and Markov chain steady state computations. We also sketch a possible interpretation of the variables in the dual system. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-92185-1_56 | WINE |
Keywords | Field | DocType |
ellipsoid algorithm,dual system,extensive form,extensive-form correlated equilibrium,multiplayer extensive game,correlated equilibrium,polynomial time,markov chain,efce concept,polynomial-time algorithm,constructive existence proof,equilibrium notion,steady state,linear program | Correlated equilibrium,Polynomial,Duality (optimization),Linear programming,Time complexity,Extensive-form game,Discrete mathematics,Mathematical economics,Combinatorics,Mathematical optimization,Markov chain,Ellipsoid method,Mathematics | Conference |
Volume | ISSN | Citations |
5385 | 0302-9743 | 5 |
PageRank | References | Authors |
0.52 | 7 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wan Huang | 1 | 23 | 2.64 |
| Bernhard von Stengel | 2 | 275 | 38.51 |