View Item 
      •   Home
      • 1. Schools
      • College of Science
      • School of Physical and Mathematical Sciences (SPMS)
      • SPMS Conference Papers
      • View Item
      •   Home
      • 1. Schools
      • College of Science
      • School of Physical and Mathematical Sciences (SPMS)
      • SPMS Conference Papers
      • View Item
      JavaScript is disabled for your browser. Some features of this site may not work without it.
      Subject Lookup

      Browse

      All of DR-NTUCommunities & CollectionsTitlesAuthorsBy DateSubjectsThis CollectionTitlesAuthorsBy DateSubjects

      My Account

      Login

      Statistics

      Most Popular ItemsStatistics by CountryMost Popular Authors

      About DR-NTU

      Enforcing efficient equilibria in network design games via subsidies

      Thumbnail
      Author
      Augustine, John
      Caragiannis, Ioannis
      Fanelli, Angelo
      Kalaitzis, Christos
      Date of Issue
      2012
      Conference Name
      Symposium on Parallelism in algorithms and architectures (24th : 2012)
      School
      School of Physical and Mathematical Sciences
      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.
      Subject
      DRNTU::Science::Mathematics::Discrete mathematics::Algorithms
      Type
      Conference Paper
      Collections
      • SPMS Conference Papers
      http://dx.doi.org/10.1145/2312005.2312054
      Get published version (via Digital Object Identifier)

      Show full item record


      NTU Library, Nanyang Avenue, Singapore 639798 © 2011 Nanyang Technological University. All rights reserved.
      DSpace software copyright © 2002-2015  DuraSpace
      Contact Us | Send Feedback
      Share |    
      Theme by 
      Atmire NV
       

       


      NTU Library, Nanyang Avenue, Singapore 639798 © 2011 Nanyang Technological University. All rights reserved.
      DSpace software copyright © 2002-2015  DuraSpace
      Contact Us | Send Feedback
      Share |    
      Theme by 
      Atmire NV
       

       

      DCSIMG