.png){kind=icon}
返回
Computing equilibria for integer programming games
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2022.03.048.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The recently-defined class of integer programming games (IPG) models situations where multiple self-interested decision makers interact, with their strategy sets represented by a finite set of linear constraints together with integer requirements. Many real-world problems can suitably be cast in this way, hence anticipating IPG outcomes is of crucial value for policy makers. Nash equilibria have been widely accepted as the solution concept of a game. Thus, their computation provides a reasonable prediction of games outcome. In this paper, we start by showing the computational complexity of deciding the existence of a Nash equilibrium for an IPG. Then, using sufficient conditions for their existence, we develop a general algorithmic approach that is guaranteed to return a Nash equilibrium when the game is finite and to approximate an equilibrium when payoff functions are Lipschitz continuous. We also showcase how our methodology can be changed to determine other types of equilibria. The performance of our methods is analyzed through computational experiments on knapsack, kidney exchange and a competitive lot-sizing games. To the best of our knowledge, this is the first time that equilibria computation methods for general IPGs have been designed and computationally tested. (C) 2022 Elsevier B.V. All rights reserved.
Keyword:
Combinatorial optimization
Nash equilibria
Correlated equilibria
Algorithmic game theory
Integer programming games
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
.png){kind=icon}
Effect of carboxyl methyl cellulose on the adhesion properties of sodium silicate wood adhesive
PREAI
分享收藏分享收藏
Solving three-player games by the matrix approach with application to an electric power market通过矩阵方法解决三人游戏，并将其应用于电力市场
PREAI
分享收藏
查看更多内容