[EM] Better cardinal methods?

[Kristofer Munsterhjelm]

On 9/27/21 8:43 AM, Andy Jennings wrote:
> Kristofer,
> 
> I, too, find myself going back to the risk-neutral lottery-based 
> definition of utility. I feel like it goes so naturally with "random 
> ballot".
> 
> Suppose V1 has a ranking of A > B > C and V2 has a ranking of C > B > A. 
> In random ballot, V1's vote becomes a lottery ticket that causes A to 
> win and V2's vote becomes a lottery ticket that causes C to win. Let us 
> ask when would V1 and V2 both agree to trade their "one chance of A 
> winning and one chance of C winning" for "two chances of B winning".

There are two threads to this that I think it's useful to keep separate. 
The first is that since we're dealing with lotteries (over candidate 
alternatives), it makes sense to consider *actual* lotteries 
(probabilities of winning) based on this information. The second is 
that, while interpersonal comparisons of utility are very hard (if not 
impossible, e.g. qualia problems), we can access risk neutral lottery 
information.

I was investigating the second aspect, because if Range and Approval's 
failings come from asking more than the voter can provide (namely, 
asking for utilities on an interval scale, and sort of just throwing its 
hands in the air and say "then just normalize"), then it's natural to 
ask, well, what kind of cardinal utility information *can* we get? And 
how can a (deterministic) method that's honest about the limits to its 
information be constructed?

The two threads or lines of investigation may be related, e.g. one such 
method may be "determinize a random method by electing the candidate 
with the greatest probability of victory", justified by arguing that 
this will generally be a good candidate due to the linearity of 
expectation. However, I would imagine that a method specifically 
designed for the deterministic case would be better.

While it's also possible to e.g. take lottery information and "just 
normalize", I have the impression that doing so would add information 
that doesn't exist: it in a sense pretends that what isn't on an 
interval scale actually is. It needs additional justification, e.g. that 
OMOV means that each voter's power should the same, and that a voter 
with an extreme preferences should have all his other preferences 
diminuated rather than the scale being clamped.

> We know we can say little about the "absolute" or "interpersonal" 
> utilities of how U_V1(A), U_V1(B), and U_V1(C) compare to U_V2(A), 
> U_V2(B), and U_V2(C).

Ordinary incommensurability would mean that you can only get an affine 
scaling of the utilities (defined by the lotteries). But I was thinking: 
at least for sensory (hedonic) types of utilitarianism, couldn't you 
define a zero point by saying everything with utility less than zero is 
something you'd prefer not to experience (i.e. you wouldn't prefer a 
presence of this to an absence of this), while everything with utility 
greater than zero is something you would?

> But asking each voter to quantify exactly where B lies on the spectrum 
> between A and C, as a number between 0 and 1, is completely meaningful 
> (in the risk-neutral lottery paradigm).
> 
> Let b_1 = (U_V1(B) - U_V1(C)) / (U_V1(A) - U_V1(C))
> 
> Let b_2 = (U_V2(B) - U_V2(A)) / (U_V2(C) - U_V2(A))
> 
> (In other words, rescale each voter's utility so their favorite 
> candidate is at 1.0 and their least favorite is at 0.0 and examine their 
> utility estimations of B.)

Yes. I used a four-tuple because I was thinking "what if A and C are the 
same utility value, then you'd get a division by zero". But if we also 
gather honest rank information, that problem more or less goes away, 
because it's clear who the voter's favorite and least favorite are 
(excepting the degenerate case where the voter equal-ranks everybody).

There may still be numerical imprecision problems, but let's leave that 
for now; no need to make it any more complex than it needs to.

So the sufficient data would seem to be: an ordering of c candidates, 
plus (c-2) scale values. There are c-2 of these because in a 
two-candidate election, there's no meaningful ratio between the favorite 
and the least favorite, as the affine (or even linear) scaling make 
their utilities completely ambiguous. All we know is that the favorite 
is better than the least favorite.

But that this is sufficient suggests (at least at first glance) that 
cyclical preferences may occur. And perhaps this is a natural 
consequence of being limited to affine/linear scalings of utilities. I'd 
have to think more about what such a cycle "means": I would *guess* it's 
something like that any candidate in the cycle can win depending on what 
the affine constants are (as opposed to say, a Pareto-domination 
situation where everybody ranks A>B>C so that whatever the voters' 
constants are, A is a better candidate than B).

> If b_1 = 0.5 and b_2 = 0.5, we propose they trade "one chance of A 
> winning and one chance of C winning" for "two chances of B winning". The 
> voters are actually completely neutral toward this trade, though as an 
> outsider I much prefer the lowered entropy. b_1 and b_2 would have to be 
> strictly greater than 0.5 for both voters to be excited about the 
> transaction.
> 
> It works for other fractions, too. If b_1 = 0.6 and b_2 = 0.4, the 
> utility-neutral trade is "one chance of A winning and one chance of C 
> winning" for "1.666 chances of B winning and 0.333 chance of C winning". 
> (If b_1 > 0.6 and b_2 > 0.4, then the trade is positive-sum.)
> 
> 
> 
> Can we actually set up this market (declared-strategy style), let all 
> voters submit their three-candidate ranking and a utility (between 0 and 
> 1) for their middle candidate, then we simulate all the trades and come 
> up with a final, optimal lottery?
> 
> A > B > C voters and C > B > A voters would trade with each other. A > C 
>  > B voters and B > C > A voters would trade with each other. B > A > C 
> voters and C > A > B voters would trade with each other.
> 
> It seems obvious to me that in an election where 50% of the voters want 
> A > B > C and 50% want C > B > A, if you can get a number from each 
> voter on where B is on their scale from 0 to 1, that information is 
> useful AND meaningful. I mean, if all the voters say 0.9 then clearly we 
> should just elect B as the compromise candidate. And if all the voters 
> say 0.1, then giving them a 50/50 lottery between A and C is probably 
> the best we can do. Why should we decline to collect and use this 
> "utility of the middle candidate" information?
> 
> How can we simulate those trades? Line up all the A > B > C voters in 
> order of decreasing "B" utility and line up all the C > B > A voters in 
> order of increasing "B" utility and match up the two lines somehow? What 
> about the mismatch in length?
I think the best approach in such a case would be to consider the method 
as an optimization problem: then trading should result in much less path 
dependence because the solver can consider the problem globally.

