|
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.
An 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 egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2012}, |
| NUMBER | = | {TR-2012-18} |