Equilibrium Computation in Atomic Splittable Singleton Congestion Games

Veerle Timmermans*, Tobias Harks

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Abstract

We devise the first polynomial time algorithm computing a pure nash equilibrium for atomic splittable congestion games with singleton strategies and player-specific affine cost functions. Our algorithm is purely combinatorial and computes the exact equilibrium assuming rational input. The idea is to compute a pure nash equilibrium for an associated integrally-splittable singleton congestion game in which the players can only split their demands in integral multiples of a common packet size. While integral games have been considered in the literature before, no polynomial time algorithm computing an equilibrium was known. Also for this class, we devise the first polynomial time algorithm and use it as a building block for our main algorithm.
Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization. IPCO 2017.
Subtitle of host publication19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings
PublisherSpringer
Pages442-454
Volume10328
ISBN (Electronic)978-3-319-59250-3
ISBN (Print)978-3-319-59249-7
DOIs
Publication statusPublished - 2017
EventIPCO 2017: Integer Programming and Combinatorial Optimization: 19th International Conference - Waterloo, ON, Waterloo, Canada
Duration: 26 Jun 201728 Jun 2017

Publication series

SeriesLecture Notes in Computer Science
Number10328

Conference

ConferenceIPCO 2017
Country/TerritoryCanada
CityWaterloo
Period26/06/1728/06/17

Cite this