Computing equilibrium in network utility-sharing and discrete election games

Rahul Swamy () and Timothy Murray ()
Additional contact information
Rahul Swamy: University of Illinois at Urbana-Champaign
Timothy Murray: University of Illinois at Urbana-Champaign

Journal of Combinatorial Optimization, No 0, 29 pages

Abstract: Abstract This paper studies the computation of pure Nash equilibrium (PNE) in network utility-sharing and discretized Hotelling–Downs games, and the interplay between these classes of games. First, we introduce and study a variant of network utility-sharing games with additional player-specific non-shareable costs (NUSG+), which is shown to possess a 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. Second, a spatial election game is introduced with a discretized utility function. The complexity of this game is shown to be in Polynomial Local Search, and a polynomial-time PNE computation is derived for certain settings. Third, a spatio-temporal election game model is presented based on an NUSG+ 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.

Keywords: Nash equilibrium; Hotelling–Downs; Network utility-sharing game (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00554-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00554-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00554-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().