Category Archives: 2010-2014

Distance-based voting rules

After a long gestation period in which I seemed to be publishing nothing, a few projects have reached maturity. With Benjamin Hadjibeyli, I have a preprint studying so-called distance rationalizable voting rules, which we recently submitted. These are voting rules in which we specify some notion of consensus winner, set up a distance measure on elections, and then choose the winner(s) based on minimizing the distance to a consensus election. This framework has been used by other authors over the years, particularly by Edith Elkind, Piotr Faliszewksi and Arkadii Slinko in a series of papers.

We deal with a lot of foundational issues and give some insight into the way Minkowski geometry relates to decisiveness of such rules. This includes both positive and negative results.

This work was inspired by discussions with Elchanan Mossel and Miklos Racz in Berkeley in 2013, about whether the Dodgson rule is a so-called hyperplane rule. That question is still not answered, but now the underbrush has been cleared, it makes sense to go back to it.

Flajolet memorial volume of CPC

The journal Combinatorics, Probability and Computing (obviously, since the publisher is Cambridge University Press, it doesn’t use the “Oxford comma”) will publish a special issue dedicated to Philippe Flajolet, whose early death in 2011 shocked, although perhaps didn’t surprise, the Analysis of Algorithms community.

I have submitted a paper, and judging from one I have been asked to referee, the standard will be high. Philippe’s own research work and encouragement of others were an inspiration to the entire community, and I am sure everyone wants to submit something approaching his standards.

Research happenings

Publications 

I have updated my local archive  to reflect some new publications:

  • Simulator for the 2011 NZ Referendum (with Geoffrey Pritchard), Parliamentary Affairs, to appear.
  • Best Reply Dynamics for Scoring Rules (with Reyhaneh Reyhani), Proceedings of ECAI 2012.
  • Coordination via Polling in Plurality Voting Games under Inertia(with Reyhaneh Reyhani and Javad Khazaei), Proceedings of COMSOC 2012.
  • Asymptotics of coefficients of multivariate generating functions: improvements for multiple points. Online Journal of Analytic Combinatorics 2012.
  • Power measures derived from the sequential query process (with Geoffrey Pritchard and Reyhaneh Reyhani), Mathematical Social Sciences, to appear.
  • Random Cayley digraphs of diameter 2 and given degree (with Manuel Lladser, Primoz Potocnik and Jozef Siran), Discrete Mathematics and Theoretical Computer Science 2012.

 

The Complexity of Safe Manipulation under Scoring Rules

This paper will appear in Proceedings of IJCAI ’11 and be presented at the conference in Barcelona in July.

Abstract: Slinko and White have recently introduced a new model of coalitional
manipulation of voting rules under limited communication, which they
call {em safe strategic voting}. The computational aspects of this
model were first studied by Hazon and Elkind, who provide
polynomial-time algorithms for finding a safe strategic vote under
$k$-approval and the Bucklin rule. In this paper, we answer an open
question of Hazon and Elkind by presenting a polynomial-time algorithm
for finding a safe strategic vote under the Borda rule. Our results for
Borda generalize to several interesting classes of scoring rules.

Asymptotics of coefficients of multivariate generating functions: improvements for multiple points

This has been uploaded to arXiv and submitted to Online Journal of Combinatorics. Interestingly, it was rejected by Electronic Journal of Combinatorics without refereeing, as being out of scope. It improves on previous work mainly by giving explicit formulae. The main work associated with this paper is the SAGE implementation by Alex Raichev. Computation of higher order asymptotic expansions by hand is essentially impossible, hence the paucity of numerical or explicit results  in published papers.

Download author copy

The probability of safe manipulation

This paper (joint with Reyhaneh Reyhani) will be presented at COMSOC 2010. It deals with the concept of “safe manipulation”, whereby an agent can attempt to manipulate the result of an election without risk, provided that voters of other preferences vote sincerely but irrespective of the number of like-minded voters that also try to vote strategically. It was introduced by Slinko and White in COMSOC 2008.

Abstract: The concept of safe manipulation has recently been introduced by Slinko and White. We show how to compute the asymptotic probability that a safe manipulation exists for a given scoring rule under the uniform distribution on voting situations (the so- called Impartial Anonymous Culture). The technique used is computation of volumes of convex polytopes. We present explicit numerical results in the 3-candidate case.

Download author copy

An interesting new Mahonian permutation statistic

While studying the standard method for random permutation generation I discovered a function whose distribution on a uniformly random permutation of fixed length is the same as that of the number of inversions. Such things are called Mahonian permutation statistics.

This statistic appears to be new, but this is not as easy to show as I would like. After several attempts to find out by reading papers, asking experts and doing database searches, I concluded that it probably was and submitted the paper to the arXiv and for publication. Almost immediately I got email from Dennis White at University of Minnesota pointing out a connection with a paper by him and Galovich in 1996. This raises some questions: how much responsibility do we have in the modern research environment to check novelty? why is there no standard database of numerical values of all important functions, and how do we achieve one?

Abstract: The standard algorithm for generating a random permutation gives rise to an obvious permutation statistic $stat$ that is readily seen to be Mahonian. We give evidence showing that it is not equal to any previously published statistic. Nor does its joint distribution with the standard Eulerian statistics $des$ and $exc$ appear to coincide with any known Euler-Mahonian pair.
A general construction of Skandera yields an Eulerian partner $ska$ such that $(ska, stat)$ is equidistributed with $(des, maj)$. However $ska$ itself appears not to be a known Eulerian statistic.
Several ideas for further research on this topic are listed.

Download author copy

AAGTSC 2010

The newly formed Centre for Mathematical Social Sciences at the University of Auckland (of which I am a founding member) recently held its first event, a workshop on Algorithmic Aspects of Game Theory and Social Choice. There were some interesting talks and some good colleagues from overseas attended. I enjoyed it very much. Thanks to all the participants especially those coming from afar.