6 papers
The Communication Complexity of Instant-Runoff Voting
Ãlie de Panafieu, François Durand, Jérôme Lang
The communication complexity of a voting rule is the worst-case number of bits that n voters must transmit to a central authority under the most efficient elicitation protocol in a…
Super Condorcet Winners and Limit Coalitional Manipulability of IRV
François Durand, Ãlie de Panafieu, Guillem Perarnau
We study the limit CM rate of single-winner voting rules under Impartial Culture, defined as the probability that a preference profile is coalitionally manipulable in the limit of…
Combinatorics of nondeterministic walks
Ãlie de Panafieu, Michael Wallner
This paper introduces nondeterministic walks, a new variant of one-dimensional discrete walks. The main difference to classical walks is that its nondeterministic steps consist of…
Probability of a Condorcet Winner for Large Electorates: An Analytic Combinatorics Approach
Emma Caizergues, François Durand, Marc Noy +2
We study the probability that a given candidate is an alpha-winner, i.e. a candidate preferred to each other candidate j by a fraction alpha_j of the voters. This extends the class…
Tree walks and the spectrum of random graphs
Eva-Maria Hainzl, Ãlie de Panafieu
It is a classic result in spectral theory that the limit distribution of the spectral measure of random graphs G(n, p) converges to the semicircle law in case np tends to infinity…
Robot Positioning Using Torus Packing for Multisets
Chung Shue Chen, Peter Keevash, Sean Kennedy +2
We consider the design of a positioning system where a robot determines its position from local observations. This is a well-studied problem of considerable practical importance an…