Mark C. Wilson: Publications

Here is an archive of my formally published pieces, in roughly reverse chronological order of production. Some are not peer reviewed publications (such as submissions to government and opinion pieces), but most are, and are marked as such.

The files available here often differ slightly from the officially published version, but I try to post the last ("postprint") version I submitted to the publication (obviously I have no control on what they do after that). I also link to the journal version. Variants of the same basic paper (for example, conference versions) are merged into the "final" version. The abstracts below are taken directly from the paper, and may contain LaTeX symbols. MathJax should render these nicely in your browser but this is not guaranteed.

Partial, less reliable lists of my research publications can also be found at (in roughly descending order of completeness) MathSciNet, DBLP , arXiv.org

Refereed research papers and books

Information Extraction Framework to Build Legislation Network
(with Neda Sakhaee), 20pp, submitted.

This paper concerns an Information Extraction process for building a dynamic Legislation Network from legal documents. Unlike supervised learning approaches which require additional calculations, the idea here is to apply Information Extraction methodologies by identifying distinct expressions in legal text and extract quality network information. The study highlights the importance of data accuracy in network analysis and improves approximate string matching techniques for producing reliable network datasets with more than 98 percent precision and recall. The values, applications, and the complexity of the created dynamic Legislation Network are also discussed and challenged.

Quiver Asymptotics: $\mathcal{N}=1$ Free Chiral Ring
(with Sanjaye Ramgoolam and Ali Zahabi), 18pp, submitted.

The large N generating functions for the counting of chiral operators in $\mathcal{N}=1$, four-dimensional quiver gauge theories have previously been obtained in terms of the weighted adjacency matrix of the quiver diagram. We introduce the methods of multi-variate asymptotic analysis to study this counting in the limit of large charges. We describe a Hagedorn phase transition associated with this asymptotics, which refines and generalizes known results on the 2-matrix harmonic oscillator. Explicit results are obtained for two infinite classes of quiver theories, namely the generalized clover quivers and affine $\mathbb{C}^3/\hat{A}_n$ orbifold quivers.

Balance and Frustration in Signed Networks
(with Samin Aref), Journal of Complex Networks 7, 163-189, 2019.

The frustration index is a key measure for analysing signed networks, which has been underused due to its computational complexity. We use an exact optimisation-based method to analyse frustration as a global structural property of signed networks coming from diverse application areas. In the classic friend-enemy interpretation of balance theory, a by-product of computing the frustration index is the partitioning of nodes into two internally solidary but mutually hostile groups. The main purpose of this paper is to present general methodology for answering questions related to partial balance in signed networks, and apply it to a range of representative examples that are now analysable because of advances in computational methods. We provide exact numerical results on social and biological signed networks, networks of formal alliances and antagonisms between countries, and financial portfolio networks. Molecular graphs of carbon and Ising models are also considered. We point out several mistakes in the signed networks literature caused by inaccurate computation, implementation errors or inappropriate measures.

Inputs, Algorithms, Quality Measures: More Realistic Simulation In Social Choice
to appear Future of Economic Design (editors: Jean-Francois Laslier, Herve Moulin, Remzi Sanver, William Zwicker.)

Much of my research deals with trying to evaluate the performance of social choice \emph{algorithms} via simulations, which requires appropriate \emph{inputs} and \emph{quality measures}. All three areas offer substantial scope for improvement in the coming years. For concreteness and because of my own limited experience, I focus on the allocation of indivisible goods and on voting, although many of the ideas are more broadly applicable.

Multi-district preference modelling
(with Geoffrey Pritchard), 14pp, submitted.

Generating realistic artificial preference distributions is an important part of any simulation analysis of electoral systems. While this has been discussed in some detail in the context of a single electoral district, many electoral systems of interest are based on districts. Neither treating preferences between districts as independent nor ignoring the district structure yields satisfactory results. We present a model based on an extension of the classic Eggenberger-P\'{o}lya urn, in which each district is represented by an urn and there is correlation between urns. We show in detail that this procedure has a small number of tunable parameters, is computationally efficient, and produces ``realistic-looking" distributions. We present applications to retrospective analysis and forecasting of real elections, and intend to use the methodology to help set optimal parameters for electoral systems.

New algorithms for matching problems
(with Jacky Lo), 19pp, preprint.

The standard two-sided and one-sided matching problems, and the closely related school choice problem, have been widely studied from an axiomatic viewpoint. A small number of algorithms dominate the literature. For two-sided matching, the Gale-Shapley algorithm; for one-sided matching, (random) Serial Dictatorship and Probabilistic Serial rule; for school choice, Gale-Shapley and the Boston mechanisms. The main reason for the dominance of these algorithms is their good (worst-case) axiomatic behaviour with respect to notions of efficiency and strategyproofness. However if we shift the focus to fairness, social welfare, tradeoffs between incompatible axioms, and average-case analysis, it is far from clear that these algorithms are optimal. We investigate new algorithms several of which have not appeared (to our knowledge) in the literature before. We give a unified presentation in which algorithms for 2-sided matching yield 1-sided matching algorithms in a systematic way. In addition to axiomatic properties, we investigate agent welfare using both theoretical and computational approaches. We find that some of the new algorithms are worthy of consideration for certain applications. In particular, when considering welfare under truthful preferences, some of the new algorithms outperform the classic ones.

