How Bad Can An Election Game of Two or More Parties Be?

淡江大學機構典藏 > 工學院 > 資訊工程學系暨研究所 > 會議論文 > Item 987654321/125479

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/125479

题名:	How Bad Can An Election Game of Two or More Parties Be?
作者:	Lin, Chuang-chieh;Lu, Chi-jen;Chen, Po-an
关键词:	Election game;Nash equilibrium;Price of anarchy;Egoism;Monotonicity
日期:	2024-05-06
上传时间:	2024-06-07 12:05:22 (UTC+8)
摘要:	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.
显示于类别:	[資訊工程學系暨研究所] 會議論文

文件中的档案:

没有与此文件相关的档案.

在機構典藏中所有的数据项都受到原著作权保护.

TAIR相关文章

数据加载中.....