Category Archives: 2005-2009

Exact results on manipulability of positional voting rules

Geoffrey Pritchard and Mark C. Wilson, Social Choice and Welfare 29 (2007), 487-513.

Download author version

Abstract:

We consider 3-candidate elections under a general scoring rule and derive precise conditions for a given voting situation to be strategically manipulable by a given coalition of voters. We present an algorithm that makes use of these conditions to compute the minimum size M of a manipulating coalition for a given voting situation.

The algorithm works for any voter preference model — here we present numerical results for IC and for IAC, for a selection of scoring rules, and for numbers of voters up to 150. A full description of the distribution of M is obtained, generalizing all previous work on the topic.

The results obtained show interesting phenomena and suggest several conjectures. In particular we see that rules “between plurality and Borda” behave very differently from those “between Borda and antiplurality”.

Twenty combinatorial examples of asymptotics derived from multivariate generating functions

Robin Pemantle and Mark C. Wilson, to appear in SIAM Review, June 2008.

Download author version

Abstract: Let $latex F$ be a power series in at least two variables that defines a meromorphic function in a neighbourhood of the origin; for example, $latex F$ may be a rational multivariate generating function. We discuss recent results that allow the effective computation of asymptotic expansions for the coefficients of $latex F$, uniform in certain explicitly defined cones of directions.

The purpose of this article is to illustrate the use of these techniques on a variety of problems of combinatorial interest. The first part reviews the Morse-theoretic underpinnings of these techniques, and then summarizes the necessary results so that only elementary analyses are needed to check hypotheses and carry out computations. The remainder focuses on combinatorial applications. Specific examples deal with enumeration of words with forbidden substrings, edges and cycles in graphs, polyominoes, descents and solutions to integer equations. After the individual examples, we discuss three broad classes of examples, namely functions derived via the transfer matrix method, those derived via the kernel method, and those derived via the method of Lagrange inversion. Generating functions derived in these three ways are amenable to our asymptotic analyses, and we state some further general results that apply to these cases.

Some old talks

Here are slides for recent talks, in reverse chronological order of delivery. If the date is incomplete, then the slides are not yet available, probably because the talk has not yet been given. Slides for several earlier talks seem no longer to be available. I will be putting up any newer talks as individual blog posts.

Asymptotics of coefficients of multivariate generating functions Workshop in Asymptotic Enumeration, ANU, Canberra, 2007-09-{10-14}.

Polytope computations in social choice theory Auckland Discrete Mathematics and Social Sciences Seminar 2007-04-23.

The diameter of random Cayley graphs 12th AofA workshop Alden Biesen 2006-07-06

Asymptotics of generalized Riordan arrays 11th AofA workshop Barcelona 2005-06-08

Multivariate generating functions II CDMTCS seminar Auckland 2005-04-26

Multivariate generating functions I CDMTCS seminar Auckland 2005-04-12

Sattolo’s algorithm INRIA Rocquencourt 2004-06-28

Towards a theory of multivariate generating functions INRIA Rocquencourt 2004-06-28

Asymptotics of multivariate generating functions Melbourne FPSAC conference 2002-07-

Superalgebras and their uses Missoula 1999-03-09

Primitive ideals in Hopf algebra extensions San Antonio 1999-01-14

Algebras of my acquaintance Auckland 1998-04-29

Asymptotics for generalized Riordan arrays

Mark C. Wilson, Discrete Mathematics and Theoretical Computer Science, volume AD (2005), 323-334 (Proceedings of the 2005 International Conference on Analysis of Algorithms, Barcelona).

Download author version

Abstract: The machinery of Riordan arrays has been used recently by several authors. We show how meromorphic singularity analysis can be used to provide uniform bivariate asymptotic expansions, in the central regime, for a generalization of these arrays. We show how to do this systematically, for various descriptions of the array. Several examples from recent literature are given.