research-article

Root counts of semi-mixed systems, and an application to counting nash equilibria

Authors:

Ioannis Z. Emiris,

Raimundas VidunasAuthors Info & Claims

ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

Pages 154 - 161

https://doi.org/10.1145/2608628.2608679

Published: 23 July 2014 Publication History

Abstract

Semi-mixed algebraic systems are those where the equations can be partitioned into subsets with common Newton polytopes. We are interested in counting roots of semi-mixed multihomogeneous systems, where both variables and equations can be partitioned into blocks, and each block of equations has a given degree in each block of variables. The motivating example is counting the number of totally mixed Nash equilibria in games of several players. Firstly, this paper relates and unifies the BKK and multivariate Bézout bounds for semi-mixed systems, through mixed volumes and matrix permanents. Permanent expressions for BKK bounds hold for all multihomogeneous systems, without any requirement of semi-mixed structure, as well as systems whose Newton polytopes are products of polytopes in complementary subspaces. Secondly, by means of a novel asymptotic analysis, the complexity of a combinatorial geometric algorithm for semi-mixed volumes (i.e., mixed volumes of semi-mixed systems) is explored and juxtaposed to the complexities of computing permanents, or using generating functions (via MacMahon's Master theorem), or orthogonal polynomials.

References

[1]

D. N. Bernstein. The number of roots of a system of equations, Functional Anal. Appl., 9:183--185, 1975.

[2]

R. S. Datta. Finding all Nash equilibria of a finite game using polynomial algebra, Econ.Theory, 42:55--96, 2010.

[3]

A. Dickenstein and I. Z. Emiris. Multihomogeneous resultant formulae by means of complexes. J. Symb. Comput., Spec. Issue, 36(3-4):317--342, 2003.

Digital Library

[4]

M. Dyer, P. Gritzmann and A. Hufnagel. On the complexity of computing mixed volumes. SIAM J. Comput., 27(2):356--400, 1998.

Digital Library

[5]

I. Z. Emiris, Sparse elimination and applications in kinematics. PhD Thesis, Computer Science Division, Univ. of California at Berkeley, 1994.

Digital Library

[6]

I. Z. Emiris and J. F. Canny. Efficient incremental algorithm for the sparse resultant and the mixed volume. J. Symb. Comp, 20:117--149, 1995.

Digital Library

[7]

I. Z. Emiris and A. Mantzaflaris. Multihomogeneous resultant matrices for systems with scaled support. J. Symb. Comput., Spec. Issue, 47:820--842, 2012.

Digital Library

[8]

I. Z. Emiris and B. Mourrain. Computer algebra methods for studying and computing molecular conformations. Algorithmica, 25:372--402, 1999.

[9]

S. Even and J. Gillis. Derangements and Laguerre polynomials. Proc. Cambridge Phil. Soc., 79:135--143, 1976.

[10]

D. Foata and D. Zeilberger, Laguerre polynomials, weighted derangements, and positivity. SIAM J. Disc. Math., 1 (1988), pg. 425--433.

Digital Library

[11]

K. Fukuda. From the zonotope construction to the Minkowski addition of convex polytopes. J. Symb. Comput., 38, 2004.

[12]

T. Gao, T. Y. Li. Mixed volume computation for semi-mixed systems. Discr. Comp. Geom., 29:257--277, 2003.

[13]

P. Gritzmann and V. Klee. On the complexity of some basic problems in computational convexity II: volume and mixed volumes, In Polytopes: Abstract, Convex and Computational, pp. 373--466, 1994, Kluwer.

[14]

B. Huber and B. Sturmfels. A polyhedral method for solving sparse polynomial systems. Math. Comp., 64(212): 1542--1555, 1995.

Digital Library

[15]

G. Jeronimo, D. Perrucci, and J. Sabia. A parametric representation of totally mixed Nash equilibria, Comp. & Math. with Applications, 58(6):1126--1141, 2009.

Digital Library

[16]

M. Konvalinka and I. Pak, Noncommutative extensions of MacMahon's Master theorem, Adv. Math., 216:29--61, 2007.

[17]

P. A. MacMahon. Combinatory analysis, Cambridge Univ. Press, 1916.

[18]

A. McLennan. The maximum number of real roots of a multihomogeneous system of polynomial equations, Beitrage zur Algebra und Geom., 40:343--350, 1999.

[19]

R. D. McKelvey and A. McLennan. The maximal number of regular totally mixed Nash equilibria. J. Economic Theory, 72:411--425, 1997.

[20]

T. Mizutani, A. Takeda and M. Kojima. Dynamic enumeration of all mixed cells. Discr. Comp. Geometry, 37(3):351--367, 2007.

Digital Library

[21]

A. P. Morgan, A. J. Sommese and C. W. Wampler. A product-decomposition theorem for bounding Bezout numbers. SIAM J. Num. Anal., 32:1308--1325, 1995.

Digital Library

[22]

N. Nisan et al. (Eds), Algorithmic Game Theory. Cambridge University Press, 2007.

Digital Library

[23]

P. Pedersen. Mixed volume is #P-complete. AMS--SIAM Conference on Continuous Algorithms and Complexity. Mt. Holyoke, Mass., July 1994.

[24]

H. J. Ryser, Combinatorial Mathematics, The Carus Mathematical Monographs #14 (1963), MAA.

[25]

B. Sturmfels and A. Zelevinsky. Multigraded resultants of Sylvester type, J. Algebra, 163:115--127, 1994.

[26]

R. Vidunas. Counting derangements and Nash equilibria, 2014, Preprint, arxiv.org/1401.5400.

[27]

Wikipedia, Permanent is sharp-P-complete and Laguerre polynomials. http://en.wikipedia.org.

[28]

P. M. Vaidya. An algorithm for linear programming which requires O(((m + n)n² + (m + n)^1.5n)L) arithmetic operations. Math. Prog., 47:175--201, 1990.

Digital Library

[29]

J. Verschelde, K. Gatermann, and R. Cools. Mixed volume computation by dynamic lifting applied to polynomial system solving. Discr. Comp. Geom., 16(1):69--112, 1996.

Digital Library

[30]

C. Wenchang. Determinant, permanent, and MacMahon's Master theorem. Lin. Algebra & Appl., 255:171--183, 1997.

Cited By

Bartzos EEmiris ITzamos C(2021)The m-Bézout Bound and Distance GeometryComputer Algebra in Scientific Computing10.1007/978-3-030-85165-1_2(6-20)Online publication date: 16-Aug-2021
https://doi.org/10.1007/978-3-030-85165-1_2
Bartzos EEmiris ISchicho J(2020)On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-020-00447-7Online publication date: 21-Jul-2020
https://doi.org/10.1007/s00200-020-00447-7
Busé LMantzaflaris ATsigaridas E(2019)Matrix formulæ for resultants and discriminants of bivariate tensor-product polynomialsJournal of Symbolic Computation10.1016/j.jsc.2019.07.007Online publication date: Jul-2019
https://doi.org/10.1016/j.jsc.2019.07.007
Show More Cited By

Index Terms

Root counts of semi-mixed systems, and an application to counting nash equilibria

Recommendations

Applications of the Cosecant and Related Numbers

Power series expansions for cosecant and related functions together with a vast number of applications stemming from their coefficients are derived here. The coefficients for the cosecant expansion can be evaluated by using: (1) numerous recurrence ...
Convolutions and zeros of orthogonal polynomials

In an attempt to answer a long standing open question of Al-Salam we generate various beautiful formulae for convolutions of orthogonal polynomials similar toU"n(x)=@?k=0nP"k(x)P"n"-"k(x), where U"n(x) are the Chebyshev polynomials of the second kind ...
A subdivision-based algorithm for the sparse resultant

Multivariate resultants generalize the Sylvester resultant of two polynomials and characterize the solvability of a polynomial system. They also reduce the computation of all common roots to a problem in linear algebra. We propose a determinantal ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

July 2014

444 pages

ISBN:9781450325011

DOI:10.1145/2608628

Editor:
Katsusuke Nabeshima
The University of Tokushima, Japan
,
General Chairs:
Kosaku Nagasaka
Kobe University, Japan
,
Franz Winkler
RISC, University Linz, Austria
,
Program Chair:
Agnes Szanto
North Carolina State University

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Greek National Fund
European Social Fund

Conference

ISSAC '14

ISSAC '14: International Symposium on Symbolic and Algebraic Computation

July 23 - 25, 2014

Kobe, Japan

Acceptance Rates

ISSAC '14 Paper Acceptance Rate 51 of 96 submissions, 53%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
105
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bartzos EEmiris ITzamos C(2021)The m-Bézout Bound and Distance GeometryComputer Algebra in Scientific Computing10.1007/978-3-030-85165-1_2(6-20)Online publication date: 16-Aug-2021
https://doi.org/10.1007/978-3-030-85165-1_2
Bartzos EEmiris ISchicho J(2020)On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-020-00447-7Online publication date: 21-Jul-2020
https://doi.org/10.1007/s00200-020-00447-7
Busé LMantzaflaris ATsigaridas E(2019)Matrix formulæ for resultants and discriminants of bivariate tensor-product polynomialsJournal of Symbolic Computation10.1016/j.jsc.2019.07.007Online publication date: Jul-2019
https://doi.org/10.1016/j.jsc.2019.07.007
Chen T(2019)Unmixing the Mixed Volume ComputationDiscrete & Computational Geometry10.1007/s00454-019-00078-x62:1(55-86)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s00454-019-00078-x
Bender MFaugère JMantzaflaris ATsigaridas EKauers MOvchinnikov ASchost É(2018)Bilinear Systems with Two SupportsProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209011(63-70)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3209011
Duff THill CJensen ALee KLeykin ASommars J(2018)Solving polynomial systems via homotopy continuation and monodromyIMA Journal of Numerical Analysis10.1093/imanum/dry017Online publication date: 13-Apr-2018
https://doi.org/10.1093/imanum/dry017
Mantzaflaris ATsigaridas EYap CEl Din M(2017)Resultants and Discriminants for Bivariate Tensor-Product PolynomialsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087646(309-316)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087646
Malajovich G(2017)Computing Mixed Volume and All Mixed Cells in Quermassintegral TimeFoundations of Computational Mathematics10.1007/s10208-016-9320-117:5(1293-1334)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s10208-016-9320-1
Vidunas R(2017)Counting Derangements and Nash EquilibriaAnnals of Combinatorics10.1007/s00026-017-0344-221:1(131-152)Online publication date: 2-Feb-2017
https://doi.org/10.1007/s00026-017-0344-2
Emiris IAbramov SZima EGao X(2016)Compact Formulae in Sparse EliminationProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930943(1-4)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930943
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten