space and games

March 19, 2010

When is an honest vote a cabal equilibrium?

Filed under: Voting — Peter de Blanc @ 2:11 pm

When I posted about cabal equilibria to election methods mailing list, Jameson Quinn asked me when honest voting is a cabal equilibrium. I have a partial answer.

Assume we are using an election method that satisfies the Condorcet criterion, and there exists a double Condorcet winner. Then an honest vote is a cabal equilibrium.

What is a double Condorcet winner, you ask? It is a candidate C such that, for every other pair of candidates A and B, there exists a majority of voters who each prefer C over both A and B.

Proof: Suppose that an honest vote is not a cabal equilibrium.

Then there must be some set S of voters that can improve the outcome for themselves by changing their votes. Let B be the new winner. Then no member of S may prefer C to B.

In the new strategy-profile, C is no longer a Condorcet winner (or else C would be elected). However, B is still ranked below C by a majority of voters. This is because only members of the set S changed their vote, and by assumption, members of S were already ranking B above C.

Thus, there must be some other candidate A who isn’t ranked below C (i.e. some members of S changed their vote by moving A above C).

Since all voters who prefer C to B are still voting honestly, the set of voters who prefer C to both B and A must not be a majority.

Thus C is not a double Condorcet winner.

January 26, 2010

Summary on Cabal Equilibria and Voting

Filed under: Voting — Peter de Blanc @ 11:29 pm

Last year I introduced cabal equilibria. This post is a summary of my research on cabal equilibria and election methods. Since this is just a short summary, I’m going to skip over any caveats about exact ties in elections.

In any game, a cabal equilibrium is a strategy profile in which no set C of players can simultaneously change strategies in such a way that at least one member of C benefits and no member of C is worse off. Every cabal equilibrium is a Nash equilibrium, but the reverse is not true. For example, in the prisoner’s dilemma, the Nash equilibrium is for both players to defect. This is not a cabal equilibrium, because if both players changed their strategy to cooperate, then both players would benefit. Thus, the prisoner’s dilemma has no cabal equilibria.

The cabal equilibria in elections are particularly interesting, and are related to the notion of a Condorcet winner. In a ranked voting method, a Condorcet winner is a candidate A such that, for any other candidate B, more than half of the voters ranked A higher than B. Of course, the existence and identity of the Condorcet winner (as defined above) depends on how the voters actually vote, not on their true preferences, so for our discussion it’s important to define a pure Condorcet winner as any candidate A such that, for any other candidate B, more than half of the voters actually prefer A to B.

Before I can give my first result, I have to define an election method criterion. An election method is weakly majority-controllable if any majority of voters can cooperate to dictate the outcome of the election, assuming that they already know how the remaining voters are voting. Plurality voting, range voting, all Condorcet voting methods, instant-runoff voting, and the Borda count are all weakly majority-controllable.

My first result is that in any weakly majority-controllable election method, a cabal equilibrium will always elect a pure Condorcet winner.

This is quite easy to see: if an election selects some candidate A who is not a pure Condorcet winner, then there must be some other candidate B whom a majority prefers to A. Since the election is weakly majority-controllable, that majority could change their votes to force B to be elected. That majority has just benefited by changing strategies, so the original election must not have been a cabal equilibrium. Thus any election which does not elect a pure Condorcet winner is not a cabal equilibrium; by contraposition, any cabal equilibrium elects a pure Condorcet winner.

Now let’s define a strongly majority-controllable election method as one in which a majority can control the outcome of the election in which they have to choose their strategies first, even if some members of the majority betray the majority afterwards (as long as it remains a majority). The Borda count is not strongly majority-controllable, but all of the other election methods I mentioned above are.

My second result is that in any strongly majority-controllable election method, the existence of a pure Condorcet winner guarantees the existence of a cabal equilibrium, so this is a partial converse of the first result.

To see this, suppose A is a pure Condorcet winner. Then there is some way that the electorate could vote that guarantees that A will be elected, even if some minority were to change strategies.

Now suppose that there exists a set C of voters that can change their strategies in a way that is beneficial for them. In order for there to be any benefit, the outcome of the election must be changed. No minority of voters has the power to change the outcome, so C must be a majority, and since they consider the change beneficial, none of them may prefer A to the new election outcome. But then A is not a pure Condorcet winner – contradiction.

