4.7 Article

Computing equilibria for integer programming games

期刊

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 303, 期 3, 页码 1057-1070

出版社

ELSEVIER
DOI: 10.1016/j.ejor.2022.03.048

关键词

Combinatorial optimization; Nash equilibria; Correlated equilibria; Algorithmic game theory; Integer programming games

资金

  1. Fonds de recherche du Quebec (FRQ) through the FRQ-IVADO Research Chair
  2. NSERC [2019-04557]
  3. Portuguese Foundation for Science and Technology (FCT) [SFRH/BD/79201/2011]
  4. POPH/FSE
  5. Institut de valorisation des donnees (IVADO)

向作者/读者索取更多资源

In this paper, the concept of integer programming games (IPG) and its application in real-world problems are introduced. A general algorithmic approach is developed to determine the equilibrium solution of the game by computing Nash equilibria and utilizing sufficient conditions. The performance of the method is validated through computational experiments on various games.
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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.7
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据