Tag Archives: voting

Condorcet Paradoxes and dice

Posted on by

NB: don’t take this as a sign that I’ve brought the blog back to life for real. I’ve made too many unfulfilled promises on that front…

There was a talk at UChicago in the fall (I’m still on the seminar mailing lists) given by Jan Hązła based, I think, on a paper titled “The Probability of Intransitivity in Dice and Close Elections” with Elchanan Mossel, Nathan Ross, and Guangqu Zheng. The abstract was quite interesting and led to a discussion with my colleagues Emina Soljanin and Roy Yates in which I realized I didn’t quite get the result so I promised to come back after reading it more carefully. Fast forward several months and now I am in Berkeley (on a pre-tenure sabbatical) and they are back east so I figured I could at least blog about it.

The problem is about intransitive dice, which was a new term for me. Consider an n-sided die with numbers \mathbf{a} = (a_1, a_2, a_n) and call \sum_{i=1}^{n} a_i the face sum. The die is fair, so the expected face value is \frac{1}{n} \sum_{i=1}^{n} a_i. We can define an ordering on dice by saying $\mathbf{a} \succ \mathbf{b}$ if a uniformly chosen face of \mathbf{a} is larger than a uniformly chosen face of \mathbf{b}. That is, if you roll both dice then on average \mathbf{a} would beat \mathbf{a}.

A collection of dice is intransitive if the relation \succ based on dice beating each other cannot be extended to a linear order. The connection to elections is in ranked voting — an election in which voters rank candidates may exhibit a Condorcet paradox in which people’s pairwise preferences form a cycle: A beats B, B beats C, but C beats A in pairwise contests. (As an aside, in election data we looked at in my paper on instant runoff voting we actually rarely (maybe never?) saw a Condorcet cycle).

Suppose we generate a die randomly with face values drawn from the uniform distribution on [-1,1] and condition on the face sum being equal to 0. Then as the number of faces n \to \infty, three such independently generated dice will become intransitive with high probability (see the Polymath project).

However, it turns out that this is very special to the uniform distribution. What this paper shows (among other things) is that if you generate the faces from any other distribution (but still condition the face sum to be 0), the dice are in fact transitive with high probability. This to me is interesting because it shows the uniform distribution as rather precariously balanced — any shift and a total linear order pops out. But this also makes some sense: the case where the dice become intransitive happens when individuals essentially are choosing a random permutation of the candidates as their preferences. In face, the authors show that if you generate voters/votes this way and then condition on the election being “close” you get a higher chance of turning up a Condorcet paradox.

The details of the proofs are a bit hairy, but I often find ranking problems neat and interesting. Maybe one day I will work on them again…

Advertisement

ISIT Blogging, part 2

Posted on by

Logarithmic Sobolev inequalities and strong data processing theorems for discrete channels
Maxim Raginsky (University of Illinois at Urbana-Champaign, USA)
Max talked about how the strong data processing inequality (DPI) is basically a log-Sobolev inequality (LSI) that is used in measure concentration. The strong DPI says that
D(QW \| PW) \le \alpha D(Q \| P)
for some \alpha < 1, so the idea is to get bounds on
\delta^*(P,W) = \sup_{Q} \frac{D(QW \| PW)}{D(Q \| P)}.
What he does is construct a hierarchy of LSIs in which the strong DPI fits and then gets bounds on this ratio in terms of best constants for LSIs. The details are a bit hairy, and besides, Max has his own blog so he can write more about it if he wants…

Building Consensus via Iterative Voting
Farzad Farnoud (University of Illinois, Urbana-Champaign, USA); Eitan Yaakobi (Caltech, USA); Behrouz Touri (University of Illinois Urbana-Champaign, USA); Olgica Milenkovic (University of Illinois, USA); Jehoshua Bruck (California Institute of Technology, USA)
This paper was about rank aggregation, or how to take a bunch of votes expressed as permutations/rankings of options to produce a final option. The model is one in which people iteratively change their ranking based on the current ranking. For example, one could construct the pairwise comparison graph (a la Condorcet) and then have people change their rankings when they disagree with the majority on an edge. They show conditions under which this process converges (the graph should not have a cycle) and show that if there is a Condorcet winner, then after this process everyone will rank the Condorcet winner first. They also look at a Borda count version of this problem but to my eye that just looked like an average consensus method, but it was at the end of the talk so I might have missed something.

Information-Theoretic Study of Voting Systems
Eitan Yaakobi (Caltech, USA); Michael Langberg (Open University of Israel, Israel); Jehoshua Bruck (California Institute of Technology, USA)
Eitan gave this talk and the preceding talk. This one was about looking at voting through the lens of coding theory. The main issue is this — what sets of votes or distribution of vote profiles will lead to a Condorcet winner? Given a set of votes, one could look at the fraction of candidates who rank candidate j in the i-th position and then try to compute entropies of the resulting distributions. The idea is somehow to characterize the existence or lack of a Condorcet winner in terms of distances (Kendall tau) and these entropy measures. This is different than looking at probability distributions on permutations and asking about the probability of there existing a Condorcet cycle.

