How egalitarian are Nash equilibria in network cost-sharing games?

Po-An Chen*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the egalitarian social cost, which is the maximum individual cost (instead of the sum), when analyzing Nash equilibria in fair network cost-sharing games. Intuitively, the egalitarian price of anarchy reflects how uneven cost is distributed among players at equilibrium. We first show a tight upper bound of k in general fair network cost-sharing games, where k is the total number of players. For fair network cost-sharing games with a single source-sink pair and a relaxed benchmark, we then show an upper bound of n-1 on the egalitarian price of anarchy defined using such benchmark, where n is the network size. This gives a possibly better bound that does not depend on the number of players nor the costs.

Original languageEnglish
Article number5985
Pages (from-to)564-566
Number of pages3
JournalOperations Research Letters
Volume43
Issue number6
DOIs
StatePublished - 1 Nov 2015

Keywords

  • Egalitarian
  • Network cost-sharing game
  • Network design game
  • Network formation game
  • Price of anarchy

Fingerprint Dive into the research topics of 'How egalitarian are Nash equilibria in network cost-sharing games?'. Together they form a unique fingerprint.

Cite this