A novel approximate method of computing extended Nash equilibria

被引:1
|
作者
Juszczuk, Przemyslaw [1 ]
机构
[1] Univ Econ, Fac Informat & Commun, Dept Knowledge Engn, Katowice, Poland
关键词
Approximate equilibrium; Game theory; Differential evolution; Matrix games; DIFFERENTIAL EVOLUTION; POINTS; OPTIMIZATION; COMPUTATION; ALGORITHM;
D O I
10.1016/j.asoc.2019.01.003
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
In this paper, we propose a new method of computing an approximate Nash equilibrium with additional features. Existing algorithms often fail to produce an exact solution for games involving more than 3 players. Similarly, existing algorithms do not permit additional constraints on the problem. The principle idea of this paper involves proposing a methodology for computing approximate solutions through evolutionary computation. To do so, we first provide formal definitions of these problems and their approximate versions. Following which, we present the details of our solution. One of the most important advantages of the proposed solution is flexibility, which provides solutions to problems related to Nash equilibrium extensions. The proposed idea is tested on several types of games that vary with difficulty and size. All test sets are generated based on the well-known Gamut program. Additional comparisons with classical algorithms are also performed. Results indicate that Differential Evolution is capable of obtaining satisfactory solutions to large random and covariant games. The results also demonstrate that there is a high probability that even large games, in which a set of strategies with a non-zero probability of being chosen are very small, have a solution. The computation time depends mainly on the problem size, and the original Nash equilibrium problem is unaffected by additional modifications. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码:682 / 696
页数:15
相关论文
共 50 条
  • [21] Approximate Nash Equilibria in Bimatrix Games
    Boryczka, Urszula
    Juszczuk, Przemyslaw
    COMPUTATIONAL COLLECTIVE INTELLIGENCE: TECHNOLOGIES AND APPLICATIONS, PT II: THIRD INTERNATIONAL CONFERENCE, ICCCI 2011, 2011, 6923 : 485 - 494
  • [22] On Approximate Nash Equilibria in Network Design
    Albers, Susanne
    Lenzner, Pascal
    INTERNET AND NETWORK ECONOMICS, 2010, 6484 : 14 - 25
  • [23] Communication complexity of approximate Nash equilibria
    Babichenko, Yakov
    Rubinstein, Aviad
    GAMES AND ECONOMIC BEHAVIOR, 2022, 134 : 376 - 398
  • [24] Query Complexity of Approximate Nash Equilibria
    Babichenko, Yakov
    STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, : 535 - 544
  • [25] Communication Complexity of Approximate Nash Equilibria
    Babichenko, Yakov
    Rubinstein, Aviad
    STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, : 878 - 889
  • [26] Approximate Nash equilibria in anonymous games
    Daskalakis, Constantinos
    Papadimitriou, Christos H.
    JOURNAL OF ECONOMIC THEORY, 2015, 156 : 207 - 245
  • [27] On Approximate Nash Equilibria in Network Design
    Albers, Susanne
    Lenzner, Pascal
    INTERNET MATHEMATICS, 2013, 9 (04) : 384 - 405
  • [28] Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming
    Caragiannis, Ioannis
    Jiang, Zhile
    PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023, : 710 - 722
  • [29] Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions
    Bilo, Vittorio
    Flammini, Michele
    Monaco, Gianpiero
    Moscardelli, Luca
    DISTRIBUTED COMPUTING, 2021, 34 (01) : 1 - 14
  • [30] Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions
    Vittorio Bilò
    Michele Flammini
    Gianpiero Monaco
    Luca Moscardelli
    Distributed Computing, 2021, 34 : 1 - 14