Wednesday, May 12, 2010

UK election game

Here's a fun game-theory problem; Martin Gairing helped me find a solution during lunch, which I will add later.

There are 2 political parties and N constituencies; each party wants to win as many of them as possible. Both parties have an amount M of money (to spend on election campaigning) which they split amongst the N constituencies; for each constituency, it is won by the party that allocated it the larger amount of money. A party's payoff is the number of constituencies it wins, so it's a zero-sum game. The problem is to find a Nash equilibrium. You can assume that M is infinitely divisible, or if not, you're allowed to find an approximate solution with error proportional to 1/M.

Note that there is no pure equilibrium; if a party fails to randomize, the other one will be able to narrowly defeat it in nearly all constituencies while allocating no money to one(s) that it loses.

Obviously lots of generalizations are possible...

7 comments:

Anonymous said...

My rough guess

choose a random permutation of the constituencies and allocate 2(i-1)M/((N(N-1)) to the i-th constituency.

If both parties follow this, each should win (N-1)/2 constituencies in expectation. Additionally, in expectation, one constituency will be a tie.

Ashley said...

Another fun and topical game to play is to work out, using the techniques of Section 3.4 of this survey or similar, how sensitive the UK election is to noise (i.e. mistakes in tallying ballots). If I haven't made a mistake, for small levels of noise, our current constituency system is about 20x more likely to give the "wrong" answer than straight majority voting...

Anonymous said...

@Anonymous

For M=N=3 I can beat your random permutation of {0,1,2} by taking a random permutation of {1.49, 1.49, 0.02} (I always beat your 0, always lose to your 2, and beat your 1 two-thirds of the time)

Paul Goldberg said...

In reply to comment 3: I agree, that breaks the suggestion of comment 1. But the idea of comment 1 is roughly correct, at least it becomes a good approximate Nash equilibrium for large N (error proportional to 1/N). Tomorrow I will give a 3-constituency solution...

To Ashley, thanks for the link, I spent some time reading the survey this morning and will continue! I would have guessed that the sensitivity to noise was about that same.

Paul Goldberg said...

To give the game away, so to speak, a party should aim for the following: For each constituency, the amount spent on it should be uniformly distributed in the range [0,2M/N]. If this can be achieved, then for the other party, the probability of winning a given constituency is directly proportional to the amount it spends there, up to a limit of 2M/N, beyond which there is no incentive to spend more. One constituency's gain becomes another's loss, and you may as well use any payments that are all below 2M/N.

To achieve this for the 3-constituency case, let's put M=1 without loss of generality; choose a random number x uniformly in [0,1/3] and spend it on constituency 1. Choose one of the other 2 constituencies at random and spend 2/3-x/2 on it, and spend the rest on the other one.

Larger values of N are left as an exercise.

David Kempe said...

Sounds quite related to Colonel Blotto Games. (I hope I got the spelling right there.) Though if I remember right, there, you don't care about how many constituencies you win, just winning more than your opponents.

Paul Goldberg said...

David, thanks, I just took a look at the wikipedia page, they look similar; I will now study them further!