[EM] Lp-ball range

[Warren Smith]

On Wed, Sep 7, 2011 at 4:56 PM, Andy Jennings
<elections at jenningsstory.com> wrote:
>> > The unit ball for method two has no corners or bulges (which all other
>> > values of p involve), so the strategy is not so obvious. But if Samuel
>> > Merrill is right, then in the zero information case, the optimum strategy
>> > for method two is to vote appropriately normalized sincere utilities.
>>
>> --wrong.
>> Your best strategy for any of these methods is, you identify the two
>> "frontrunners", you vote max for one and min for the other, and then
>> if you have any freedom left, you start considering the other N-2
>> candidates.
>
> He said "in the zero information case".  I think this means you can't know
> who the frontrunners are.

--Aha!

OK, so I guess Zero Info means that all the other votes
are assumed to be random uniformly selected (independently) from the
allowed-vote ball.

Your best strategy is to maximize expected utility of the winner in
that case.   Assume your probability of you swinging it from winner A
to winner B is roughly proportional to the score-difference your vote
gives
to B minus your score for A.  Also assume that
it is much less (neglectibly less) likely that you can accomplish more
than one swing.

(Those assumptions are correct in regimes where the central limit
theorem holds...)

You then should cast the vote (within the allowed-vote ball) maximizing
    sum_j S_j * (U_j - meanU)
where S_j is your score for candidate j and U_j is your utility for
candidate j.   This sum is proportional
to your expected utility gain from casting a vote versus doing nothing.

Assume wlog for simplicity that meanU=0.

Geometrically speaking, you want to push the hyperplane that is
orthogonal to the direction (U_1, U_2, U_3..., U_N)
as far as you can in that direction, subject to the constraint that it
still have nonempty intersection with
the allowed-votes ball.  Any point within that intersection is an
optimal-vote (to first order, anyhow).

The solution to that problem is obviously a unique
optimal vote for any allowed-votes-ball which
is strictly convex, e.g. for an Lp-ball for any fixed p
within  1<p<infinity.  For the p=1 case, the solution still is
generically unique despite lack of strict convexity.

For the round-ball case p=2,
the optimum vote is proportional to (U_1, U_2,..., U_N)
i.e. your optimum vote is (a normalized version of) honesty, that is,
you pre-normalize your U's so that have mean=0 and variance=1/N then
cast that as your vote-scores.

So this now is in agreement with what FW Simmons (and Merrill?) was
saying.  Note this only works in the (usually unrealistic) zero-info
case.  [Actually I'd said this myself
on some rangevoting.org puzzle-page once in a different context...
this was a way I suggested of inspiring honest utility revelation.]

For the p=infinity case, the solution is non-unique
and we get lots of possible approval-style votes.

So I guess the moral is, if the voters have information, use range
voting (p=infinity); but if they have zero information use round-ball
voting (p=2) and I suppose one now could try to argue that p should
depend smoothly on the amount of information voters have about the
other voters.

Except that seems impracticible.


-- 
Warren D. Smith
http://RangeVoting.org