The Borda count is not strongly majority-controllable, so the existence of a pure Condorcet winner does not guarantee that there is a cabal equilibrium. Here’s an example:

The preferences of the voters are:
5: A > B > C
4: C > B > A
A is the pure Condorcet winner, but the majority cannot simultaneously guard against B and C. For example, if 3 of the majority vote ABC and 2 vote ACB, then the minority can all vote BCA to elect B. Thus there is no cabal equilibrium.

In Hay voting, there are no cabal equilibria except in some degenerate cases. Since every cabal equilibrium is a Nash equilibrium, the only thing that might be a cabal equilibrium is the Nash equilibrium in which each voter votes his or her true preferences. If there exist two players whose utility functions are not scalar multiples of each other, then they can cooperate by each transferring some voting mass between a pair of candidates between which they are relatively indifferent.

Similarly in random ballot, the Nash equilibrium is for each voter to vote for his or her favorite candidate. If there’s a pair of voters who most prefer A and B respectively, but who would choose some compromise C over a coin toss between A and B, then they can cooperate by switching their votes to C.

In both of the above examples, there’s a way for two players can cooperate to get a result that is better than the Nash equilibrium, but now each player has an incentive to betray the other and vote their original choice. This mirrors the Prisoner’s Dilemma, which also has no cabal equilibrium.

I’d like to find an election method where cabal equilibria are likely to exist even with a very large number of candidates, but such a method could not be weakly majority-controllable because the probability of a pure Condorcet winner vanishes as the number of candidates increases (assuming random preferences). This is what I’m thinking about now.

September 21, 2009

Will conditional commitments change politics?

Filed under: Voting — Peter de Blanc @ 12:44 pm

If you think that Condorcet voting would be a good thing, then you should also be in favor of voter collusion, such as Nader Trading, or political analogues of Facebook groups like “Once we reach 4,096 members, everyone will donate $256 to SingInst.org” or “1 million people, $100 million to defeat aging.” When groups can collectively 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, this only works to the extent that people follow through on their promises.

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.

February 5, 2007

More on Hay Voting

Filed under: Voting — Peter de Blanc @ 10:36 pm

What has probably generated the most confusion about Hay Voting is that the original article does not give a formula for the amount of voting mass allocated to each candidate as a function of your utility function. I will derive such a formula here.

First of all, as indicated in the original article, each candidate starts out with √(n−1) units of voting mass on your ballot. The total amount of voting mass does not change; it is only reallocated. If we indicate the final mass allocated to a candidate i by Mi then the probability allocated to i is P(i) = Mi / n√(n−1).

Now, to transfer voting mass from a candidate i to a candidate k (or vice versa), you spend some voting credits. The amount that you transfer is equal to the square root of the amount of credit you spend. To put it another way, the amount you must spend is proportional to the square of the amount of mass you wish to transfer. Your utility density for transfers of mass from i to k is simply the difference in utility between the two candidates: Uk − Ui. As described in “The n-Substance Problem”, your optimal strategy is to transfer an amount of mass proportional to this utility density. So we’ll write ΔMi,k = cUkcUi, where c is some constant (which we will now solve for).

The amount of voting credit you spent on this transfer would be c2 (Uk − Ui)2. We transfer voting mass between each pair of candidates, so the total amount of credit spent is Σ{i, k} c2 (Uk − Ui)2 = 1, since you have one credit. Solving for c, we get c = 1 / √(Σ{i, k} (Uk − Ui)2).

The total mass allocated to candidate i is simply Mi = √(n−1) − ΣkΔMi,k. That is, the initial mass minus the amount transfered to each candidate. Note that the amount transfered can be negative, indicated that mass was transfered to candidate i from somebody else.

So our formulae are:

  1. P(i) = Mi / n√(n−1), where
  2. Mi = √(n−1) − ΣkΔMi,k, where
  3. ΔMi,k = cUkcUi, where
  4. c = 1 / √(Σ{j, k} (Uk − Uj)2)

Combining all the above formulae, we then have:


P(i) = Mi / n√(n−1)
= (√(n−1) − ΣkΔMi,k) / n√(n−1)
= (√(n−1) − cΣk(Uk − Ui)) / n√(n−1)
= (√(n−1) − Σk(Uk − Ui) / √(Σ{j, k} (Uk – Uj)2)) / n√(n−1)

