How Bad Can An Election Game of Two or More Parties Be?
學年 112
學期 2
發表日期 2024-05-06
作品名稱 How Bad Can An Election Game of Two or More Parties Be?
作品名稱（其他語言）
著者 Lin, Chuang-chieh; Lu, Chi-jen; Chen, Po-an
作品所屬單位
出版者
會議名稱 6th Games, Agents, and Incentives Workshop (GAIW 2024)
會議地點 Auckland, New Zealand
摘要 An election campaign among two or more parties can be viewed as a game of two or more players, each of which has its own candidates as the pure strategies. People, as voters, comprise supporters for each party, and a candidate brings utility for the supporters of each party. Each party nominates exactly one of its candidates to compete against the other party’s. A candidate is assumed to win the election with greater or equal odds if it brings more utility for all the people. The payoff of each player is the expected utility that its supporters get. The game is egoistic if every candidate benefits its party’s supporters more than any candidate from a competing party does. In this paper, we first prove that it is NP-complete to determine whether an election game in a succinct representation, which is called the general form, has a pure-strategy Nash equilibrium even if it is egoistic. Next, we propose two sufficient conditions for an egoistic election game to have a pure-strategy Nash equilibrium.Based on these conditions, we propose a fixed-parameter tractable algorithm to compute a pure-strategy Nash equilibrium of an ego-istic election game. Finally, perhaps surprisingly, we show that the price of anarchy for egoistic election games is upper bounded by the number of parties. Our results suggest that an election becomes unpredictable in terms of stability and efficiency when more than two parties are involved and, moreover, the price-of-anarchy bound deteriorates with an increasing number of participating parties.This provides one of supporting arguments why the two-party system is prevalent in democratic countries.
關鍵字 Election game;Nash equilibrium;Price of anarchy;Egoism;Monotonicity
語言 en_US
收錄於
會議性質 國際
校內研討會地點 無
研討會時間 20240506~20240507
通訊作者
國別 NZL
公開徵稿
出版型式
出處
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/125479 )

SDGS 優質教育,夥伴關係