## Abstract

In many games, players’ decisions consist of multiple subdecisions, and hence can give rise to an exponential number of pure strategies. However, this set of pure strategies is often structured, allowing it to be represented compactly, as in network congestion games, security games, and extensive form games. Reduction to the standard normal form generally introduces exponential blow-up in the strategy space and therefore are inefficient for computation purposes. Although individual classes of such games have been studied, there currently exists no general purpose algorithms for computing solutions. equilibrium. To address this, we define multilinear games generalizing all. Informally, a game is multilinear if its utility functions are linear in each player’s strategy, while fixing other players’ strategies. Thus, if pure strategies, even if they are exponentially many, are vectors in polynomial dimension, then we show that mixed-strategies have an equivalent representation in terms of marginals forming a polytope in polynomial dimension. The canonical representation for multilinear games can still be exponential in the number of players, a typical obstacle in multi-player games. Therefore, it is necessary to assume additional structure that allows computation of certain sub-problems in polynomial time. Towards this, we identify two key subproblems: computation of utility gradients, and optimizing linear functions over strategy polytope. Given a multilinear game, with polynomial time subroutines for these two tasks, we show the following: (a) We can construct a polynomially computable and continuous fixed-point formulation, and show that its approximate fixed-points are approximate NE. This gives containment of approximate NE computation in PPAD, and settles its complexity to PPAD-complete. (b) Even though a coarse correlated equilibrium can potentially have exponential representation , through LP duality and a carefully designed separation oracle, we provide a polynomial-time algorithm to compute one with polynomial representation. (c) We show existence of an approximate NE with support-size logarithmic in the strategy polytope dimensions.

Original language | English (US) |
---|---|

Title of host publication | Web and Internet Economics - 12th International Conference, WINE 2016, Proceedings |

Editors | Adrian Vetta, Yang Cai |

Publisher | Springer |

Pages | 44-58 |

Number of pages | 15 |

ISBN (Print) | 9783662541098 |

DOIs | |

State | Published - 2016 |

Event | 12th International Conference on Web and Internet Economics, WINE 2016 - Montreal, Canada Duration: Jun 11 2016 → Jul 14 2016 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10123 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 12th International Conference on Web and Internet Economics, WINE 2016 |
---|---|

Country/Territory | Canada |

City | Montreal |

Period | 6/11/16 → 7/14/16 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science