[EM] Saari reply

[Blake Cretney]

On Mon, 2002-06-24 at 20:50, Blake Cretney wrote:
> On Sun, 2002-06-23 at 16:17, Blake Cretney wrote:
> > On Thu, 2002-06-20 at 13:45, Tarr, Adam wrote:
> > > Dave wrote:
> > > 
> > > > I missed any believable proof of this equivalence.
> > > >  
> > 

My previous proof, although correct was more complex than necessary
while not being as general as possible.  So, here's a better version. 
Here's what I'm trying to show

1.  That under a reasonable assumption it is never strategically useful
to vote anything other than minimum or maximum in any ratings-type
method.
2.  That when to rate maximum or minimum can be given in a formula,
which is fairly simple given certain assumptions.  This also shows how
to vote in approval.

Let's say you have a ratings ballot and are considering maximizing the
rating of one candidate as a strategy.  To find out the change in your
expected outcome, you would calculate the sum for each candidate J,

(probability of J in front among candidates other than I)(probability of
changing the result from J to I)(utility of change from J to I)

If you were considering minimizing the rating of a candidate, you would
sum for all J

(probability of J in front among candidates other than I)(probability of
changing the result from I to J)(utility of change from I to J)

The "probability of changing" is the probability that I will be close
enough, and on the right side, so that the change of ratings effects a
change in result.  This may vary based on J.  It is possible that if X
is winning, I is likely to be close, but not if Y is winning.

Now for the assumption.  I will assume that the probability of changing
based on maximizing and minimizing are related in a particular way.  I
will assume that if the probability of changing the result from J to I
is x[J,I], then the probability of changing from I to J when minimizing
is c[i]*x[J,I], where c[i] is some number greater than 0 and not
dependent on J.  That is a weaker assumption than proportional effect,
which I assumed last time.

So, what we get for the expected utility benefit of maximizing is given
by the following formula.  I use
p[J] -- probability of J leading
x[J,I] -- probability maximizing changes victory from J to I
u[I] -- utility of I
u[J] -- utility of J
SUM J<>I -- find the sum of the following expression for all possible J
other than I

Now, the probability of J winning is equal to the probability that I
doesn't win when J is leading among candidates other than I.  So
p[J]=(1-p[I])(prob. of J leading among candidates other than I).  So the
prob. of J leading among candidates other than I is P[J]/(1-p[I])  I
assume that p[I] isn't 1, or else there'd be no point in voting.

e_max=SUM J<>I:  (p[J]/(1-p[I]))*x[J,I]*(u[I]-u[J])

and minimizing
e_min=SUM J<>I:  (p[J]/(1-p[I]))*c[I]*x[J,I]*(u[J]-u[I])

but e_min= -c[I] * e_max

so either e_min=e_max=0, and it doesn't matter whether the rating is
maximized minimized or unchanged, or it does matter, and either
maximizing or minimizing is correct strategy.

To figure out when you should maximize and when you should minimize, you
can use this test.

SUM J<>I: (p[J]/(1-p[I]))*x[J,I]*(u[I]-u[J]) >0

factoring out 1/(1-p[I]) gives

SUM J<>I: p[J]*x[J,I]*(u[I]-u[J]) >0

or

u[I]* SUM J<>I: p[J]*x[J,I] > 
  SUM J<>I: p[J]*x[J,I]*u[J]

If this is true you should maximize.  If not, you can minimize.  If the
two expressions are equal, it doesn't matter what you do.

So, if a ballot has a candidate not maximized or minimized, it is at
least neutral to do one of maximizing or minimizing that candidate.  The
above formula allows you to form a complete ballot by considering
candidates one at a time.  It is possible that a change will alter
probabilities enough that some other ratings should be reconsidered. 
However, since every change is positive, it is impossible to get into an
endless loop, so this procedure will work.

But for reasonable situations, you can make two simplifying
assumptions.  First, that my vote doesn't affect the probabilities
enough to affect my strategy.  Second, that x[J,I] is independent of J. 
This allows it to be factored out.

u[I]* SUM J<>I: p[J] > 
  SUM J<>I: p[J]*u[J]

By adding u[I]p[I] to each side, we get

u[I](p[I]+ SUM J<>I: p[J]) > u[I]p[I]+ SUM J<>I: p[J]*u[J]

But p[I]+ SUM J<>I: p[J] = 1, since it is equivalent to the probability
of any of the candidates winning.  

u[I] > u[I]p[I]+ SUM J<>I: p[J]*u[J]

The equation on the right hand side is simply the sum of all possible
outcomes multiplied by their probability, so I could write,

u[I] > SUM J: p[J]*u[J]

Since these probabilities are assumed to be sufficiently independent of
my vote, I simply calculate the expected utility of the outcome without
my vote, and compare it to the utility of each candidate.  Those
candidates above get maximum support.  Those below get minimum.  That's
how you should vote in approval too.

---
Blake Cretney


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