Extending finite-memory determinacy to multi-player games

被引：4

作者：

Le Roux, Stephane ^{[1
]}

Pauly, Arno ^{[1
]}

机构：

[1] Univ Libre Bruxelles, Dept Informat, B-1050 Brussels, Belgium

来源：

INFORMATION AND COMPUTATION | 2018年 / 261卷

关键词：

Finite memory; Games played on finite graphs; Finite-memory determinacy; Nash equilibrium; Equilibrium transfer; Energy parity games; PARITY GAMES;

D O I：

10.1016/j.ic.2018.02.024

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that under some general conditions the finite memory determinacy of a class of two-player win/lose games played on finite graphs implies the existence of a Nash equilibrium built from finite memory strategies for the corresponding class of multi-player multi-outcome games. This generalizes a previous result by Brihaye, De Pril and Schewe. We provide a number of example that separate the various criteria we explore. Our proofs are generally constructive, that is, provide upper bounds for the memory required, as well as algorithms to compute the relevant Nash equilibria. (C) 2018 Elsevier Inc. All rights reserved.

引用

页码：676 / 694

页数：19

共 44 条

[21] Selfish cops and active robber: Multi-player pursuit evasion on graphs
Konstantinidis, G.
Kehagias, A.
THEORETICAL COMPUTER SCIENCE, 2019, 780 : 84 - 102
[22] Finite-Memory Least Squares Universal Prediction of Individual Continuous Sequences
Dar, Ronen
Feder, Meir
2011 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS (ISIT), 2011, : 224 - 228
[23] On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria
Berthelsen, Marie Louisa Tolboll
Hansen, Kristoffer Arnsfelt
THEORY OF COMPUTING SYSTEMS, 2022, 66 (03) : 519 - 545
[24] The One-Round Multi-player Discrete Voronoi Game on Grids and Trees
Sun, Xiaoming
Sun, Yuan
Xia, Zhiyu
Zhang, Jialin
COMPUTING AND COMBINATORICS, COCOON 2019, 2019, 11653 : 529 - 540
[25] The one-round multi-player discrete Voronoi game on grids and trees
Sun, Xiaoming
Sun, Yuan
Xia, Zhiyu
Zhang, Jialin
THEORETICAL COMPUTER SCIENCE, 2020, 838 : 143 - 159
[26] Multi-Player Game Theoretic MAC Strategies for Energy Efficient Data Dissemination
Antonopoulos, Angelos
Verikoukis, Christos
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, 2014, 13 (02) : 592 - 603
[27] there exists R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria
Garg, Jugal
Mehta, Ruta
Vazirani, Vijay V.
Yazdanbod, Sadra
ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION, 2018, 6 (01)
[28] Existence theorems of generalized K-lateral support equilibria via local cooperative strategies for multi-player pure strategy games in tensor form
Xu, Chenli
Gao, Kaixin
Huang, Zheng-Hai
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2025, 468
[29] Nash Equilibria of 2-Player Finite Simultaneous Move Games
Chen, Qianqin
Ou, Ruiqiu
Yang, Jianmei
FIRST IITA INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2009, : 833 - +
[30] FINITE-MEMORY NONLINEAR SYSTEM MODELLING OF OFFSHORE STRUCTURAL RESPONSE ACCOUNTING FOR EXTREME VALUES RESIDUES
Zaki, N. I. Mohd
Abu Husain, M. K.
Mallahzadeh, H.
Najafian, G.
PROCEEDINGS OF THE ASME 32ND INTERNATIONAL CONFERENCE ON OCEAN, OFFSHORE AND ARCTIC ENGINEERING - 2013, VOL 2A, 2013,

← 1 2 3 4 5 →