Rational Generating Functions and Integer Programming Games

Matthias Köppe (), Christopher Thomas Ryan () and Maurice Queyranne ()
Additional contact information
Matthias Köppe: Department of Mathematics, University of California, Davis, Davis, California 95616
Christopher Thomas Ryan: Booth School of Business, University of Chicago, Chicago, Illinois 60637
Maurice Queyranne: Sauder School of Business, University of British Columbia, Vancouver, British Columbia V6T 1Z2, Canada

Operations Research, 2011, vol. 59, issue 6, 1445-1460

Abstract: We explore the computational complexity of computing pure Nash equilibria for a new class of strategic games called integer programming games, with differences of piecewise-linear convex functions as payoffs. Integer programming games are games where players' action sets are integer points inside of polytopes. Using recent results from the study of short rational generating functions for encoding sets of integer points pioneered by Alexander Barvinok, we present efficient algorithms for enumerating all pure Nash equilibria, and other computations of interest, such as the pure price of anarchy and pure threat point, when the dimension and number of “convex” linear pieces in the payoff functions are fixed. Sequential games where a leader is followed by competing followers (a Stackelberg--Nash setting) are also considered.

Keywords: algorithmic game theory; integer programming; Barvinok's generating functions; pure Nash equilibria; Stackelberg--Nash games (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.0964 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:6:p:1445-1460

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().