[EM] A computationally feasible method

[Kristofer Munsterhjelm]

Juho wrote:
> Here's one practical and simple approach to guaranteeing
> computational feasibility of some otherwise complex election methods.
> The original method might be based e.g. on evaluating all possible
> sets of n candidates and then electing the best set. Comparing all
> the sets is usually not computationally feasible. But the function
> that compares two of these sets is typically computationally
> feasible.
> 
> The solution is to apply some general optimization methods (monte
> carlo, following the gradient etc.) to find the best set one can.

As in optimization, if you want to find a local optimum (or the problem
is set up so that hillclimbing finds the global optimum), then that can
work. But in some situations, the local optimum may not be good enough.
For instance, if you want to use Kemeny to determine a social ordering,
then approximating the solution would probably make the new method
(approximation-Kemeny) fail reinforcement.

On the other hand, approximating may make strategy more difficult. I
think Rob LeGrand wrote something about how approximations to minimax
Approval obscured the strategy that would otherwise work.

> To gain even better trust that this set is the best one one could
> publish the best found set and then wait for a week and allow other
> interested parties to seek for even better sets. Maybe different
> parties or candidates try to find alternatives where they would do
> better. If nothing is found then the first found set is declared
> elected.

This strategy could be used for any kind of data where one wants to 
optimize, where getting an approximation isn't too bad, and where it's 
very hard to fix a near-optimal solution (that is, rig it in any one's 
favor). One example where that holds (I think) is redistricting, which 
has been mentioned before. Another, if more abstract, would be the case 
of a democratic economic organization where one first (through some 
democratic method) determines what should be produced, then runs 
optimization (linear programming) to figure out what intermediate 
products have to be made to reach that goal. The optimization would be 
hard, but a similar trick should make it incentive-compatible for any 
faction within the organization to submit a better LP solution while 
making it hard to strategize. If rewards are needed, the difference 
between the best solution and the next best could go to those who 
proposed the best solution, although that may break down if a faction 
gets a sufficiently large computer to go directly to the optimum.

> In this approach one is typically finds a set that is with high 
> probability either the best or at least in value close to best. If 
> better ones can not be found, this set could as well be considered to
> be the best ("best known" at least). Other random factors of the
> election method may well cause more randomness, so from theoretical
> point of view this approach should in most cases be good enough.
> 
> This approach should make many complex methods computationally
> feasible. The involved randomness may be a bit unpleasant, but from
> technical point of view the performance is probably quite good.

In multiwinner election situations (like CPO-STV), the randomness might 
make the losers complain that they lost because the assembly that the 
optimization algorithm stumbled on didn't include them, not because the 
optimal assembly didn't include them. The "everyone may propose a 
solution" approach would to some extent limit these complaints - those 
who won could say "well, if you're on the optimal assembly, why didn't 
you calculate it and submit it as proof?" - but not eliminate it altogether.