space and games

March 4, 2009

A Stronger Type of Equilibrium

Filed under: Decision Theory, Voting — Peter de Blanc @ 5:57 pm

In game theory, a Nash equilibrium is an assignment of strategies to players, such that no player can benefit from changing vis own strategy (assuming the other players’ strategies remain the same). For example, in the one-shot Prisoner’s Dilemma, mutual defection is the only Nash equilibrium. There are several other ideas for how to define an “equilibrium” of a game, many of which are “refinements” of Nash Equilibrium, in the sense that the set of equilibria is smaller.

Here’s another one: a “cabal equilibrium” is an assignment of strategies to players, such that no subset (or “cabal”) K of players can simultaneously change strategies in such a way that some players in K benefit and no players in K are worse off. In other words, each cabal of players is playing a strategy which is Pareto optimal for the players within that cabal. Note that any subset of players is considered a cabal, so if there are N players, then there are 2N cabals.

Any cabal equilibrium is also a Nash equilibrium. A single player is just a cabal of size one, so if no cabal of players wishes to change strategies, then single no player wishes to change strategy. So this definition of equilibrium is “stronger” than the Nash equilibrium, in the sense that it is a more stringent test.

For example, the Prisoner’s Dilemma has no cabal equilibrium. First observe that mutual defection is the only Nash equilibrium, so there is at most one cabal equilibrium. But mutual defection is not an cabal equilibrium, because both players would prefer to simultaneously switch their strategy to cooperation.

Stag hunt has two Nash equilibria but only one cabal equilibrium. Battle of the Sexes has two Nash equilibria, both of which are cabal equilibria.

Mike Dobbins and I talked about cabal equilibria in voting. Because the outcome of an election depends on the voters in such a coarse way, the Nash equilibrium does not seem like a strong enough definition to apply to voting situations. For example, any election in which the winner beats the first loser by more than one vote is a Nash equilibrium, because no single voter can change the outcome by changing vis strategy. So not only are there multiple Nash equilibria, but in fact almost any election is a Nash equilibrium.

So let’s consider cabal equilibria in a plurality or approval vote. Suppose there is an equilibrium, and this equilibrium elects candidate A.

Suppose that more than half of the voters preferred B over A. Then they could all vote for B (and disapprove of A in an approval vote), resulting in a better outcome from their point of view. Then the original election was not a cabal equilibrium: contradiction! So there is no candidate that is preferred over A by a majority.

So if we ignore the possibility that exactly half the voters prefer some other candidate over A, this would mean that A is a Condorcet winner!

Now let’s consider the converse. Suppose that there is no cabal equilibrium. Then, in particular, it is not a cabal equilibrium for everyone to vote for the same candidate A. Then there exists some cabal K of voters which could make a Pareto improvement by changing votes. In order for the new strategy to be a Pareto improvement, it must affect the outcome of the election somehow; thus it must cause some other candidate B to be elected instead of A. In order to change the outcome of the election, we must have changed at least half of the votes (since originally everyone was voting for A), so K must contain at least half of the voters. Since no member of K prefers B over A, we know A is not preferred over B by a majority, and thus is not a Condorcet winner.

So if there is no cabal equilibrium, then A is not a Condorcet winner. Since the same argument works for any other candidate (not just candidate A), this means that no cabal equilibrium implies no Condorcet winner. Taking the contrapositive, this means that in an election with a Condorcet winner, there is a cabal equilibrium!

So we’ve just proven a theorem: A plurality or approval vote with an odd number of voters has a cabal equilibrium iff there is a Condorcet winner, and a cabal equilibrium always elects the Condorcet winner.

