Computer Science – Computer Science and Game Theory
Scientific paper
2008-09-03
Computer Science
Computer Science and Game Theory
18 pages
Scientific paper
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.
Köppe Matthias
Queyranne Maurice
Ryan Christopher Thomas
No associations
LandOfFree
Rational Generating Functions and Integer Programming Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rational Generating Functions and Integer Programming Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rational Generating Functions and Integer Programming Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-105140