[EM] The Ultimate Lottery Method!

[fsimmons at pcc.edu]

I wonder if the solution to the maximization problem could be done iteratively
analogous to the iterative computation of  an eigenvector:

Initialize a column matrix V with 1/n in all n rows, where n is the number of
alternatives.

For each ballot vector b, form another column matrix W(b) whose k_th component is 

  (1/N)*V[k]*b[k]/(the dot product of b and V) 

Update V as the sum of all the W(b) over b.

Repeat until V stabilizes.

> Ballots are ratings with a minimum possible rating of zero.

> Ballots with all zero ratings are thrown out as not valid.

> The lottery probabilities are chosen so as to maximize the product of the
> expected ratings over the ballots.

> This method is (1) monotone, (2) clone free, and (3) gives proportional
> probability to stubborn voters.  (4) Each ballot has equal weight in determining
> the winning probabilities. (5) Good opportunities for cooperation are not wasted
> by this method. (6) There is little if any incentive for insincere ratings.

> Let's use the Lagrange multiplier method to find the lottery that maximizes the
> product of the expected ballot ratings:

> Let ProdE represent the product of the expected ratings, and let SumP represent
> the sum of the lottery probabilities.  Then a necessary condition for maximality
> of ProdE is the stationarity of the expression

> L = log(ProdE) - Lambda*SumP

> as the lottery probabilities are varied subject to the constraint SumP = 1.

> Setting to zero the partial derivative of  L  with respect to the lottery
> probability p(k) of the k_th alternative (i.e. candidate number k) verifies
> claim (4) in that each ballot b contributes to p(k) precisely the quantity

> (1/N)*p(k)*b(k)/E(b)

> where N = Lambda is the number of ballots, b(k) is ballot b's rating of
> alternative k, and E(b) is ballot b's expected rating

> E(b) = p(1)*b(1) + p(2)*b(2) + ...