[EM] Range Voting "unbeatable"?

[Kristofer Munsterhjelm]

Raph Frank wrote:
> On Mon, Aug 31, 2009 at 2:10 PM, Warren Smith<warren.wds at gmail.com> wrote:
>>> What you could do is take a "poll" and have 10 random voters.  You
>> then work out optimal assuming that they are the electorate.
>>
>> --there is no such thing as "optimal strategy" in games with >=3
>> players. Game theory breaks down.
> 
> That probably explains why I couldn't see an obvious way to extend the
> mini-max strategy.

One possible multiplayer extension is the MaxN search for games where 
the "players" take turns:

If your move is a terminal move (you're the last player), the best move 
is the one that maximizes your utility.
Otherwise: The best move is the one for which, when you pick that move 
and recurse to the next moves (for the other players), maximizes your 
utility.

The function passes an n-vector for n players: this vector contains the 
utilities for each player of the moves so far. In the two-player zero 
sum case, you get minimax, since the second player's utility is the 
first player's, negated - i.e. a win for the first player is (1, -1), a 
tie is (0, 0), and a win for the second is (-1, 1).

For an election game, the number of turns would be equal to the number 
of "players" (voters), and the voters would be arranged in a random 
order (different every time). Each voter could have a certain utility 
for each candidate, and then each voter's utility value so far is the 
value of the winner by the voter.

One problem with MaxN is that it is not very amenable to game tree 
pruning. Standard alpha-beta doesn't work.

> I guess what you want is some way for people to suggest strategies and
> then compete them against each other.

That can also be done, but then you need a way of specifying strategies. 
It is possible (see genetic programming), but rather complex.