Computation and efficiency of potential function minimizers of combinatorial congestion games

Pieter Kleer*, Guido Schäfer

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We study the computation and efficiency of pure Nash equilibria in combinatorial congestion games, where the strategies of each player i are given by the binary vectors of a polytope Pi. Our main goal is to understand which structural properties of such polytopal congestion games enable us to derive an efficient equilibrium selection procedure to compute pure Nash equilibria with attractive social cost approximation guarantees. To this aim, we identify two general properties of the underlying aggregation polytopePN= ∑ iPi which are sufficient for our results to go through, namely the integer decomposition property (IDP) and the box-totally dual integrality property (box-TDI). Our main results for polytopal congestion games satisfying IDP and box-TDI are as follows: (i) we show that pure Nash equilibria can be computed in polynomial time. In fact, we obtain this result through a general framework for separable convex function minimization, which might be of independent interest. (ii) We bound the inefficiency of these equilibria and show that this provides a tight bound on the price of stability. (iii) We also prove that these results extend to strong equilibria for the “bottleneck variant” of polytopal congestion games. Examples of polytopal congestion games satisfying IDP and box-TDI include common source network congestion games, symmetric totally unimodular congestion games, non-symmetric matroid congestion games and symmetric matroid intersection congestion games (in particular, r-arborescences and strongly base-orderable matroids).

Original languageEnglish
Pages (from-to)523-560
Number of pages38
JournalMathematical Programming
Volume190
Issue number1-2
Early online date11 Aug 2021
DOIs
Publication statusPublished - Nov 2021

Bibliographical note

Funding Information:
Pieter Kleer was supported by NWO Gravitation Project NETWORKS, Grant Number 024.002.003.

Publisher Copyright:
© 2020, The Author(s).

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

Fingerprint

Dive into the research topics of 'Computation and efficiency of potential function minimizers of combinatorial congestion games'. Together they form a unique fingerprint.

Cite this