Complexity of equilibria in linear service-providing games

Tamás Király, Júlia Pap


A fundamental problem in algorithmic game theory is to determine the hardness of computing equilibria in various classes of games. It is difficult to pinpoint the properties that affect hardness, since computing an equilibrium seems to be hard even for 2-player games with very special payoff matrices. To address this problem, we introduce an LP-based model (a special case of the Generalized Nash Equilibrium Problem) where the interaction of players is limited to providing services to each other at fixed prices. This enables us to investigate computational complexity as a function of the structure of provider-customer relationships.
Our model guarantees the existence of equilibria with polynomial bit-size. If the service prices are optimal in some sense, then socially optimal solutions are in equilibrium and can be computed in polynomial time. However, for arbitrary service prices, the computation of an equilibrium is PPAD-complete. To study the complexity in terms of the structure of interactions between players, we introduce a digraph describing the provider-customer relatioships, and give a polynomial-time algorithm if every strong component of the digraph is a simple directed cycle. The proof is based on a new algorithmic result on approximating a fixed point of a multidimensional function having a cyclic structure.

Previous version can be found here.

An even earlier version of this report is available as report no. 2012-12.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia},
TITLE = {Complexity of equilibria in linear service-providing games},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-18}

Last modification: 13.3.2018. Please email your comments to Tamás Király!