## Abstract

We consider the atomic version of congestion games with affine cost functions, and analyze the quality of worst case Nash equilibria when the strategy spaces of the players are the set of bases of a k-uniform matroid. In this setting, for some parameter k, each player is to choose k out of a finite set of resources, and the cost of a player for choosing a resource depends affine linearly on the number of players choosing the same resource. Earlier work shows that the price of anarchy for this class of games is larger than 1.34 but at most 2.15. We determine a tight bound on the asymptotic price of anarchy equal to ≈1.35188. Here, asymptotic refers to the fact that the bound holds for all instances with sufficiently many players. In particular, the asymptotic price of anarchy is bounded away from 4/3. Our analysis also yields an upper bound on the price of anarchy <1.4131, for all instances.

Original language | English |
---|---|

Title of host publication | Approximation and Online Algorithms |

Subtitle of host publication | 15th International Workshop, WAOA 2017, Revised Selected Papers |

Editors | Roberto Solis-Oba |

Publisher | Springer |

Pages | 317-328 |

Number of pages | 12 |

Volume | 10787 LNCS |

ISBN (Electronic) | 978-3-319-89441-6 |

ISBN (Print) | 9783319894409 |

DOIs | |

Publication status | Published - 2018 |

Event | 15th Workshop on Approximation and Online Algorithms, WAOA 2017 - Vienna, Austria Duration: 7 Sept 2017 → 8 Sept 2017 Conference number: 15 |

### Publication series

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

Volume | 10787 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Conference

Conference | 15th Workshop on Approximation and Online Algorithms, WAOA 2017 |
---|---|

Abbreviated title | WAOA 2017 |

Country/Territory | Austria |

City | Vienna |

Period | 7/09/17 → 8/09/17 |

## Keywords

- Asymptotic price of anarchy
- Congestion games
- Uniform matroid