Enforcing Efficient Equilibria in Network Design Games via Subsidies

John Augustine, Ioannis Caragiannis, Angelo Fanelli () and Christos Kalaitzis
Additional contact information
John Augustine: IIT Madras - Indian Institute of Technology Madras
Ioannis Caragiannis: CTI - Computer Technology Institute - Computer Technology Institute
Angelo Fanelli: CREM - Centre de recherche en économie et management - UNICAEN - Université de Caen Normandie - NU - Normandie Université - UR - Université de Rennes - CNRS - Centre National de la Recherche Scientifique
Christos Kalaitzis: School of Computer and Communication Sciences - EPFL - Ecole Polytechnique Fédérale de Lausanne

Post-Print from HAL

Abstract: The efficient design of networks has been an important engineering task that involves challenging combinatorial optimization problems. Typically, a network designer has to select among several alternatives which links to establish so that the resulting network satisfies a given set of connectivity requirements and the cost of establishing the network links is as low as possible. The Minimum Spanning Tree problem, which is well-understood, is a nice example. In this paper, we consider the natural scenario in which the connectivity requirements are posed by selfish users who have agreed to share the cost of the network to be established according to a well-defined rule. The design proposed by the network designer should now be consistent not only with the connectivity requirements but also with the selfishness of the users. Essentially, the users are players in a so-called network design game and the network designer has to propose a design that is an equilibrium for this game. As it is usually the case when selfishness comes into play, such equilibria may be suboptimal. In this paper, we consider the following question: can the network designer enforce particular designs as equilibria or guarantee that efficient designs are consistent with users' selfishness by appropriately subsidizing some of the network links? In an attempt to understand this question, we formulate corresponding optimization problems and present positive and negative results.

Keywords: price of stability; equilibria; algorithmic game theory; Network design (search for similar items in EconPapers)
Date: 2015-05
References: Add references at CitEc
Citations:

Published in Algorithmica, 2015, 72 (1), pp.44-82. ⟨10.1007/s00453-013-9845-5⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-01103888

DOI: 10.1007/s00453-013-9845-5

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().