[EM] Optimal Approval strategy

Fri Apr 26 13:21:06 PDT 2002

Optimal Approval Strategy

One instrumentally-driven strategy for you as a voter in an Approval 
election is to vote for each candidate whose utility for you is at least the 
election’s prior utility (i.e. expected utility without your participation). 
   A couple weeks ago I termed this strategy the ‘Rational Strategy’.

A few days later, as an aside within a long post, Richard Moore noted - very 
tactfully, not mentioning me or taking me to task in any way - that he had 
some time before posted an example showing the non-optimality of this 
‘Rational Strategy’.

To my frustration, for his example's posting, Richard gave no operative 
reference - time or place or name.  Maybe this was for the better:  I was 
forced to devise my own example.  In generic form, this example  readily 
illustrates implications about Approval strategy which likely are well known 
to experts, including various on this list.

However, to a novice like me, these implications were instructive and not 
obvious, and at first were startling.  Accordingly, for possible benefit to 
other novices, the post-script presents the example and its implications.

Joe Weinstein
Long Beach CA USA

POST-SCRIPT:  OPTIMAL APPROVAL STRATEGY -  EXAMPLE AND IMPLICATIONS
Joe Weinstein  -   Fri. 26 April 2002

STRATEGIES.  Suppose you, the voter, are given a set of candidates, with 
your utilities for them.  For an impending single-winner Approval election 
among the candidates, you want to determine a strategy, preferably an 
optimal strategy (i.e. with maximum expected utility from the election).

Strictly speaking,  ‘strategy’ usually means a general rule or recipe which 
you - or whatever fully coordinated bloc of voters you are a part of - can 
apply in many situations:  to many candidate lists, each in many elections.  
  Here, consider the special case where there is but a given single list and 
a single impending election (but in which certain features are variable or 
stochastic), and but a single voter (you) in your bloc.  (As usual, the 
prospective behaviors of the other voters are assumed given, and already 
account for whatever strategy those voters would impute to you.)

Your strategy amounts to deciding - as best you can from information at hand 
- which of the candidates to vote for (i.e. vote YES, ballot checked) and 
which to vote against (i.e. vote NO, ballot left blank).   That is, your 
strategy amounts to specifying your subset S of yes-candidates.

If all candidates have the same utility, then you are indifferent to who 
wins, and so every possible strategy (subset S of the candidates) is 
optimal.

Suppose then that candidates don’t all have the same utility for you.   For 
suitably chosen  units and reference points, your candidate utilities range 
inclusively from 0 (least) to 1 (most).  The ‘best’ candidates are those 
with utility = 1, the ‘worst’ candidates are those with utility = 0, and the 
remaining ‘middling’ candidates have ‘middling’ utility values, i.e. 
strictly between 0 and 1.  There must be at least one best candidate and at 
least one worst candidate.  Let M be the number of middling candidates.  
(Maybe M=0, maybe M>0.)

Now, no matter what strategy you find that seems optimal, you can do no 
worse and you might indeed do better (increase expected utility of the 
election) if you amend the strategy by making sure to vote for all best 
candidates and against all worst candidates.  Hence, for practical purposes 
your strategy is given by just your set S of middling yes-candidates.

MAIN QUESTION.  There are 2^M  (2 to power M)  possible strategy sets S.  
Just which of these could possibly be OPTIMAL?

ANSWER/THEOREM (based on examples below).  ANY subset S whatever - of these 
2^M subsets of the middling candidates - may turn out to be uniquely 
optimal!

Moreover, and more precisely:  suppose that S is any subset whatever of the 
middling candidates, that N is any given integer 2 or greater, and that U is 
any given middling value.  Then:

THERE IS AN ELECTION WITH  N  VOTERS BESIDES YOURSELF,  AND WITH PRIOR 
UTILITY  U  ,  SUCH THAT  S  IS YOUR (UNIQUE) OPTIMAL STRATEGY.