An exact method for computing the frustration index in signed networks using binary programming
(with Samin Aref and Andrew J. Mason), 20pp, submitted.

Computing the frustration index of a signed graph is a key step toward solving problems in many fields including social networks, physics, material science, and biology. The frustration index determines the distance of a network from a state of total structural balance. Although the definition of the frustration index goes back to 1960, its exact algorithmic computation, which is closely related to classic NP-hard graph problems, has only become a focus in recent years. We develop three new binary linear programming models to compute the frustration index exactly and efficiently as the solution to a global optimisation problem. Solving the models with prioritised branching and valid inequalities in Gurobi, we can compute the frustration index of real signed networks with over 15000 edges in less than a minute on inexpensive hardware. We provide extensive performance analysis for both random and real signed networks and show that our models outperform all existing approaches by large factors. Based on solve time, algorithm output, and effective branching factor we highlight the superiority of our models to both exact and heuristic methods in the literature.

Computing the Line Index of Balance Using Integer Programming Optimisation
(with Samin Aref and Andrew J. Mason), Graphs' Optimization Problems and Their Computational Complexities (G. Gutin 60th birthday special volume) Springer 2018.

An important measure of signed graphs is the line index of balance which has several applications in many fields. However, this graph-theoretic measure was underused for decades because of the inherent complexity in its computation which is closely related to solving NP-hard graph optimisation problems like MAXCUT. We develop new quadratic and linear programming models to compute the line index of balance exactly. Using the Gurobi integer programming optimisation solver, we evaluate the line index of balance on real-world and synthetic datasets. The synthetic data involves Erd\H{o}s-R\'{e}nyi graphs, Barab\'{a}si-Albert graphs, and specially structured random graphs. We also use well known datasets from the sociology literature, such as signed graphs inferred from students' choice and rejection as well as datasets from the biology literature including gene regulatory networks. The results show that exact values of the line index of balance in relatively large signed graphs can be efficiently computed using our suggested optimisation models. We find that most real-world social networks and some biological networks have small line index of balance which indicates that they are close to balanced.

Manipulation of consular election rules
(with Egor Ianovski), Social Choice and Welfare 52, 363-393, 2019.

The Gibbard-Satterthwaite theorem is a cornerstone of social choice theory, stating that an onto social choice function cannot be both strategy-proof and non-dictatorial if the number of alternatives is at least three. The Duggan-Schwartz theorem proves an analogue in the case of set-valued elections: if the function is onto with respect to singletons, and can be manipulated by neither an optimist nor a pessimist, it must have a weak dictator. However, the assumption that the function is onto with respect to singletons makes the Duggan-Schwartz theorem inapplicable to elections which necessarily select a committee with multiple members. In this paper we make a start on this problem by considering elections which elect a committee of size two (such as the consulship of ancient Rome). We establish that if such a \emph{consular election rule} cannot be expressed as the union of two disjoint social choice functions, then strategy-proofness implies the existence of a dictator. Although we suspect that a similar result holds for larger sized committees, there appear to be many obstacles to proving it, which we discuss in detail.

Structural Analysis of Legislation Networks
(with Neda Sakhaee and Golbon Zakeri), 4pp, Proceedings of JURIX2016.

This paper concerns the recently introduced concept of Legislation Networks, with an application focus on the New Zealand legislation network. Legislation networks have some novel features which make them an excellent test case for new network science tools. They involve legal documents, but differ substantially from citation networks involving case-law, Supreme Court opinions, etc. We develop several such networks, compute relevant centrality measures, and apply community detection algorithms. We study the relationship between the legislation network measures and legal/political factors. The intention is to follow-up with more detailed studies in network science (link prediction, node attribute prediction, generative models and time evolution) and legal and political analyses.

Average-case analysis of random assignment algorithms
(with Jacky Lo), 15pp, submitted.

The problem of one-sided matching without money (also known as house allocation), namely computing a bijection from a finite set of items to a finite set of agents each of whom has a strict preference order over the items, has been much studied. Symmetry considerations require the use of randomization, yielding the more general notion of random assignment. The two most commonly studied algorithms (Random Serial Dictatorship (RP) and Probabilistic Serial Rule (PS)) dominate the literature on random assignments. One feature of our work is the inclusion of several new algorithms for the problem. We adopt an average-case viewpoint: although these algorithms do not have the axiomatic properties of PS and RP, they are computationally efficient and perform well on random data, at least in the case of sincere preferences. We perform a thorough comparison of the algorithms, using several standard probability distributions on ordinal preferences and measures of fairness, efficiency and social welfare. We find that there are important differences in performance between the known algorithms. In particular, our lesser-known algorithms yield better overall welfare than PS and RP and better efficiency than RP, with small negative consequences for envy, and are computationally efficient. Thus provided that worst-case and strategic concerns are relatively unimportant, the new algorithms should be seriously considered for use in applications.

Distance rationalization of social rules
(with Benjamin Hadjibeyli), 20pp, submitted.

The concept of distance rationalizability of social choice rules has been explored in recent years by several authors. We deal here with several foundational questions, and unify, correct, and generalize previous work. For example, we study a new question involving uniqueness of representation in the distance rationalizability framework, and present a counterexample. For rules satisfying various axiomatic properties such as anonymity, neutrality and homogeneity, the standard profile representation of input can be compressed substantially. We explain in detail using quotient constructions how distance rationalizability is interpreted in this situation. This enables us to connect the theory of distance rationalizability with geometric concepts such as Earth Mover distance and optimal transportation. We give improved sufficient conditions for distance rationalizable rules to satisfy anonymity, neutrality, homogeneity, consistency and continuity.

Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behavior
(with Stephen Melczer), 30pp, submitted.

We consider the enumeration of walks on the non-negative lattice $\mathbb{N}^d$, with steps defined by a set $\mathcal{S} \subset \{-1, 0, 1\}^d \setminus \{\mathbf{0}\}$. Previous work in this area has established asymptotics for the number of walks in certain families of models by applying the techniques of analytic combinatorics in several variables (ACSV), where one encodes the generating function of a lattice path model as the diagonal of a multivariate rational function. Melczer and Mishna obtained asymptotics when the set of steps $\mathcal{S}$ is symmetric over every axis; in this setting one can always apply the methods of ACSV to a multivariate rational function whose whose set of singularities is a smooth manifold (the simplest case). Here we go further, providing asymptotics for models with generating functions that must be encoded by multivariate rational functions with non-smooth singular sets. In the process, our analysis connects past work to deeper structural results in the theory of analytic combinatorics in several variables. One application is a closed form for asymptotics of models defined by step sets which are symmetric over all but one axis. As a special case, we apply our results when $d=2$ to give a rigorous proof of asymptotics conjectured by Bostan and Kauers; asymptotics for walks returning to boundary axes and the origin are also given.

FPSAC 2016 conference paper

Measuring Partial Balance in Signed Networks
(with Samin Aref), Journal of Complex Networks 6, 566–595, 2018.

Is the enemy of an enemy necessarily a friend, or a friend of a friend a friend? If not, to what extent does this tend to hold? Such questions were formulated in terms of signed (social) networks and necessary and sufficient conditions for a network to be “balanced" were obtained around 1960. Since then the idea that signed networks tend over time to become more balanced has been widely used in several application areas, such as international relations. However investigation of this hypothesis has been complicated by the lack of a standard measure of partial balance, since complete balance is almost never achieved in practice. We formalise the concept of a measure of partial balance, compare several known measures on real-world and synthetic datasets, as well as investigating their axiomatic properties. We use both well-known datasets from the sociology literature, such as Read’s New Guinean tribes, and much more recent ones involving senate bill co-sponsorship. The synthetic data involves both Erdos-Renyi and Barabasi-Albert graphs. We find that under all our measures, real-world networks are more balanced than random networks. We also show that some measures behave better than others in terms of axioms. We make some recommendations for measures to be used in future work. `

Networked crowds answer tricky questions poorly
(with Patrick Girard and Valery Pavlov),8pp, preprint.

We focus on the following basic group decision situation, which we call \emph{iterative distributed jury} (IDJ), a variant of the \emph{Delphi technique}. Group members seek to answer truthfully a question having a well-defined objectively correct answer; they revise answers iteratively; only summary feedback on group members' answers is available at each iteration; individual estimates are aggregated to form a group answer. Experimental studies of the effectiveness of Delphi-like methods have yielded mixed results. To investigate further, we designed a laboratory multiple choice IDJ experiment having some novel features. One novelty was that we incentivized participants to reveal their ignorance; another is the use of both \emph{logical} and \emph{factual} questions. Because of this we can observe the contributions to the wisdom of the crowd of all three groups composing it, roughly speaking: those who know, those who know that they don't know, and those who don't know that they don't know. Another novelty is that the tasks faced by experimental participants included both \emph{logical} and \emph{factual} questions. We find that, perhaps surprisingly, substantial social influence occurs even in this highly anonymized and information-restricted setting, and even for purely logical questions. Eventual group accuracy is strongly dependent on the \emph{trickiness} (likelihood of being answered confidently but wrongly, a concept distinct from \emph{difficulty}) of the question. Also, the bulk of learning occurs by those who were willing to admit to being undecided. We find that question factors are more important than participant characteristics.

Belief diffusion in social networks

