space and games

March 19, 2010

When is an honest vote a cabal equilibrium?

Filed under: Voting — Peter de Blanc @ 2:11 pm

When I posted about cabal equilibria to election methods mailing list, Jameson Quinn asked me when honest voting is a cabal equilibrium. I have a partial answer.

Assume we are using an election method that satisfies the Condorcet criterion, and there exists a double Condorcet winner. Then an honest vote is a cabal equilibrium.

What is a double Condorcet winner, you ask? It is a candidate C such that, for every other pair of candidates A and B, there exists a majority of voters who each prefer C over both A and B.

Proof: Suppose that an honest vote is not a cabal equilibrium.

Then there must be some set S of voters that can improve the outcome for themselves by changing their votes. Let B be the new winner. Then no member of S may prefer C to B.

In the new strategy-profile, C is no longer a Condorcet winner (or else C would be elected). However, B is still ranked below C by a majority of voters. This is because only members of the set S changed their vote, and by assumption, members of S were already ranking B above C.

Thus, there must be some other candidate A who isn’t ranked below C (i.e. some members of S changed their vote by moving A above C).

Since all voters who prefer C to B are still voting honestly, the set of voters who prefer C to both B and A must not be a majority.

Thus C is not a double Condorcet winner.

March 14, 2010

The War Club vs. the Ant-Men, part 1

Filed under: General — Peter de Blanc @ 11:19 pm

Paron had been at the academy for far too long. He had switched from geometry to biology, and finally to game theory. When at last he finished his thesis, it was a cause for celebration. The party was far from grand; more than twenty people were packed into Paron’s meager, candle-lit apartment. Like organisms, conversations competed with their kin for limited attention and limited air while sleep-deprived gamers competed to dominate virtual markets. I was in my element.

“The strange thing about Ant War,” I mused, “is the player. We’re willing to anthropomorphize ants to the point of substituting our own decisions for theirs in the game, but ant behavior is completely inhuman.”

“It’s not like normal human behavior,” said my opponent, Nik, “but unusual situations can produce unusual behaviors. We’re fighting a virtual war; humans could also fight a real one.”

This comment drew Paron’s attention. “More unusual than you might think. A war requires extreme cooperation. The ants in a colony are all sisters, and they share 3/4 of their genes because their father is basically a glorified sperm cell. To get humans to cooperate like ants, they’d have to be born of incest.”

“You don’t need common end goals to cooperate,” countered Nik, “only common proximate goals. Not to mention the fact that evolution formed our goal systems imperfectly; we may agree on values aside from inclusive fitness.”

“But a war requires two coalitions,” said Paron. “You’d need everyone in your coalition to share proximate goals – and everyone in the opposing coalition to share an opposing proximate goal. And if both coalitions are composed of humans? — what could ever cause that, apart from inclusive fitness?”

I moved my ants, then re-entered the conversation. “What about competing protocols? Maybe one coalition follows one set of rules, and the other coalition follows different rules. Economic productivity would be boosted if everyone followed the same rules, but whichever coalition is forced to convert has to pay a cost.”

“But then you’d just bid on it,” said Paron.

“Why don’t ants bid on land?” asked Nik.

Paron said, “Ants don’t engage in inter-colony trade. They’re not smart enough to trade, so they war instead.”

“Let’s go back to end goals,” said Nik. “I think there are goals that all humans share; we all value love, life, and laughter, and not just for ourselves and our kin. One coalition could be human. The opposing coalition could be inhuman.”

“Like what? Giant ants?” I asked.

Nik said, “Or the broad-shouldered people across the sea.”