This optimization problem would contain a penalty on entropy, but I'm 
not sure what more. The obvious choice would be to maximize social 
utility, but since we only have affine transformations (or linear, 
depending on whether the natural zero idea is tenable), we can't extract 
social utility from the ballots, so I'm not sure how to do that.

(Well, you could fit a function of the ballots to maximize VSE under 
say, a spatial model. But I'm not sure what such a function would look 
like and if it would be generalizable. It sounds a bit ugly an approach.)

I'd think the trade idea would produce constraints on the allowed 
solutions that we're optimizing over. Suppose that a A>B>C voter trades 
with a C>B>A voter to decrease both the chance of A and C winning and 
increase the chance of B winning. Then there exists a point where the 
A>B>C voter has given up enough probability that any further increase in 
B's chance of winning only lowers that voter's expected utility. At that 
point, the voter is indifferent between an epsilon more of B winning, 
and e/2 more of A and C winning. So that's a marginal constraint.

I'm not sure how the optimization method should find out who each voter 
would consider trading with, though, and how to handle more complex 
trades. In a market, that's usually handled through some kind of money, 
but there's no money here. Someone who's better than me at 
microeconomics could probably figure that out.

(But the good news, I think, is that the marginal constraints only need 
the lottery information, because they're about indifference between two 
lotteries.)

> One problem I see is that whenever a transaction is perfectly fair, it 
> is utility-neutral, and the two parties are indifferent to whether the 
> trade actually happens. A trade that is positive-sum, on the other hand, 
> has some surplus utility and we could be unfair about which voter 
> captures it.
> 
> If b_1 = b_2 = 0.6, then trading "one chance of A and one chance of C" 
> for any of the following would be utility-neutral or -positive for both 
> voters:
> 
> - 1.666 chances of B winning and 0.333 chance of C winning
> - 2 chances of B winning
> - 1.666 chances of B winning and 0.333 chance of A winning
> 
> Obviously, as neutral election administrators, we should choose the 
> middle option. But I think this illustrates the opportunity for 
> strategic voting in this system. If you, as a voter, have perfect 
> information about the other voters, maybe your utility for B is 0.6 and 
> you see that you can decrease your declared utility for B to 0.400001 
> and still get a trade. It will be a trade the other person barely agrees 
> to, and you'll maximize your utility, capturing all the surplus from the 
> transaction.

Yes, all of the above remarks are in the context of a honest system. The 
deterministic system that I'm interested in would be subject to 
Gibbard's earlier theorem, and the lottery method would probably be 
subject to the later one.

I'm not sure if accounting for strategy can be done as easily through 
the optimization framework. I think there are fields of study on this, 
from an economic perspective, on how to add constraints that make 
certain types of strategy pointless (at the expense of producing some 
lower utility solution), but I don't know anything about them.

> Is there something else we could do as election administrators to make 
> dishonesty less profitable? Does it depend on the way we line up and 
> match up the opposing voters? If we always try to make sure that we 
> match up voters with a "sum of compromise utility" that is greater than 
> one but as small as possible, does that help somehow?
> 
> Perhaps in a large election, it will be difficult to know enough 
> information about the other voters and the benefits will be small enough 
> that voters will just be honest?
> 
> Or maybe we just discard the concept of matching up individual voters, 
> look at all the data, and come up with a "market-clearing price" for 
> turning A and C chances into B chances? Does that fix anything, or just 
> leave a lot of positive-sum transactions unfulfilled?

There's the generalized SARVO approach: arrange the voters in some 
random order. The first voter goes first, the second voter optimizes his 
vote given the first's ballot; the third optimizes wrt the two who went 
before, and so on. Suppose the inner method returns a lottery. Choose 
the lottery that is the expectation of all these lotteries. More complex 
methods could try to use the minmax game AI algorithm for optimizing the 
ballots. (The idea for both is related to the concept of "averaging over 
clairvoyance", which is used in imperfect information game AI when there 
are no information-gathering moves.)

But your idea might be both simpler to program and more comprehensible. 
For a deterministic method, if you can get enough voters to compromise, 
it doesn't matter if the other voters strategize away from the 
compromise, because the compromise candidate will win anyway. So first 
choosing voters who have the most to gain by compromising but not so 
much that they could've misrepresented their ballots (by strategy) and 
got a better result, might work.

Other ideas: perhaps there is some kind of Condorcet analog, i.e. 
treating the ranks plus (n-2) factors as biasing the preferences. If so, 
we could then use standard Condorcet methods on the result and get 
something that's "majoritarian by utility" -- although it wouldn't 
exactly be by utility, since the factors don't set utility. But perhaps 
one could prove say, that if there's a lottery that involves only some 
candidates, and everybody (or some large enough fraction by strength of 
preference) prefers every lottery containing only candidates in that set 
to lotteries containing everybody, then that set (an analog of the Smith 
set) should win.