期刊
OPERATIONS RESEARCH
卷 59, 期 6, 页码 1445-1460出版社
INFORMS
DOI: 10.1287/opre.1110.0964
关键词
-
资金
- Natural Sciences and Engineering Research Council (NSERC) of Canada
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据