Now why did I leave something this important out of the original article?

September 12, 2006

Hay Voting

Filed under: Decision Theory, Voting — Peter de Blanc @ 2:10 am

Marcello Herreshoff and I talked a bit about voting theory during the Summer of AI, and we came up with our own voting method. In compliance with Stigler’s Law, I’ve decided to call it Hay Voting (after Nick Hay). Hay Voting is, I fear, somewhat impractical, but it has some interesting properties.

Hay Voting is a stochastic voting method; it does not always elect the same candidate given the same votes. Hay Voting is based on the idea of expected utility. It assumes that each voter possesses a utility function which assigns a numeric value to each candidate, and that the voter will vote in such a way as to maximize their expected value for this number. Our intention was to design a voting method such that, when voters follow their optimal strategy, we can deduce their utility functions. You might think of this as a voting method which encourages voters to be “honest.”

A Voting Method that Rewards Honesty

Before I get to Hay Voting, I’m going to talk a bit more about honesty and stochastic methods. Suppose we only wish to know the identity of each voter’s favorite candidate. Here we will give each voter a single vote, which they can cast in favor of any candidate. If we simply count the number of votes for each candidate, and elect the candidate with the most votes (this is called Plurality Voting, and is used by many countries), then we will fail to achieve our goal of discovering which candidate each voter most favors.

That’s because plurality voting introduces voting strategies. Let’s suppose that there is an election between three candidates: A, B, and C. A is really your favorite, but you know that A has no real chance of winning, and the race between B and C is very close. Of those, you prefer B, so voting for B would be a good strategy. So that’s what you do.

Suppose instead that I selected one vote at random. I put all the votes in a hat, pull one out, and elect whichever candidate is lists. If I select a vote other than yours, then your vote had no effect, and if I select your vote, then I elect that candidate. So your optimal strategy is to vote for your favorite candidate – A. So this voting method encourages you to be honest. Of course, all I found out about you was who your favorite candidate was. I don’t know anything else about your preferences.

A Ranked Voting Method that Rewards Honesty

Most voting methods that I know of (e.g. Condorcet Voting, the Borda Count, Instant Runoff Voting (which is awful)) ask each voter to rank each candidate from most to least favorite. All of the methods listed above encourage some strategy; that is, there exist situations in which a voter can achieve a better result by voting something other than vis true preferences. Such situations are supposed to be rare in Condorcet voting methods, but they exist.

It is easy to construct a ranked voting method which encourages voters to be honest – if we assume that the voters are ignorant of the value of a certain variable. Let’s call it X, and let’s say that there are N candidates. We need a probability distribution for X such that p(X=1) > p(X=2) > … > p(X=N).

Now we select a ballot from our hat, and then elect the candidate listed in place X on that ballot. Since that’s most likely to be the first candidate listed, and less likely to be each successive candidate after that, your best bet is to rank the candidates by preference.

The N-Substance Problem

Okay, now we’re almost ready to talk about Hay Voting, but there’s one more preliminary. It’s what I call the “N-substance problem.” Let’s say I’m a merchant, and I have a collection of N different substances which I can sell to you. You have a preference function over these substances, which you are going to try to maximize. I’m making a special assumption about this preference function: it’s a linear combination of the quantities of each substance that you have.

Let’s say Vk is the volume of substance k that you have, for k=1…n. Then your preference function U can be written as:

U = u1V1 + u2V2 + ... + unVn

We can call uk your utility density for substance k.

Let’s say you have 1.00 credit to spend on these substances, but this credit can be divided into arbitrarily small quantities. The N-substance problem is this: how can I devise a pricing scheme such that, based on what you buy, I can determine (up to a positive Affine Transformation) what your utility function is (that is, the values u1un)?

Not just any pricing scheme will work. For example, consider the obvious scheme in which you can buy one liter of any substance for 1 credit. If the substances are green tea, lemonade, and maple syrup, with utility densities 2, 3, and 20 respectively, your optimal strategy is to spend your entire credit on maple syrup, without buying any green tea or lemonade. But then I can’t find out the relative values you assign to green tea and lemonade, so this pricing scheme fails.

