Equilibrium: Difference between revisions
It seems that a cabal equilibrium is the same thing as a strong Nash equilibrium; make a change to this effect.
imported>R.H. (Nash + cabal equilibrium definitions) |
(It seems that a cabal equilibrium is the same thing as a strong Nash equilibrium; make a change to this effect.) |
||
| (10 intermediate revisions by 4 users not shown) | |||
Line 1:
The word "'''equilibrium'''" refers, among other things, to concepts of game theory. The most well-known equilibrium in game theory is the [[Nash equilibrium]].
== Types of equilibria ==
{{wikipedia|List of types of equilibrium#Game theory}}
According to https://en.wikipedia.org/w/index.php?title=List_of_types_of_equilibrium&oldid=1076576484#Game_theory
<blockquote>
* [[Correlated equilibrium]], a solution concept in game theory that is more general than Nash equilibrium
* [[Nash equilibrium]], the basic solution concept in game theory
** [[Quasi-perfect equilibrium]], a refinement of Nash Equilibrium for extensive form games due to Eric van Damme
** [[Sequential equilibrium]], a refinement of Nash Equilibrium for games of incomplete information due to David M. Kreps and Robert Wilson
** [[Perfect Bayesian equilibrium]], a refinement of Nash equilibrium for games of incomplete information that is simpler to use than sequential equilibrium
* [[Symmetric equilibrium]], an equilibrium where all players use the same strategy
* [[Trembling hand perfect equilibrium]] assumes that the players, through a "slip of the hand" or tremble, may choose unintended strategies
** [[Proper equilibrium]] due to Roger B. Myerson, where costly trembles are made with smaller probabilities
</blockquote>
According to some editors on [[electowiki]]:<ref>https://electowiki.org/w/index.php?title=Equilibrium&oldid=11149</ref>:
<blockquote>
'''Nash equilibria''' are situations where each player has chosen a strategy and no single player could improve their situation by unilaterally changing strategy while all the other players keep their strategies.
'''Cabal equilibria''' or [[w:Strong Nash equilibrium|strong Nash equilibria]] are situations where each player has chosen a strategy and no ''subset of players'' could simultaneously change behaviour (while those outside that subset keep their strategies) in a way that no player in that subset is worse off and at least one in the subset is better off.
All cabal equilibria are Nash equilibria but not vice versa.
</blockquote>
The term "cabal equilibrium" was devised by Peter de Blanc. It is difficult to find online by that name elsewhere.
== Strong equilibrium ==
A strong Nash equilibrium is a set of ballots such that candidate X wins, and no set of voters can change their ballots such that a candidate Y whom all of them strictly prefer to X will win.
A slightly stronger and more restrictive concept is that of a strictly semi-honest strong Nash equilibrium; that is, one in which no voter puts any A above some B despite actually preferring B over A or being indifferent between the two.
If there is a [[majority Condorcet winner]], there is almost certain to be a strong Nash equilibrium that favors that winner, in almost any reasonable deterministic voting system; but in some voting systems, that equilibrium may not be strictly semi-honest.
If there is a Condorcet winner but not a majority Condorcet winner (in other words, if enough voters are indifferent between the CW X and some other candidate Y, so that the social preference for X over Y is not a majority), it may not be possible to have a strictly semi-honest strong Nash equilibrium in a candidate-blind, non-dictatorial voting system.
===Smith set equilibrium ===
Many voting methods that have an equilibrium around the Condorcet winner likely more generally have an equilibrium around any candidate in the [[Smith set]], particularly if every candidate in the Smith set majority-beats all candidates not in the Smith set. For example, with [[Approval voting]]:<blockquote>2: A>B>C
2: B>C>A
2: C>A>B
5: D</blockquote>A, B, and C are in the "majority Smith set" (every candidate in the Smith set [[majority-beat]]<nowiki/>s every candidate not in the set). Every voter in the (A, B, C) [[solid coalition]] has an incentive to approve all of (A, B, C) to ensure that one of them wins, rather than D; if any of them approve fewer candidates, then D wins or at least ties, which is strictly worse from the solid coalition voters' perspectives.
Another example:
<br />
{| class="wikitable"
|+Losses and ties are bolded, with every win being a majority-win
!
!A
!B
!C
!D
!E
!F
!G
|-
|A
| ---
|Win
|'''Lose'''
|Win
|Win
|Win
|Win
|-
|B
|'''Lose'''
| ---
|Win
|Win
|Win
|Win
|Win
|-
|C
|Win
|'''Lose'''
| ---
|'''Lose'''
|Win
| Win
|Win
|-
|D
|'''Lose'''
|'''Lose'''
|Win
| ---
|'''Tie'''
|Win
|Win
|-
| E
|'''Lose'''
|'''Lose'''
|'''Lose'''
|'''Tie'''
| ---
| Win
|Win
|-
|F
|'''Lose'''
|'''Lose'''
|'''Lose'''
|'''Lose'''
|'''Lose'''
| ---
|Win
|-
|G
|'''Lose'''
|'''Lose'''
|'''Lose'''
|'''Lose'''
|'''Lose'''
|'''Lose'''
| ---
|}
A through E are in the Smith set (there are [[beat-or-tie path]]<nowiki/>s of A<C<B and C<D=E). Suppose F wins in [[Score voting]]; then the majority that prefers any of the Smith set members can set their [[approval threshold]] between the Smith set member and F, giving the Smith set member a majority of points and F a minority of points.
==Strong Nash equilibrium==
Applied to voting theory, a '''strong Nash equilibrium''' means a set of votes, where no coalition of voters can change their votes to get a result they all prefer.
This is one of the strongest, most elusive kinds of equilibria in voting theory. The only ways to make it stronger are if it is known (through some reliable aspect of the system, not just through polling) and/or unique. It has also been called a '''coalition-proof social equilibrium''' or '''CPSE'''.
== Notes ==
Although a particular type of candidate may be elected in equilibrium for a particular election method and election, that does not necessarily imply that this candidate type is in equilibrium for every election for that method. For example, [[Approval voting]] may elect the [[Condorcet winner]] in equilibrium in some elections, but not all: <blockquote>Here's my reasoning: consider a standard chicken dilemma:
{| class="wikitable"
!Number
! Ballots
|-
|1
| A
|-
|34
|A>B>C
|-
|25
|B>A>C
|-
|40
|C
|}
where, under honesty, the 59 voters ranking both A and B over C would approve of both A and B.
If B-top voters strategically bury/don't approve A, and A-top voters vote honestly, B of course wins; and B is clearly not the honest CW, nor the honest Approval winner (A is both). If B voters do this ''first'', the strategic equilibrium for A voters (supposing here that C is indeed honestly unacceptable to A-top voters) is to simply continue to vote honestly, and thus B wins. So it seems incorrect to generally claim that strategic voting under Approval has an equilibrium where the CW wins all the time.
Furthermore, there seems to be (in my view) considerable similarity between representing this election as a game under Approval voting and as a game under, say, Ranked Pairs. What I mean is that each of the A-B player factions has two moves really available (honesty and disapproval/burial respectively in each game). So then, the result for Approval voting is:
{| class="wikitable"
!-
!Honesty (A)
!Disapprove (A)
|-
|'''Honesty (B)'''
|A wins, minor B utility loss
|A wins, minor B utility loss
|-
|'''Disapprove (B)'''
|B wins, minor A utility loss
|C wins, major A,B utility loss
|}
For Ranked Pairs, the game matrix is exactly the same:
{| class="wikitable"
!-
!Honesty (A)
!Burial (A)
|-
|'''Honesty (B)'''
|A wins, minor B utility loss
| A wins, minor B utility loss
|-
|'''Burial (B)'''
|B wins, minor A utility loss
|C wins, major A,B utility loss
|}
So, to suggest that Approval voting selects a CW under strategic equilibrium seems equivalent to saying that in such scenarios, Ranked Pairs and similar Condorcet methods also must do so in such scenarios; which is clearly incorrect.
(A brief comment: note that despite these scenarios being ''called'' "chicken dilemmas", they do not in fact share the same payoff matrices with the actual game of chicken. The RP/Approval payoff matrix is something like
{| class="wikitable"
!-
!Honesty (A)
!Burial (A)
|-
|'''Honesty (B)'''
| -1, 0
| -1, 0
|-
|'''Burial (B)'''
|1, -1
| -10, -10
|}
whereas in the actual standard game of chicken, the matrix is more like
{| class="wikitable"
!-
!Swerve(A)
!Straight (A)
|-
|'''Swerve (B)'''
|0, 0
| -1, 1
|-
|'''Straight (B)'''
|1, -1
| -10, -10
|}
this is an important difference; namely, we see from the RP and Approval payoff matrix that regardless of which choice B makes, A is better off or at least not worse off for having chosen Honesty, whereas in standard chicken this is not true (what's best for A depends heavily on what B does).)<ref>https://www.reddit.com/r/EndFPTP/comments/ewgjss/shouldnt_the_nash_equilibriums_of_approval_voting/fg2fd63/</ref></blockquote>
==External links==
*[[w:Nash equilibrium|Wikipedia: Nash equilibrium]]
*[https://web.archive.org/web/20160401013731/http://www.spaceandgames.com/?p=46 Peter de Blanc: A Stronger Type of Equilibrium]
*[https://web.archive.org/web/20160507114642/http://www.spaceandgames.com/?p=134 Peter de Blanc: When is an honest vote a cabal equilibrium?]
==References==
<references />
[[Category:Voting theory]]
[[Category:Game theory]]
[[Category:Game theory equilibrium concepts|*]]
| |||