## Abstract

We investigate the problem of equilibrium computation for “large” n-player games where each player has two pure strategies. Large games have a Lipschitz-type property that no single player’s utility is greatly affected by any other individual player’s actions. In this paper, we assume that a player can change another player’s payoff by at most 1/n by changing her strategy. We study algorithms having query access to the game’s payoff function, aiming to find ε-Nash equilibria. We seek algorithms that obtain ε as small as possible, in time polynomial in n. Our main result is a randomised algorithm that achieves ε approaching 1/8 in a completely uncoupled setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players’ payoffs/actions. O(log n) rounds/queries are required. We also show how to obtain a slight improvement over 1/8, by introducing a small amount of communication between the players.

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

Title of host publication | Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings |

Editors | Martin Gairing, Rahul Savani |

Publisher | Springer Verlag |

Pages | 3-14 |

Number of pages | 12 |

ISBN (Print) | 9783662533536 |

DOIs | |

State | Published - 2016 |

Externally published | Yes |

Event | 9th International Symposium on Algorithmic Game Theory, SAGT 2016 - Liverpool, United Kingdom Duration: Sep 19 2016 → Sep 21 2016 |

### Publication series

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

Volume | 9928 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 9th International Symposium on Algorithmic Game Theory, SAGT 2016 |
---|---|

Country/Territory | United Kingdom |

City | Liverpool |

Period | 9/19/16 → 9/21/16 |

### Bibliographical note

Publisher Copyright:© Springer-Verlag Berlin Heidelberg 2016.