COMMENT.  In other words - contrary to the import of my former postings 
about ‘Rational Strategy’ -  what turns out to be your optimal strategy S 
need have NOTHING to do with the prior utility of the election, or the exact 
values (other than the fact that they are either 0, 1 or middling) of your 
candidate utilities!   In order to arrive at S, knowledge of these values 
may count for next to nought.

EXAMPLE.   We can arrange that the N other voters fall into two categories: 
a bloc of two or more ‘deciding’ voters, and the remaining ‘neutral’ voters. 
  The ‘neutral’ voters, between them, will produce the same aggregate 
support for all candidates: i.e., every candidate will receive the same 
number of neutral-voter votes.  (This situation can always be arranged in a 
trivial way - each voter casts a totally blank or a totally checked ballot - 
and, with at least two neutral voters, in less trivial ways too.)  The 
deciding voters will each vote for the same pair of candidates.  As a 
result, in case you do not participate, the election will produce a tie - to 
be broken by random means - between those two candidates.  Your 
participation can break the tie, but cannot otherwise pick a third winner.

Just WHICH pair of candidates will the deciding voters select for support?  
They will determine this pair randomly, in accord with given probabilities, 
at the last minute before the election.  Only certain ‘selectable’ pairs 
will have non-zero probabilities.

These selectable pairs have the following properties:

	*  Every selectable pair includes at least one non-middling candidate.
	*  Every middling candidate occurs in at least one selectable pair.
	*  If A, B, C are respectively best, middling and worst candidates, then 
{A,B} and {B,C} are not both selectable.  That is, each middling candidate B 
occurs in selectable pairs either just with best candidates or just with 
worst candidates.

Note that given any set S of middling candidates we can always construct a 
set of selectable pairs (and attendant nonzero probabilities) with the above 
properties.  Namely, let the selectable pairs be of the following two kinds: 
{B,C}, for each candidate B in S and each worst candidate C;   and {A,B}, 
for each middling candidate B not in S and each best candidate A.

Moreover, let’s add three special kinds of selectable pairs:  {A,C} for each 
best candidate and each worst candidate, {A1, A2} for each pair of best 
candidates (including case A1=A2), and {C1, C2} for each pair of worst 
candidates (including case C1=C2).

Note that we can assign nonzero probabilities to all resulting selectable 
pairs in such wise that the election will have prior expected utility U.  
Namely, apart from the pairs which comprise just two best candidates or two 
worst candidates, let the sum total of assigned probabilities be 
sufficiently small.  Then a suitable assignment of probabilities to 
best-candidate pairs and worst-candidate pairs can yield the utility U.

NOTE THAT IN THIS EXAMPLE YOU HAVE A UNIQUE OPTIMAL STRATEGY - namely S  
(with vote for all best and against all worst candidates).

Namely, note first that if A is a best candidate and C is a worst candidate, 
an optimal strategy requires that you do vote for A and against C; else, in 
case pair {A,C} is selected, your ballot may leave A tied with C, or even 
win for C over A.

Now, suppose B is any middling candidate.  Your vote for or against B will 
influence the election just in case the deciding voters select a pair which 
contains B.  If B is in S, your vote for B will win the election for B over 
a worst candidate; but your vote against B will leave B tied with a worst 
candidate: so in case B is in S your optimal strategy must include a vote 
for B.  If B is not in S, your vote for B will leave B tied with a best 
candidate; but your vote against B will win the election for that best 
candidate: so in case B is not in S your optimal strategy must include a 
vote against B.

COMMENT.  The example shows that - for determining strategy - past a certain 
point the precise computation of tie probabilities need not matter.  If the 
impending election is known to have certain generic features found in the 
example, all that you must know - but it is essential that you do know - is 
which tie probabilities are zero and which are greater than zero.

Joe Weinstein  -  Fri. 26 April 2002

_________________________________________________________________
Chat with friends online, try MSN Messenger: http://messenger.msn.com

----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em