Network cost-sharing games: Equilibrium computation and applications to election modeling

Rahul Swamy, Timothy Murray, Jugal Garg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We introduce and study a variant of network cost-sharing games with additional non-shareable costs (NCSG+), which is shown to possess a pure Nash equilibrium (PNE). We extend polynomial-time PNE computation results to a class of graphs that generalizes series-parallel graphs when the non-shareable costs are player-independent. Further, an election game model is presented based on an NCSG+ when voter opinions form natural discrete clusters. This model captures several variants of the classic Hotelling-Downs election model, including ones with limited attraction, ability of candidates to enter, change stance positions and exit any time during the campaign or abstain from the race, the restriction on candidates to access certain stance positions, and the operational costs of running a campaign. Finally, we provide a polynomial-time PNE computation for an election game when stance changes are restricted.

Original languageEnglish (US)
Title of host publicationCombinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Proceedings
EditorsAlexander Zelikovsky, Donghyun Kim, R.N. Uma
PublisherSpringer
Pages722-738
Number of pages17
ISBN (Print)9783030046507
DOIs
StatePublished - 2018
Event12th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2018 - Atlanta , United States
Duration: Dec 15 2018Dec 17 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11346 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2018
Country/TerritoryUnited States
CityAtlanta
Period12/15/1812/17/18

Keywords

  • Hotelling-Downs
  • Nash equilibrium
  • Network cost-sharing game

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Network cost-sharing games: Equilibrium computation and applications to election modeling'. Together they form a unique fingerprint.

Cite this