Brute force searching, the typical set and Guesswork
Mark Chirstiansen (National University of Ireland Maynooth, Ireland); Ken R Duffy (National University of Ireland Maynooth, Ireland); Flávio du Pin Calmon (Massachusetts Institute of Technology, USA); Muriel Médard (MIT, USA)
Suppose an item X is chosen \sim P from a list and we want to guess the choice that is made. We’re only allowed to ask questions of the form “is the item Y?” Suppose now that the list is a list of codewords of blocklength k drawn i.i.d. according to Q. This paper looks at the number of guesses one needs if P is uniform on the typical set according to Q versus when P is distributed according the distribution Q^k conditioned on X being in the typical set. The non-uniformity of the latter turns out to make the guessing problem a lot easier.

Rumor Source Detection under Probabilistic Sampling
Nikhil Karamchandani (University of California Los Angeles, USA); Massimo Franceschetti (University of California at San Diego, USA)
This paper looked at an SI model of infection on a graph — nodes are either Susceptible (S) or Infected (I), and there is a probability of transitioning from S to I based on your neighbors’ states. There in exponential waiting time \tau_{ij} for the i to infect j if i is infected. The idea is that the rumor starts somewhere and infects a bunch of people and then you get to observe/measure the network. You want to find the source. This was studied by Zaman and Shah under the assumption of perfect observation of all nodes. This work looked at the case where nodes randomly report their infection state, so you only get an incomplete picture of the infection state. They characterize the effect of the reporting probability on the excess error and show that for certain tree graphs, incomplete reporting is as good as full reporting.

Linkage

Posted on by

I’m heading off to Mexico in less than 12 hours for a week during which I hope to disconnect : no email, web, or phone. I guess I’ll miss the majority of the post-Bin Laden news cycle. In the meantime, here are some more links because I am too lazy to post content.

Speaking of 9/11, this is simply terrible.

An interview with George Saunders, one of my favorite authors.

Blackwell’s proof of Wald’s Identity, as told by Max.

Long pepper looks fascinating and tasty!

Can Voter ID Laws Be Administered in a Race-Neutral Manner? The short answer is no. The longer answer is a 30 page paper.

Frank has blogger about our trip last weekend to The 2nd 8th Annual Grilled Cheese Invitational. My arteries may never be the same again.

There are no more typewriter factories. This makes me especially sad, as I have a 1914 Underwood No. 5 that I love (and lug).

Online voting is like drunk driving

Posted on by

So one of the stories that circulated during the EVT/WOTE workshop last summer revolved around a presentation given by Ron Rivest at a special workshop on Uniformed and Overseas Citizens Absentee Voting Act (UOCAVA) in which he compared online voting to drunk driving. Today I saw that he has in fact posted the slides. Why the fuss? Apparently the default solution was to conduct voting for military personnel posted in say, Afghanistan, via the internet. There are a raft of security issues with this, as outlined in the slides. They are pretty amusing, except when you realize that they will probably do the voting over the internet thing anyway.

Readings

Posted on by

The Solitudes (John Crowley) – The first book in the Aegypt Cycle, as recommended by Max. This book really blew my mind. I don’t really see it as “fantasy” but an expansive meditation on memory and history. It’s the first book in a 4-part series, and I’m looking forward to finishing the rest of the cycle.

Impossible Subjects: Illegal Aliens and the Making of Modern America (Mae M. Ngai) – a fascinating scholarly history of the idea of the “illegal immigrant” that provides a much needed context for our contemporary debate on the subject. Ngai shows how recent our notions of citizenship and immigration are vie the history of the debates and revisions of statues from the 19th and 20th centuries. Highly recommended.

The Toughest Indian in the World (Sherman Alexie) – a collection of short stories by one of the most famous contemporary Indian novelists. It surprised me and shocked me at times, but some of the stories and images really stuck with me. I haven’t read Alexie’s other collections so I don’t know how it compares.

The Human Use of Human Beings (Norbert Wiener) – Wiener’s general-audience book on cybernetics has lots of gems that I’ve been blogging here and there. I found it interesting because at the time his ideas were somewhat new, and now they either seem antiquated or have been absorbed into out “default” view of things.

Absurdistan (Gary Shteyngart) – A madcap farce involving a massively overweight and fabulously wealthy Russian Jew trying to muddle his way through a massively dysfunctional Central Asian nation. It’s over the top and some readers may not enjoy the narrator’s neuroses, but it was pretty funny, if raw.

Numbers Rule (George Szpiro) – This is another book on the history of voting and electoral apportioning schemes. Szpiro takes us chapter-by-chapter through famous figures in the history of voting — from Ramon Llull through the Marquis de Condorcet and Charles Dodgson to Kenneth Arrow. A very entertaining read, if less of a page-turner than Poundstone’s book. The sections on choosing the number of representatives for each state in the House is pretty fascinating.