So now let’s specify our pricing scheme. We want a function f which determines the volume of substance you get for a given number of credits. And for any u1, u2, we want U = u1f(x1) + u2f(x2) to be maximized whennever f(x1) / f(x2) = u1 / u2. Furthermore, we will arbitrarily set f(1) = 1.

So let’s say we are spending a total of C credits on x1 and x2. Then we can let x2 = C−x1. Now if we differentiate U with respect to x1 (conveniently assuming f is differentiable), we get:

dU/dx1 = u1f'(x1) − u2f'(C−x1)

If U is at a maximum, then this derivative will be 0, so:

u1f'(x1) − u2f'(C−x1) = 0

u1f'(x1) = u2f'(C−x1)

u1 / u2 = f'(C−x1) / f'(x1)

whennever:

f(x1) / f(C−x1) = u1 / u2

Combining these two equations, we get:

f(x1) / f(C−x1) = f'(C−x1) / f'(x1)

We set x1 = 1. Recall that we arbitrarily set f(1) = 1, so:

1 / f(C−1) = f'(C−1) / f'(1)

Letting x = C−1 and letting k = f ‘(1):

1 / f(x) = f'(x) / k

f'(x) = k / f(x)

So f(x) = √x.

Hay Voting

Now we have a pricing scheme which encourages you to purchase quantities of each substance which are proportional to your utility density for that substance – assuming it makes sense to talk about “utility density” (that is, assuming your preferences are linear). When does that assumption hold?

If you’re trying to maximize the expected value of some function, then your preferences are linear over the probabilities assigned to each outcome. So if I sell you probabilities using this pricing scheme, I can discover your utility function!

Under Hay Voting, you receive a ballot which has a √(N-1) units of “voting mass” (called votes) allocated to each candidate, where N is the number of candidates. You get 1.00 voting credit, which you may spend to reallocate some of this voting mass. If you spend x credits to trasnfer mass from candidate A to candidate B, then A loses √x votes and B gains √x votes. The √(N-1) value was selected so that you have just enough voting credit to completely eliminate one candidate from your ballot, or double the voting mass assigned to one candidate.

To elect a candidate, we gather all the ballots together and place them into a hat. One ballot is drawn at random, and then one point of voting mass is selected from that ballot, so that the probability of any candidate being selected is proportional to the amount of voting mass allocated to that candidate.

Now it makes sense to talk about the utility density of a transfer of voting mass from one candidate to another. This density is simply the difference between the utilities you assign to the two candidates. So if you buy these transfers in such a way as to maximize your expected utility, I can see relative sizes of the intervals between the utilities you assign to any two candidates – and that tells me everything there is to know about your utility function over candidates.

Deterministic Hay Voting…?

In Deterministic Hay Voting, the election procedure is as above, but the candidate with the most voting mass is always elected. It may still be possible (at least with idealized agents) to determine the utility functions of the voters by looking at their votes.


Why do we vote? In real life one may vote for any number of reasons: to make a statement, to do one’s patriotic duty, etc. In designing Hay Voting I made the unrealistic assumption that one votes only in order to affect the outcome of the election. I will continue to use that assumption to talk about deterministic voting.

Thus, one’s utility function over votes is dependent upon two things: one’s utility function over candidates, and one’s probability distribution for the effect of one’s vote on the result of the election. The latter can be written in terms of a probability distribution for the actions of the other voters.

As long as it makes sense to talk about the utility density of votes (as long as the size of your own vote is small relative to your uncertainty about how others will vote), we can discover your utility function over votes by using the square-root pricing rule. Then if we knew your probability distribution for the actions of the other voters, we would be able to find the set of all possible utility functions over candidates that would suggest the voting strategy you used.

To discover your probability distribution for the actions of the other voters, we can play a prediction game using a strictly proper scoring rule (you can read about strictly proper scoring rules here). Your reward in this game is based on the probability you assigned to the correct outcome; a strictly proper scoring rule is one such that your optimal strategy is to report your actual beliefs. In this case we would probably prefer a squared-error scoring rule because it is bounded (unlike the logarithm). The reward could be additional votes in the next election.

Deterministic Hay Voting is still a fairly sketchy idea. I’m not sure exactly what conditions the voters’ probability distributions must satisfy in order for it to work.

Again, I feel pretty uncertain about how clear my explanations were here, so please give me feedback and ask questions about anything unclear.

Thanks for reading!

Powered by WordPress