Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Enforcing Efficient Equilibria in Network Design Games via Subsidies
 
research article

Enforcing Efficient Equilibria in Network Design Games via Subsidies

Augustine, John
•
Caragiannis, Ioannis
•
Fanelli, Angelo
Show more
2015
Algorithmica

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.

  • Details
  • Metrics
Type
research article
DOI
10.1007/s00453-013-9845-5
Web of Science ID

WOS:000352434300002

Author(s)
Augustine, John
Caragiannis, Ioannis
Fanelli, Angelo
Kalaitzis, Christos  
Date Issued

2015

Publisher

Springer Verlag

Published in
Algorithmica
Volume

72

Issue

1

Start page

44

End page

82

Subjects

Network design

•

Algorithmic game theory

•

Equilibria

•

Price of stability

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL2  
Available on Infoscience
May 29, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/114223
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés