Power measures derived from the sequential query process (with Geoffrey Pritchard and Reyhaneh Reyhani), submitted.
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 IJCAI 2011, 246-251.
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 multivariate generating functions: improvements for multiple points (with Alexander Raichev), to appear in Online Journal of Analytic Combinatorics (25pp).
Let $F(x)= \sum_{\nu\in\nats^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 (2010), R147 (10 pages).
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), submitted, May 2010.
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), accepted by COMSOC 2010, June 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.
Review of "The Mathematics of Voting and Elections: A Hands-On Approach" by Hodge and Klima, SIGACT News 41 (3) (2010), 34-36.
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 (2009),
35-56.
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, (2009), 509-520.
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 (2007), R34 (11 pages).
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, Jana Siagova, Jozef
Siran) submitted (11 pages)
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.
Probability calculations under the IAC
hypothesis
(with G. Pritchard)
Mathematical Social Sciences 54 (2007), 244-256.
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
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
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
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
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 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
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
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
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
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
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
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
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
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
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
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
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)
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
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
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
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 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.
(with G. Pritchard)
Social Choice and Welfare 29 (2007), 487-513.
(with R. Pemantle)
SIAM Review 50 (2008), 199--272.
Discrete Mathematics and Theoretical Computer Science, volume AD (2005), 323-334
(Proceedings of the 2005 International Conference on Analysis of Algorithms,
Barcelona).
Journal of the Iranian Statistical Society 3 (2004), 297-308 (special issue
on probabilistic analysis of algorithms).
(with R. Pemantle)
Combinatorics, Probability and Computing 13 (2004), 735-761.
(with R. Pemantle)
Journal of Combinatorial Theory Series A 97 (2002), 129--161.
(with J. Bergen)
Journal of Algebra 220, (1999), 152-173. MR 2001a:16057.
(with M. J. Dinneen and G. Pritchard)
Networks 39 (2002), 1--9.
(with D. M. Riley)
Communications in Algebra 27 (1999), 3545-3556. MR 2000c:16032.
(with D.M. Riley)
Glasgow Mathematical Journal 41 (1999), 453-462.
MR 2000j:16037.
(with D.M. Riley)
Proceedings of the American Mathematical Society 127 (1999), 973-976.
MR 99f:16025.
(with M. J. Dinneen, J. A. Ventura and G. Zakeri)
Parallel Processing Letters 9 (1999), 53-68. MR 2000g:68014.
(with M. J. Dinneen, J. A. Ventura and G. Zakeri)
Discrete Applied Mathematics 93 (1999), 205-232. MR 2000f:90008.
(with Geoffrey Pritchard)
Archiv der Mathematik 70 (1998), 187-196.
MR 98m:17019.
Journal of Pure and Applied Algebra 133
(1998), 241-260.
Experimental Mathematics 6
(1997), 77-85. MR 98k:17014.
Bulletin of the Australian Mathematical Society 56 (1997), 483-488. MR 98m:17018.
Communications in Algebra 25 (1997), 487-496. MR 97k:17029.
Proceedings of the American Mathematical Society 124 (1996), 383-387.
MR 96d:17011.
Journal of
Algebra 175 (1995), 661-696. MR 97a:17013.
Last updated: 2011-10-03.