Distance rationalization of anonymous and homogeneous voting rules
(with Benjamin Hadjibeyli), Social Choice and Welfare 52, 559-583, 2019.
The concept of distance rationalizability of voting rules has been explored in recent years by several authors. Most previous work has dealt with a definition in terms of preference profiles. However, most voting rules in common use are anonymous and homogeneous. In this case there is a much more succinct representation (using the voting simplex) of the inputs to the rule. This representation has been widely used in the voting literature, but rarely in the context of distance rationalizability. Recently, the present authors showed, as a special case of general results on quotient spaces, exactly how to connect distance rationalizability on profiles for anonymous and homogeneous rules to geometry in the simplex. In this article we develop the connection for the important special case of votewise distances, recently introduced and studied by Elkind, Faliszewski and Slinko in several papers. This yields a direct interpretation in terms of well-developed mathematical topics not seen before in the voting literature, namely Kantorovich (also called Wasserstein) distances and the geometry of Minkowski spaces. As an application of this approach, we prove some positive and some negative results about the decisiveness of distance rationalizable anonymous and homogeneous rules. The positive results connect with the recent theory of hyperplane rules, while the negative ones deal with distances that are not metrics, controversial notions of consensus, and the fact that the $\ell^1$-norm is not strictly convex. We expect that the above novel geometric interpretation will aid the analysis of rules defined by votewise distances, and the discovery of new rules with desirable properties.
Iterated regret minimization in voting games
(with Miranda Emery), Proceedings of COMSOC 2014 (12pp).
The game-theoretic solution concept Iterated Regret Minimization (IRM) was in- troduced recently by Halpern and Pass. We give the first application of IRM to simultaneous voting games. We study positional scoring rules in detail and give theoretical results demonstrating the bias of IRM toward sincere voting. We present comprehensive simulation results of the effect on social welfare of IRM compared to both sincere and optimal voting. The results fit into a broader research theme of the welfare consequences of strategic voting.
Congruence successions in compositions
(with Toufik Mansour and Mark Shattuck), Discrete Mathematics and Theoretical Computer Science 16, 327-338, 2014.
A \emph{composition} is a sequence of positive integers, called \emph{parts}, having a fixed sum. By an \emph{$m$-congruence succession}, we will mean a pair of adjacent parts $x$ and $y$ within a composition such that $x\equiv y~(\text{mod}~m)$. Here, we consider the problem of counting the compositions of size $n$ according to the number of $m$-congruence successions, extending recent results concerning successions on subsets and permutations. A general formula is obtained, which reduces in the limiting case to the known generating function formula for the number of Carlitz compositions. Special attention is paid to the case $m=2$, where further enumerative results may be obtained by means of combinatorial arguments. Finally, an asymptotic estimate is provided for the number of compositions of size $n$ having no $m$-congruence successions.
Diagonal asymptotics for products of combinatorial classes,
Combinatorics, Probability and Computing 24, 354-372, 2015.
We generalize and improve recent results by B\'{o}na and Knopfmacher and by Banderier and Hitczenko concerning the joint distribution of the sum and number of parts in tuples of restricted compositions. Specifically, we generalize the problem to general combinatorial classes and relax the requirement that the sizes of the compositions be equal. We extend the main explicit results to enumeration problems whose counting sequences are Riordan arrays. In this framework, we give an alternative method for computing asymptotics in the supercritical case of Flajolet and Sedgewick, avoiding explicit diagonal extraction. We claim that this method is more computationally efficient.
Analytic Combinatorics in Several Variables
(with Robin Pemantle) Cambridge University Press, 2013
Simulating the 2011 referendum in New Zealand
(with Geoffrey Pritchard), Parliamentary Affairs 67, 969-980, 2014.
On 26 November 2011, an indicative referendum was held in New Zealand with the aim of gauging public support for a change from the current parliamentary electoral system (Mixed Member Proportional) to one of four alternatives. In order to understand the consequences (in terms of the seat distribution of parties in Parliament) of a change in electoral system, we created an online simulator several months before the referendum date. Several interesting research issues arose in this work, which in our opinion deserve greater analysis. We describe the assumptions made in order to create such a simulator, and their consequences.
Best reply dynamics for scoring rules
(with Reyhaneh Reyhani), Proceedings of ECAI 2012, 627-677, 2012.
We consider best-reply dynamics for voting games in which all players are strategic and no coalitions are formed. We study the class of scoring rules, show convergence of a suitably restricted version for the plurality and veto rules, and failure of convergence for other rules including $k$-approval and Borda. In particular, for 3 candidates convergence fails for all rules other than plurality and veto. We give a unified proof for the convergence of these two rules. Our proofs in the case of plurality improve the known bound on convergence, and the other convergence results are new.
Power measures derived from the sequential query process
(with Geoffrey Pritchard and Reyhaneh Reyhani), Mathematical Social Sciences 65, 174-180, 2013.
We study a basic sequential model for the discovery of winning coalitions in a simple game, well known from its use in defining the Shapley-Shubik power index. We derive in a uniform way a family of measures of collective and individual power in simple games, and show that, as for the Shapley-Shubik index, they extend naturally to measures for TU-games. In particular, the individual measures include all weighted semivalues.
We single out the simplest measure in our family for more investigation, as it is new to the literature as far as we know. Although it is very different from the Shapley value, it is closely related in several ways, and is the natural analogue of the Shapley value under a nonstandard, but natural, definition of simple game. We illustrate this new measure by calculating its values on some standard examples.
This is one of 3 papers stemming from a rewriting of a previously submitted draft, A new measure of the manipulability of voting rules.
The Complexity of Safe Manipulation under Scoring Rules
(with Egor Ianovski, Lan Yu, Edith Elkind), Proceedings of IJCAI 2011, 246-251, 2011.
Slinko and White have recently introduced a new model of coalitional manipulation of voting rules under limited communication, which they call ``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 multivariate generating functions: improvements for multiple points
(with Alexander Raichev), Online Journal of Analytic Combinatorics 2011 (25pp).
Let $F(x)= \sum_{\nu\in\mathbb{N}^d} F_\nu x_1^{\nu_1}\cdots x_d^{\nu_d}$ be a power series with complex coefficients that converges in a neighborhood of the origin. Assume $F=G/H$ for some functions $G$ and $H$ holomorphic in a neighborhood of the origin. For example, $F$ could be a rational combinatorial generating function. We derive asymptotics for the ray coefficients $F_{n \alpha}$ as $n\to\infty$ for $\alpha$ in some subset of $d$-tuples of positive integers. More specifically, we give an algorithm for computing arbitrary terms of the asymptotic expansion for $F_{n\alpha}$ when the asymptotics are controlled by a transverse multiple point of the analytic variety $H = 0$ of degree $r \ge 1$. We have implemented our algorithm in Sage and apply it to several examples. This improves upon earlier work on analytic combinatorics in several variables by R. Pemantle and M. C. Wilson.
An interesting new Mahonian permutation statistic,
Electronic Journal of Combinatorics 17, R147 (10 pages), 2010.
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.
Coordination via Polling in Plurality Voting Games under Inertia
(with Reyhaneh Reyhani and Javad Khazaei), Proceedings of COMSOC 2012.
We discuss a general model for strategic voting in plurality elections under uncertainty, using the concept of inertia to deal with information and risk attitude of agents. The model is flexible enough to be used for human societies and artificially designed multiagent systems. Under some further assumptions we show that a sequence of pre-election polls can help agents to coordinate on an equilibrium outcome. This mechanism is closely related to the STV voting rule and gives insight into the political science principle known as Duverger's law.
The probability of safe manipulation
(with Reyhaneh Reyhani), Proceedings of COMSOC 2010.
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.
Asymptotic expansions of oscillatory integrals with complex phase
(with Robin Pemantle), Contemporary Mathematics 520, American Mathematical Society, 2010.
We consider saddle point integrals in d variables whose phase function is neither real nor purely imaginary. Results analogous to those for Laplace (real phase) and Fourier (imaginary phase) integrals hold whenever the phase function is analytic and nondegenerate. These results generalize what is well known for integrals of Laplace and Fourier type. The method is via contour shifting in complex d-space. This work is motivated by applications to asymptotic enumeration.
Asymptotics of coefficients of multivariate generating functions: improvements for smooth points
(with Alexander Raichev), Electronic Journal of Combinatorics, 15, R90, 2008.
This improves on the first Pemantle-Wilson paper in several ways. It derives complete explicit asymptotic expansions controlled by smooth points. Numerical examples show the efficacy of this method. There are accompanying Maple worksheets.
Asymptotics of the minimum manipulating coalition size for positional voting rules under IC behaviour
(with Geoffrey Pritchard), Mathematical Social Sciences 58, 35-56, 2009.
We consider the problem of manipulation of elections using positional voting rules under Impartial Culture voter behaviour. We consider both the logical possibility of coalitional manipulation, and the number of voters that must be recruited to form a manipulating coalition. It is shown that the manipulation problem may be well approximated by a very simple linear program in two variables. This permits a comparative analysis of the asymptotic (large-population) manipulability of the various rules. It is seen that the manipulation resistance of positional rules with 5 or 6 (or more) candidates is quite different from the more commonly analyzed 3- and 4-candidate cases.
A new method for computing asymptotics of diagonal coefficients of multivariate generating functions
(with Alexander Raichev), Proceedings of the International Conference on Analysis of Algorithms (Juan-les-Pins, June 2007)
Let $\sum_{\nvec\in\nats^d} f_\nvec \xvec^\nvec$ be a multivariate generating function that converges in a neighborhood of the origin of $\comps^d$. We present a new, multivariate method for computing the asymptotics of the diagonal coefficients $f_{a_1n,\ldots,a_dn}$ and show its superiority over the standard, univariate diagonal method.
Random and exhaustive generation of permutations and cycles
Annals of Combinatorics 12, 509-520, 2009.
In 1986 S. Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a fixed number of symbols. This algorithm is very similar to the standard method for generating a random permutation, but is less well known.
We consider both methods in a unified way, and discuss their relation with exhaustive generation methods. We analyse several random variables associated with the algorithms and find their grand probability generating functions, which gives easy access to moments and limit laws.
Longest alternating subsequences in pattern-restricted permutations
(with Ghassan Firro and Toufik Mansour) Electronic Journal of Combinatorics 14, R34 (11 pages), 2007.
Inspired by the results of Stanley and Widom concerning the limiting distribution of the lengths of longest alternating subsequences in random permutations, and results of Deutsch, Hildebrand and Wilf on the limiting distribution of the longest increasing subsequence for pattern-restricted permutations, we find the limiting distribution of the longest alternating subsequence for pattern-restricted permutations in which the pattern is any one of the six patterns of length three. Our methodology uses recurrences, generating functions, and complex analysis, and also yields more detailed information. Several ideas for future research are listed.
The diameter of random Cayley digraphs of given degree
(with Manuel Lladser, Primoz Potocnik, Jozef Siran) Discrete Mathematics and Theoretical Computer Science 14, 83-90, 2012.
We consider random Cayley digraphs of order $n$ with uniformly distributed generating sets of size $k$. Specifically, we are interested in the asymptotics of the probability that such a Cayley digraph has diameter two as $n\to\infty$ and $k=f(n)$, focusing on the functions $f(n)=\lfloor cn\rfloor$ and $f(n)= \lfloor n^{\delta} \rfloor$. In both instances we show that the probability converges to $1$ as $n\to\infty$, for any fixed $c\in (0,1/2)$ and any fixed $\delta\in (1/2,1)$, respectively. We obtain sharper results for Abelian groups. The proofs use detailed asymptotic analysis in several regimes of the combinatorial function $a(n,k,t)$, equal to the number of ways of choosing a subset of size $k$ from a set of size $n$ while not choosing any of $t$ preassigned disjoint pairs.
This paper went through several revisions and Jana Siagova withdrew as an author. I will keep the original here for now --- the published version is Open Access.
Probability calculations under the IAC hypothesis
(with G. Pritchard) Mathematical Social Sciences 54, 244-256, 2007.
We show how powerful algorithms recently developed for counting lattice points and computing volumes of convex polyhedra can be used to compute probabilities of a wide variety of events of interest in social choice theory. Several illustrative examples are given.
Exact results on manipulability of positional voting rules
(with G. Pritchard) Social Choice and Welfare 29, 487-513, 2007.
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
(with R. Pemantle) SIAM Review 50, 199--272, 2008.
Let $F$ be a power series in at least two variables that defines a meromorphic function in a neighbourhood of the origin; for example, $F$ may be a rational multivariate generating function. We discuss recent results that allow the effective computation of asymptotic expansions for the coefficients of $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.
Note: there are some (minor) computational errors in the examples. A range of Maple worksheets accompanying the paper is available.
Asymptotics for generalized Riordan arrays
Discrete Mathematics and Theoretical Computer Science, volume AD, 323-334, 2005. (Proceedings of the 2005 International Conference on Analysis of Algorithms, Barcelona).
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.
Probability generating functions for Sattolo's algorithm
Journal of the Iranian Statistical Society 3, 297-308, 2004 (special issue on probabilistic analysis of algorithms).
In 1986 S. Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a fixed number of symbols. Recently H. Prodinger analysed two important random variables associated with the algorithm, and found their mean and variance. H. Mahmoud extended Prodinger's analysis by finding limit laws for the same two random variables.
The present article, starting from the definition of the algorithm, is completely self-contained. After giving a simple new proof of correctness, we generalize the abovementioned probabilistic results by determining the ``grand" probability generating functions of the random variables.
The focus throughout is on using standard methods that give a unified approach, and open the door to further study.
Asymptotics of multivariate sequences, part II: multiple points of the singular variety
(with R. Pemantle) Combinatorics, Probability and Computing 13, 735-761, 2004.
Let $F(\b{z})=\sum_\b{r} a_\b{r}\b{z^r}$ be a multivariate generating function which is meromorphic in some neighborhood of the origin of $\mathbb{C}^d$, and let $\sing$ be its set of singularities. Effective asymptotic expansions for the coefficients can be obtained by complex contour integration near points of $\sing$.
In the first article in this series, we treated the case of smooth points of $\sing$. In this article we deal with multiple points of $\sing$.
Asymptotics of multivariate sequences, part I: smooth points of the singular variety
(with R. Pemantle) Journal of Combinatorial Theory Series A 97, 129--161, 2002.
Given a multivariate generating function $F(z_1 , \ldots , z_d) = \sum a_{r_1 , \ldots , r_d} z_1^{r_1} \cdots z_d^{r_d}$, we determine asymptotics for the coefficients. Our approach is to use Cauchy's integral formula near singular points of $F$, resulting in a tractable oscillating integral. This paper treats the case where the singular point of $F$ is a smooth point of a surface of poles. Companion papers will treat singular points of $F$ where the local geometry is more complicated, and for which other methods of analysis are not known.
X-inner automorphisms of semicommutative quantum algebras
(with J. Bergen) Journal of Algebra 220, 152-173, 1999. MR 2001a:16057.
Many important quantum algebras such as quantum symplectic space, quantum euclidean space, quantum matrices, $q$-analogs of the Heisenberg algebra and the quantum Weyl algebra are semi-commutative. In addition, enveloping algebras $U(L_+)$ of even Lie color algebras are also semi-commutative. In this paper, we generalize work of Montgomery and examine the X-inner automorphisms of such algebras.
The theorems and examples in our paper show that for algebras $R$ of this type, the non-identity X-inner automorphisms of $R$ tend to have infinite order. Thus if $G$ is a finite group of automorphisms of $R$, then the action of $G$ will be X-outer and this immediately gives useful information about crossed products $R*_t G$.
Degree- and time-constrained broadcast networks
(with M. J. Dinneen and G. Pritchard) Networks 39, 1--9, 2002.
We consider the problem of constructing networks with as many nodes as possible, subject to upper bounds on the degree and broadcast time. The paper includes the results of an extensive empirical study of broadcasting in small regular graphs using a stochastic search algorithm to approximate the broadcast time. Significant improvements on known results are obtained for cubic broadcast networks.
Group algebras and enveloping algebras with nonmatrix and semigroup identities
(with D. M. Riley) Communications in Algebra 27, 3545-3556, 1999. MR 2000c:16032.
Let $K$ be a field of characteristic $p>0$. Denote by $\omega(R)$ the augmentation ideal of either a group algebra $R=K[G]$ or a restricted enveloping algebra $R=u(L)$ over $K$. We first characterize those $R$ for which $\omega(R)$ satisfies a polynomial identity not satisfied by the algebra of all $2\times 2$ matrices over $K$. Then, we examine those $R$ for which $\omega(R)$ satisfies a semigroup identity (that is, a polynomial identity which can be written as the difference of two monomials).
Associative algebras satisfying a semigroup identity
(with D.M. Riley) Glasgow Mathematical Journal 41, 453-462, 1999. MR 2000j:16037.
Denote by $(R,\cdot)$ the multiplicative semigroup of an associative algebra $R$ over an infinite field, and let $(R,\circ)$ represent $R$ when viewed as a semigroup via the circle operation $x\circ y=x+y+xy$. In this paper we characterize the existence of an identity in these semigroups in terms of the Lie structure of $R$. Namely, we prove that the following conditions on $R$ are equivalent: the semigroup $(R,\circ)$ satisfies an identity; the semigroup $(R,\cdot)$ satisfies a reduced identity; and, the associated Lie algebra of $R$ satisfies the Engel condition. When $R$ is finitely generated these conditions are each equivalent to $R$ being upper Lie nilpotent.
Associative rings satisfying the Engel condition
(with D.M. Riley) Proceedings of the American Mathematical Society 127, 973-976, 1999. MR 99f:16025.
Let $C$ be a commutative ring, and let $R$ be an associative $C$-algebra generated by elements $\{x_1,\ldots,x_d\}$. We show that if $R$ satisfies the Engel condition of degree $n$ then $R$ is nilpotent as a Lie algebra of class bounded by a function that depends only on $d$ and $n$. We deduce that the Engel condition in an arbitrary associative ring is inherited by its group of units, and implies a semigroup identity.
Construction of time-relaxed minimal broadcast networks
(with M. J. Dinneen, J. A. Ventura and G. Zakeri) Parallel Processing Letters 9, 53-68, 1999. MR 2000g:68014.
In broadcasting, or one-to-all communication, a message originally held in one node of the network must be transmitted to all the other nodes. A minimal broadcast network is a communication network that can transmit a message originated at any node to all other nodes of the network in minimum time. In this paper, we present a compound method to construct sparse, time-relaxed, minimal broadcast networks ($t$-mbn), in which broadcasting can be accomplished in slightly more than the minimum time. The proposed method generates a new network by connecting a subset of nodes from several copies of a $t_1$-mbn using the structure of another $t_2$-mbn. The objective is to construct a network as sparse as possible satisfying the desired broadcasting time constraint. Computational results illustrate the effectiveness of the proposed method.
Compound constructions of broadcast networks
(with M. J. Dinneen, J. A. Ventura and G. Zakeri) Discrete Applied Mathematics 93, 205-232, 1999. MR 2000f:90008.
Compound methods have been shown to be very effective in the construction of minimal broadcast networks (mbns). Compound methods generate a large mbn by combining multiple copies of an mbn $G$ using the structure of another mbn $H$. Node deletion is also allowed in some of these methods. The subset of connecting nodes of $G$ has been defined as solid $h$-cover by Bermond, Fraigniaud and Peters, and center node set by Weng and Ventura. This article shows that the two concepts are equivalent. We also provide new properties for center node sets, including bounds on the minimum size of a center node set, show how to reduce the number of center nodes of an mbn generated by a compound method, and propose an iterative compounding algorithm that generates the sparsest known mbns in many cases.
Primeness of the enveloping algebra of the special Lie superalgebras
(with Geoffrey Pritchard) Archiv der Mathematik 70, 187-196,1998. MR 98m:17019.
A primeness criterion due to Bell is shown to apply to the universal enveloping algebra of the Cartan type Lie superalgebras $S(V)$ and $\widetilde{S}(V;t)$ when $\dim V$ is even.
Bell's primeness criterion and the simple Lie superalgebras
Journal of Pure and Applied Algebra 133, 241-260, 1998.
We determine all finite-dimensional simple Lie superalgebras $L$ such that $U(L)$ satisfies a primeness criterion due to Bell. Some open problems related to primeness of enveloping algebras are listed.
Bell's primeness criterion for $W(2n+1)$ (with Geoffrey Pritchard and David H. Wood)
Experimental Mathematics 6, 77-85, 1997. MR 98k:17014.
On the basis of experimental work involving matrix computations, we conjecture that a criterion due to Bell for primeness of the universal enveloping algebra of a Lie superalgebra applies to the Cartan type Lie superalgebras $W(n)$ for $n=3$ but does not apply for odd $n\geq 5$. The experiments lead to a rigorous proof, which we present.
Primeness of the enveloping algebra of Hamiltonian superalgebras
Bulletin of the Australian Mathematical Society 56, 483-488, 1997. MR 98m:17018.
In 1990 Allen Bell presented a sufficient condition for the primeness of the universal enveloping algebra of a Lie superalgebra. Let $Q$ be a nonsingular bilinear form on a finite-dimensional vector space over a field of characteristic zero. In this paper we show that Bell's criterion applies to the Hamiltonian Cartan type superalgebras determined by $Q$, and hence obtain some new prime noetherian rings.
Crossed products of restricted enveloping algebras
Communications in Algebra 25, 487-496, 1997. MR 97k:17029.
Let $K$ be a field of characteristic $p>0$, let $L$ be a restricted Lie algebra and let $R$ be an associative $K$-algebra. It is shown that the various constructions in the literature of crossed product of $R$ with $u(L)$ are equivalent. We calculate explicit formulae relating the parameters involved and obtain a formula which hints at a noncommutative version of the Bell polynomials.
Primeness of the enveloping algebra of a Cartan type Lie superalgebra
Proceedings of the American Mathematical Society 124, 383-387, 1996. MR 96d:17011.
We show that a primeness criterion for enveloping algebras of Lie superalgebras discovered by Bell is applicable to the Cartan type Lie superalgebras $W(n)$, $n$ even. Other algebras are considered but there are no definitive answers in these cases.
Delta methods for enveloping algebras of Lie colour algebras
Journal of Algebra 175 (1995), 661-696. MR 97a:17013.
In recent papers J. Bergen and D.S. Passman have applied so-called `Delta methods' to enveloping algebras of Lie superalgebras. This paper generalizes their results to the class of Lie colour algebras. The methods and results in this paper are very similar to those of Bergen and Passman, and many of their proofs generalize easily. However, at some points there are serious difficulties to overcome. The results obtained show that if $L$ is a Lie colour algebra then the join of all finite-dimensional ideals of $L$ controls certain properties of the universal enveloping algebras $U(L)$. Specifically, we consider primeness, semiprimeness, constants, semi-invariants, almost constants, faithfulness of the adjoint action, the centre, almost centralizers and the central closure.

Nonacademic applications of my research

Submission to the Electoral Commission on the MMP Review Proposals Paper (with Michael Fowlie), 2012.
This reports on simulation work that casts some doubt on the EC's recommendation of a 4\% threshold for MMP. We find that it should be lower. This submission was included in full in the Commission's final report.

Professional articles

Reviews of others' work

Mathematical Reviews (subscription required) (since 1999)
Review of "Hodge and Klima, The Mathematics of Voting and Elections: A Hands-On Approach" (ACM SIGACT News)
Review of "Gillman and Housman, Models of Conflict and Cooperation" (ACM SIGACT News)

NZ Mathematical Society columns

I have been writing a column called Cybermath for the NZ Mathematical Society Newsletter since issue 118 (excepting issue 122). Topics relate to mathematics in the internet age, with a lot of emphasis on publication reform. All issues of the Newsletter are available here: http://nzmathsoc.org.nz/?newsletter
Topics covered so far include: new peer review methods, new mathematical results, reliability of literature, plagiarism, citation metrics, preprint servers, open access journals, journal prices, blogs and videos, arXiv overlay journals, international opinion survey on publishing reform, Free Journal Network.

Publishing reform

Feedback to Coalition S on Plan S implementation guidelines. With J. Tennant, D. Zaitsev, C. Gogolin. 2019-02-05.
Free and fair journals: flipping, fostering, founding.
Notices of the American Mathematical Society, 2018-08.
Introducing the Free Journal Network – community-controlled open access publishing
LSE Impact of Social Sciences blog, 2018-06-20.
Universities spend millions on accessing results of publicly funded research
The Conversation, 2017-12-12.
Fair Open Access Principles for Journals
(with Alex Holcombe), AOASG blog 2017-06-23.
Results of a worldwide survey of mathematicians on journal reform
(with Cameron Neylon and David Michael Roberts), Newsletter of the European Mathematical Society March 2017, 46-49.
What do mathematicians think of their journals?
Impact of Social Sciences blog, 2016-06-22.
Market failure in the research world (Speaker column for Public Address, November 2014)
The Elsevier boycott and beyond (guest editorial for NZMS Newsletter 114, April 2012)

Other

Submission to the Tertiary Education Commission (with Richard Easther, Michelle Elleray, Jolisa Gracewood, Amanda Peet, Alice TePunga Somerville), June 2000.

Last updated: 2019-05-15.