## 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 language | English |
---|---|

Article number | 5985 |

Pages (from-to) | 564-566 |

Number of pages | 3 |

Journal | Operations Research Letters |

Volume | 43 |

Issue number | 6 |

DOIs | |

State | Published - 1 Nov 2015 |

## Keywords

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