Counting derangements and Nash equilibria

DOI10.1007/S00026-017-0344-2MaRDI QIDQ521913zbMATH OpenOpenAlexFDO

Authors Raimundas Vidunas

Publication date 12 April 2017

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.5400

zbMATH Keywords

asymptoticsderangementsgame theorygenerating functionMacMahon's master theorem

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Generalized hypergeometric series, ({}_pF_q) (33C20) (n)-person games, (n>2) (91A06)

Abstract: The maximal number of totally mixed Nash equilibria in games of several players equals the number of block derangements, as proved by McKelvey and McLennan.On the other hand, counting the derangements is a well studied problem. The numbers are identified as linearization coefficients for Laguerre polynomials. MacMahon derived a generating function for them as an application of his master theorem. This article relates the algebraic, combinatorial and game-theoretic problems that were not connected before. New recurrence relations, hypergeometric formulas and asymptotics for the derangement counts are derived. An upper bound for the total number of all Nash equilibria is given.

Recommendations

• The maximal number of regular totally mixed Nash equilibria
• A note on the probability of k pure Nash equilibria in matrix games
• Some identities involving derangement polynomials and numbers and moments of gamma random variables
• scientific article; zbMATH DE number 1919530
• An Asymptotic Problem in Derangement Theory

Cites work

• A parametric representation of totally mixed Nash equilibria
• A Product-Decomposition Bound for Bezout Numbers
• Asymptotics of coefficients of multivariate generating functions: Improvements for smooth points
• Asymptotics of Multivariate Sequences II: Multiple Points of the Singular Variety
• Asymptotics of multivariate sequences. I: Smooth points of the singular variety
• Binomial identities -- combinatorial and algorithmic aspects
• Connections between p=x^2+3y^2 and Franel numbers
• Derangements and Laguerre polynomials
• Generic \(4\times 4\) two person games have at most 15 Nash equilibria
• Group theoretical basis for the terminating₃F₂(1) series
• How Joe Gillis discovered combinatorial special function theory
• scientific article; zbMATH DE number 1271722 (Why is no real title available?)
• Laguerre Polynomials, Weighted Derangements, and Positivity
• New maximal numbers of equilibria in bimatrix games
• Root counts of semi-mixed systems, and an application to counting Nash equilibria
• The maximal number of regular totally mixed Nash equilibria
• The number of roots of a system of equations
• The On-Line Encyclopedia of Integer Sequences
• Weighted permutation problems and Laguerre polynomials

Cited in

(3)

• The territorial raider game and graph derangements
• A vector bundle approach to Nash equilibria
• Mixed extensions of generic finite games embedded into products of real projective spaces

Describes a project that uses

Uses Software

• OEIS
• MultiZeilberger

This page was built for publication: Counting derangements and Nash equilibria

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521913)