[EM] Impossibility on Wikipedia: Arrow, Gibbard, and Satterthwaite

[Kristofer Munsterhjelm]

On 2024-02-15 08:13, Rob Lanphier wrote:
> Hi folks,
> 

> Are cardinal voting advocates correct to continually claim that
> Arrow's, Gibbard's, and Satterthwaite's theorems don't apply to their
> favorite voting methods?  Is there a useful distinction to be drawn
> between Gibbard's 1973 theorem and the "Gibbard-Satterthwaite theorem"
> published in 1978?  Is the distinction I draw above correct?

My understanding and opinion is this:

You have three different "main" impossibility theorems:

- Arrow's says that no deterministic reasonable ordinal voting method 
can pass IIA. This means that regardless of whether voters are honest or 
strategic, it's possible that A's win over B depends on not just how 
many voters prefer A to B, but also how many prefer X to Y. This is only 
for cardinal methods.

- Gibbard-Satterthwaite says that no deterministic reasonable ordinal 
method is strategy-proof: there always exists at least one election 
where at least one voter has an incentive to adjust his preferences 
based on how others are voting.

- Gibbard's theorem extends this to a much broader class of election 
methods that includes cardinal methods, thus also implying that no 
deterministic cardinal voting method is strategy-proof.

(In particular, both of Gibbard's theorems are about strategy.)

The part about the revelation principle is incorrect and seems to be 
using a very specific definition of honesty, inspired by Warren Smith. 
To my knowledge, what the revelation principle says is this:

- Say that a participant in a mechanism employs strategy if the 
information he submits to the mechanism depends on the actions of the 
other participants or his belief about them.[1]

- Say that a mechanism only uses honesty if no participant has an 
incentive to employ strategy.

- Then, if there exists a mechanism where people employ strategy to 
drive it to an optimal or equilibrium outcome, then there also exists a 
mechanism that only uses honesty that reaches the same outcome or 
equilibrium.

Consider it like this: suppose you're involved in a court case, and you 
hire a lawyer. You tell the lawyer the truth and the lawyer comes up 
with whatever strategy that will advance your interests, given the 
evidence and information about the other party. That's a system where 
you or your lawyer use strategy to drive the system to a particular state.

But consider a hypothetical legal system using an AI judge. This AI has 
a lawyer interface to each party; upon hearing the truth from each 
party, it then simulates a court case the way it would proceed with 
virtual lawyers who employs strategy based on the honest information. 
The AI comes with a proof that your virtual lawyer won't incriminate 
you. You would then interact honestly with the system, represented by 
the judge, and it would strategize internally.

Thus for any system that requires strategy to get an equilibrium, there 
exists another system where you can be honest. It just absorbs the 
"lawyer component" into itself.

The problem is that there is no such equilibrium for deterministic 
voting methods. That's implied by Gibbard, because otherwise, you could 
create a strategy-proof method by first creating a method that invites a 
particular type of strategy, and then embodying a "lawyer component" 
into it to perform that strategy.

If you try to do this, as far as I understand it, you get a 
nondeterministic method since the equilibrium is a mixed strategy. And, 
as we know, there exist strategy-proof nondeterministic methods, so that 
fits.

This would be like: sometimes, your lawyer says "if we do this, then no 
matter what the other party does, we win". But other times he says "if 
we focus on these elements and the other party focuses on those, then we 
win". Like rock-paper-scissors, which strategy you should play depends 
on the strategy the other guy is going to use. So you play them at 
random in such a way that the other guy can't guess what you're doing. 
That gives a nondeterministic method.

Okay.

So now about IIA.

The seeming advantage that cardinal methods have over ordinal ones is 
that they pass IIA. In Range, if A has score 100 and B has score 50, 
then A will continue to beat B even if we remove every other candidate.

But I've always been of the opinion that this IIA compliance is either 
illusory or a distraction, because it doesn't answer what we really care 
about. And that is whether the presence of a candidate who doesn't win 
changes the outcome.

Some cardinal proponents say that methods like Range have multiple 
honest ballots: there are many ways to vote that are all consistent with 
your preference ordering. But a voter has to choose which honest ballot 
to cast, and there's no externally fixed scale (what exactly does ten 
points mean? What does zero mean?).[2] Thus the selection of candidates 
who run will affect the scale, which means that some voters would change 
their ratings based on who's running - even if those additional 
candidates don't win. So these methods fail what we could call "de facto 
IIA", for lack of a better term.

For instance, suppose the election starts off with two pro-democracy 
candidates. Then a number of authoritarians enter the race. It's likely 
that in Approval, some voters who would've approved of one of the 
pro-democracy candidates but not the other, would now approve both to 
mark their distaste for authoritarianism and keep the authoritarians 
from winning.

So in my opinion, ordinal methods are merely honest about their 
limitations. Their logic says: "okay, I can't know if his 10/10 is the 
same as her 10/10 or her 5/10. I'll accept that this means I must fail 
IIA, instead of seeming to pass it by passing the buck to the voters 
that they must use a fixed scale that's not affected by who's in the race."

So ordinal methods clearly fail IIA, and aren't strategy-proof (by 
Gibbard-Satterthwaite). Cardinal methods pass IIA (but it doesn't mean 
what one may think it means) and aren't strategy-proof (by Gibbard's 
theorem).

Both ordinal and cardinal methods may pass de facto IIA for subsets of 
elections. E.g. Condorcet methods pass IIA as long as there is a CW, 
because adding a candidate either makes that candidate the new CW (hence 
he's not irrelevant) or the current winner stays a CW. Similarly, 
Approval passes de facto IIA with dichotomous preferences where every 
voter has a class of OK candidates and a class of not-OK candidates, and 
the boundary between OK and not OK doesn't depend on who's in the race. 
(Such voters may sometimes approve everybody or nobody.)

But in general: both cardinal and ordinal methods are susceptible to 
strategy. And both cardinal and ordinal methods may have the winner 
change from A to B as a consequence of C entering the race.

-km

[1] Strictly speaking we would also want "honesty" to have some 
connotation of "being the actual information being asked for". Say 
you're dealing with a system that asks you what you like the least and 
then gives it to you. You would answer its question with a thing that 
you want to be given, so that answer stays the same no matter what other 
people interacting with it would say. So by my definition that wouldn't 
be strategy, but common-sense would say that it is not honest either.

Warren's definition of honesty is somewhat based on this idea, but it 
goes too far in the other direction. It doesn't consider ballots where 
your ranking stays the same as under honesty but your scores don't, as 
being strategic. I think in part that's due to the difficulty in 
comparing utilities, but we *can* hold rated voting to a higher 
standard. Ask and I'll elaborate - this post is long enough :-)

[2] As a side note: we probably can make *some* observations of other 
people's utilities even if we don't have a fixed scale. For instance, I 
can probably reason that a candidate who would put you in a prison camp 
would be a much worse choice from your perspective than one who would 
arrange a party; and that the difference in utilities would be much 
greater than say, between a candidate who holds a week-long party and 
one who holds a two-week long party.

Some cardinal proponents also refer to von Neumann-Morgenstern utilities 
as a way of making comparisons between people's strength of preference: 
basically using lotteries to determine how much more a voter prefers one 
choice to another. But such scales still need to be normalized because 
they always have two unknown variables per voter. Methods that do the 
normalization so as to give each voter the same strength fail IIA. Not 
doing such renormalization can make the method pass IIA but they still 
don't pass "de facto IIA".

See e.g. 
https://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Morgenstern_utility_theorem#Incomparability_between_agents 
for the need for normalization.