|
A fundamental problem of algorithmic game theory is to determine the hardness of computing equilibria in various classes of games.
In this paper, we examine a class of LP-based generalized Nash equilibrium problems where the interaction of players is
limited to providing services to each other at fixed prices. This limited interaction between players enables the study of computational
complexity as a function of the structure of provider-customer relationships.
We show that the problem of computing an equilibrium is PPAD-complete in general, but
it is in P if every strong component of the digraph describing the provider-customer relationships is a simple directed cycle.
The proof is based on a new result on approximating fixed points in a special case of Kakutani's fixed point theorem.
We also give sufficient conditions for the existence of service prices under which any socially optimal solution is in equilibrium. If
such prices exist, then an equilibrium can be computed in polynomial time. This generalizes an earlier result of Agarwal and Ergun
on service networks [Agarwal, Ergun, Mechanism design for a multicommodity flow game
in service network alliances, 2008].
An earlier version (under the title "Complexity of equilibria in linear service-providing games") is available as TR-2012-18.
Bibtex entry:
| AUTHOR | = | {Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia}, |
| TITLE | = | {Finding equilibria in linear service-providing games}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2016}, |
| NUMBER | = | {TR-2016-15} |