Rational generating functions and integer programming games

DOI10.1287/OPRE.1110.0964MaRDI QIDQ2893918zbMATH OpenOpenAlexFDO

Authors Matthias Köppe, Christopher Thomas Ryan, Maurice Queyranne

Publication date 26 June 2012

Published in Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic game theoryBarvinok's generating functionsinteger programmingpure Nash equilibriaStackelberg-Nash games

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Convex functions and convex programs in convex geometry (52A41) Integer programming (90C10) Hierarchical games (including Stackelberg games) (91A65)

Abstract: We explore the computational complexity of computing pure Nash equilibria for a new class of strategic games called integer programming games with difference of piecewise linear convex 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.

Recommendations

• Rational convex programs and efficient algorithms for 2-player Nash and nonsymmetric bargaining games
• Enumeration of Nash equilibria for two-player games
• The complexity of pure Nash equilibria
• scientific article; zbMATH DE number 2243403
• A mixed 0-1 linear programming approach to the computation of all pure-strategy Nash equilibria of a finite \(n\)-person game in normal form

Cited in

(12)

• Computing equilibria for integer programming games
• Optimizing over pure stationary equilibria in consensus stopping games
• The noncooperative fixed charge transportation problem
• Multilinear games
• Nash equilibria in the two-player kidney exchange game
• A branch-and-prune algorithm for discrete Nash equilibrium problems
• Inverse optimization of integer programming games for parameter estimation arising from competitive retail location selection
• The critical node game
• Generalized Nash equilibrium problems with mixed-integer variables
• Last fifty years of integer linear programming: a focus on recent practical advances
• Integration of sales and operations: a dynamic mixed-integer programming game
• Computing approximate Nash equilibria for integer programming games

Describes a project that uses

Uses Software

• LattE

This page was built for publication: Rational generating functions and integer programming games

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