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

機構典藏 > College of Engineering > Graduate Institute & Department of Computer Science and Information Engineering > Proceeding > Item 987654321/125479

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/125479

Title:	How Bad Can An Election Game of Two or More Parties Be?
Authors:	Lin, Chuang-chieh;Lu, Chi-jen;Chen, Po-an
Keywords:	Election game;Nash equilibrium;Price of anarchy;Egoism;Monotonicity
Date:	2024-05-06
Issue Date:	2024-06-07 12:05:22 (UTC+8)
Abstract:	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.
Appears in Collections:	[Graduate Institute & Department of Computer Science and Information Engineering] Proceeding

Files in This Item:

There are no files associated with this item.

Loading...