[EM] MELLS (min expected lack of log satisfaction)

[fsimmons at pcc.edu]

I would like to give an introduction to MELLS (min expected lack of log
satisfaction) that explains what kind of "satisfaction" is referred to in its name.

The ballots are cardinal ratings on a range of zero to one hundred percent.

The method assigns each ballot to a candidate in such a way as to minimize a
certain quantity that we choose to call the "expected lack of log satisfaction,"
and then elects the candidate to whom a randomly drawn ballot was assigned.  

For ease of discourse, let's say that the ballot "votes for" the candidate to
whom it is assigned.

The "satisfaction" we have in mind has two factors: the first factor is the
percentage of ballots that voted for the winning candidate.  The second factor
is the geometric mean of the ratings of that candidate on the ballots that voted
for it.

In other words, this kind of satisfaction is jointly proportional to the number
of ballots that ended up voting for the winner and the geometric mean of the
winner's ratings on those ballots.

When we take the log, we get log satisfaction.  The max possible value of this
quantity is zero, which is attained when one hundred percent of the ballots rate
the winner at one hundred percent.

So if we want to deal with positive values, we change the sign to get lack of
log satisfaction.

Then minimizing expected lack of log satisfaction is equivalent to maximizing
expected log satisfaction, but yields a positive optimal value instead of a
negative one.

You might well ask, "Why even bother with logs?"

Of course, expected satisfaction would be positive, but maximizing expected
satisfaction doesn't yield the same nice results as maximizing expected log
satisfaction.

Furthermore, the lack of expected log satisfaction is related rather directly to
what is commonly called the entropy of a probability distribution:  If you add
(to the expected lack of log satisfaction) the log of the geometric mean of all
of the ratings that the ballots give to the candidates that they "voted for,"
then you get what is commonly known as the entropy of the lottery (as a
probability distribution)..

What do I mean by "nice results?"

I mean the family of examples implicit in the following set up:

 (ratings in brackets, with w+x+y+z=100%):

v:  A1>C1[v/(v+w)]>D[v]
w: A2>C1[w/(v+w)]>D[w]
x: B1>C2[x/(x+y)]>D[x]
y: B2>C2[y/(x+y)]>D[y]

In this example there are three lotteries tied for Minimal Expected Lack of Log
Satisfaction.  They are

(1) The Random Ballot Lottery  with respective probabilities v, w, x, y for A1,
A2, B1, B2.

(2) The consensus D "lottery."

(3) The other compromise lottery that elects C1 or C2 with respective
probabilities of (v+w) and (x+y).

The common value of the MELLS for these lotteries is

   - (vlogv+wlogw+xlogx+ylogy),

which is just the entropy of the Random Ballot Lottery.

So these three lotteries are tied for MELLS winner, which is the way it should
be if the ratings are interpreted as  utilities.  In other words, the voters
would be indifferent among these three lotteries if their ratings were "sincere
utilities."

I hope that clarifies the rationale behind MELLS.

Forest