Enforcing efficient equilibria in network design games via subsidies

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 r...

Full description

Saved in:
Bibliographic Details
Main Authors: Augustine, John, Caragiannis, Ioannis, Fanelli, Angelo, Kalaitzis, Christos
Other Authors: School of Physical and Mathematical Sciences
Format: Conference or Workshop Item
Language:English
Published: 2013
Subjects:
Online Access:https://hdl.handle.net/10356/98956
http://hdl.handle.net/10220/12510
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-98956
record_format dspace
spelling sg-ntu-dr.10356-989562020-03-07T12:31:20Z Enforcing efficient equilibria in network design games via subsidies Augustine, John Caragiannis, Ioannis Fanelli, Angelo Kalaitzis, Christos School of Physical and Mathematical Sciences Symposium on Parallelism in algorithms and architectures (24th : 2012) DRNTU::Science::Mathematics::Discrete mathematics::Algorithms 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. 2013-07-30T04:30:27Z 2019-12-06T20:01:28Z 2013-07-30T04:30:27Z 2019-12-06T20:01:28Z 2012 2012 Conference Paper Augustine, J., Caragiannis, I., Fanelli, A.,& Kalaitzis, C. (2012). Enforcing efficient equilibria in network design games via subsidies. Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and architectures - SPAA '12. https://hdl.handle.net/10356/98956 http://hdl.handle.net/10220/12510 10.1145/2312005.2312054 en
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic DRNTU::Science::Mathematics::Discrete mathematics::Algorithms
spellingShingle DRNTU::Science::Mathematics::Discrete mathematics::Algorithms
Augustine, John
Caragiannis, Ioannis
Fanelli, Angelo
Kalaitzis, Christos
Enforcing efficient equilibria in network design games via subsidies
description 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.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Augustine, John
Caragiannis, Ioannis
Fanelli, Angelo
Kalaitzis, Christos
format Conference or Workshop Item
author Augustine, John
Caragiannis, Ioannis
Fanelli, Angelo
Kalaitzis, Christos
author_sort Augustine, John
title Enforcing efficient equilibria in network design games via subsidies
title_short Enforcing efficient equilibria in network design games via subsidies
title_full Enforcing efficient equilibria in network design games via subsidies
title_fullStr Enforcing efficient equilibria in network design games via subsidies
title_full_unstemmed Enforcing efficient equilibria in network design games via subsidies
title_sort enforcing efficient equilibria in network design games via subsidies
publishDate 2013
url https://hdl.handle.net/10356/98956
http://hdl.handle.net/10220/12510
_version_ 1681045734554599424