16 Comments »

  1. [...] change strategies to benefit group members, the global situation will start to look like a cabal equilibrium, and cabal equilibria in plurality or approval votes always elect a Condorcet winner. Of course, [...]

    Pingback by space and games » Will conditional commitments change politics? — September 21, 2009 @ 12:45 pm

  2. [...] year I introduced cabal equilibria. This post is a summary of my research on cabal equilibria and election methods. Since this is just [...]

    Pingback by space and games » Summary on Cabal Equilibria and Voting — January 26, 2010 @ 11:29 pm

  3. Good stuff, thanks for sharing.

    Comment by Zella Vanni — January 6, 2011 @ 10:22 pm

  4. You should look up the core and coalition-proof Nash equilibrium. Also, read an elementary game theory text book sometime.

    Comment by asdf — June 1, 2011 @ 4:23 pm

  5. エルメス エルメス バーキン エルメス バッグ エルメス 財布 hermes
    品物スタートを切った現在個人オーバーバッグ
    hermes バッグ エルメス 財布 hermes バッグ エルメス 財布 エルメス バッグ
    http://www.hermes777jp.info/
    は何理想 1用バッグブーツ初心者のための 05 あなたのためにフィットそれにもかかわらず、技術的に自分 全く同じ。
    エルメス 長財布 エルメス 財布 メンズ エルメス 財布 新作 エルメス 財布 メンズ エルメス 財布 メンズ
    エルメス 財布 メンズ エルメス バック エルメス トート エルメス 店舗 エルメス 財布 メンズ
    これは、最新の状態に 上に置かドン 戻る
    サッチェル
    bag
    サッチェル
    .co.jp
    ホームページ

    <a href=”http://www.hermes777jp.info/”>エルメス バッグ</a> <a href=”http://www.saifujp777.info/”>hermes 財布</a> <a href=”http://www.saifuonline.info/”>エルメス バーキン</a> <a href=”http://www.hermessaifumise777.info/”>エルメス バッグ</a> <a href=”http://www.hermessaifumise.info/”>エルメス バッグ</a>
    そこに多くの店ともっぱら袋を販売靴。
    <a href=”http://www.hermes777jp.info/”>エルメス 財布</a> <a href=”http://www.saifujp777.info/”>エルメス バーキン</a> <a href=”http://www.saifuonline.info/”>エルメス</a> <a href=”http://www.hermessaifumise777.info/”>エルメス</a> <a href=”http://www.hermessaifumise.info/”>エルメス バーキン</a>
    <a href=”http://www.hermes777jp.info/”>エルメス トート</a> <a href=”http://www.saifujp777.info/”>エルメス トート</a> <a href=”http://www.saifuonline.info/”>エルメス 長財布</a> <a href=”http://www.hermessaifumise777.info/#4173″>エルメス 長財布</a> <a href=”http://www.hermessaifumise.info/”>エルメス 財布 メンズ</a>
    あなたが探している特定の着色 |あなたが見つけること|あなたを、チャンスはあなたバッグ部は、でそれを見つけることができる。
    <a href=”http://www.hermes777jp.info/#3147″>エルメス トート</a> <a href=”http://www.saifujp777.info/#1226″>エルメス 長財布</a> <a href=”http://www.saifuonline.info/#2679″>エルメス 財布 新作</a> <a href=”http://www.hermessaifumise777.info/#9834″>エルメス バック</a> <a href=”http://www.hermessaifumise.info/#7848″>エルメス 店舗</a>
    <a href=”http://www.hermes777jp.info/”>マザーズバッグ
    </a> <a href=”http://www.saifujp777.info/#4064″>バッグ 激安
    </a> <a href=”http://www.saifuonline.info/”>札幌
    </a> <a href=”http://www.hermessaifumise777.info/”>財布
    </a> <a href=”http://www.hermessaifumise.info/”>の財布
    </a>

    Comment by zfpolyiw — November 6, 2012 @ 2:37 am

  6. Your front door should preferably open into a large bright foyer or a living room. ,http://clarisonic-mia2.overblog.com/#16328

    Comment by klicsdjwaf — February 6, 2013 @ 1:54 am

  7. This is the best Product I’ve ever used. It stays on till next day, ,celine bags online us
    ,,http://maccosmeticswholesale.snackblogger.com/#34588

    Comment by aoijrtnhqs — March 1, 2013 @ 3:35 pm

  8. I have tried so many times to apply lashes. ,cheap snapbacks
    ,,http://clarisonic-mia2.snack.ws/#82643

    Comment by zoijrtnngg — March 1, 2013 @ 3:35 pm

  9. buy retin a online no prescriptioncheap generic retin a , http://buyonlineretinanow.com/#ahowi cheap generic retin a

    Comment by trigreell — March 14, 2013 @ 3:55 pm

  10. zithromax 500 mgzithromax 500 mg , http://buyreliablezithromaxonline.com/#htind cheap zithromax

    Comment by LobMoiptHoots — March 16, 2013 @ 9:15 pm

  11. What cosmetic brands do your makeup well? ,polo outlet online ,,http://maccosmeticsus.weebly.com/#37559 ,celine bags online ,,http://macmakeupwholesale.isintofashion.com/#46053

    Comment by klsdfkvvhi — April 9, 2013 @ 11:59 pm

  12. The motorcycle hobby or sport is not just for men. More and more women are taking up riding. This is fantastic, isn’t it guys? Remember when women only rode on the back of a bike as a passenger? Remember sidecars? Women ride and drive everything on the planet. The shoes also come with a padded insole that actually conforms to your foot. It’s made specifically for a woman’s foot and is not just a ray ban cockpit regular padded insole. This makes the Alegria shoes a lot more comfortable oakley sunglasses for women for people who may be on their feet for long periods of time like nurses, teachers, and hairdressers.. I can honestly say that i am one of very many people that have this nylon material fetish and as well i have gone beyond the extreme and have even shared certain things with my gf and as well she said it felt kind of weird at first because she never experienced anything like that before. as for myself i wanted to know if this fetish is normal or abnormal. i have this fetish since i was about 14 and i am 33 now and as well i have jacked off in them and the feeling is great but the experience with someone who i truly love and want to have a greater experience is far more greater then just the material itself and therefore i am going to use the material but only for pleasure and as well as just making one feel good and that is all i Ray Ban Aviator am going to say.. The era of the ‘It’ bag though is most definitely Ray Ban Sunglasses Outlet over, says Angela, as can be seen in the more muted clutches and oversized bags on offer. The Blythe textured calf leather, which comes in black and red in two sizes, features conservative buckle detailing on both sides of the bags. The label’s clutches are, however, much more dramatic, with both the Tube and Cosma bags featuring bright colours and clever studding to create lightweight easy to manage purses that the celebrity set are likely to pounce on.. If it takes 10 months, so be it. The last thing you’d want is for Griffin III to become a case study for what-might-have-been. Rushing back would be foolish, jeopardizing the chances for a long, brilliant career.

    Comment by TSUEY-SHAN LU — April 12, 2013 @ 4:47 am

  13. Hi, I think your blog might be having browser compatibility issues.
    When I look at your website in Ie, it looks fine but when opening in Internet Explorer, it has some overlapping.
    I just wanted to give you a quick heads up! Other then that, amazing blog!

    Comment by extra long iphone cable — April 14, 2013 @ 6:52 am

  14. Ask a question about anything you choose, and let readers from the Journal Community answer it. Plea ywords11.txt,1,S] se fill out all required fields. Please enter a question. The Question description should not be more than 2000 cha 15.txt,1,S] racters. Please choose a cat christian louboutin boots egory Please choose a SubCategory The language you used does not comply with community standards. Please re-enter.

    Comment by Elizabeth Oldenkamp — April 15, 2013 @ 3:54 am

  15. Home Remedies for Kidney Stones. There is a natural cure that can get rid of painful kidney stones, and keep them from coming back again. You can naturally dissolve kidney stones and flush them away, save you from the sky-rocketing cost of surgery. Do you know what kidney stones are? Kidney stones form when crystals of calcium clump together. Kidney stones can also form from mineral deposits, proteins, and other material. The problem with kidney stones is that once you’ve had kidney stones, they could keep coming randomly, for the rest of your life. Kidney stones can block the flow of urine, allowing bacteria to form and causing your kidneys to swell, which lead to serious kidney damage. Click the link to discover a Proven and Safe Remedy that has helped many kidney stone sufferers dissolve their kidney stones, and pass kidney stones without pain.

    Comment by random[a..z] — May 9, 2013 @ 5:08 am

  16. whoah this weblog is great i love reading your articles.
    Keep up the good work! You realize, a lot of persons are
    looking around for this information, you could aid them greatly.

    Comment by carros mais baratos — May 28, 2014 @ 9:31 pm

RSS feed for comments on this post. TrackBack URI

Leave a comment

Powered by WordPress