Taxed congestion games with failures

被引：9

作者：

Penn, Michal ^{[1
]}

Polukarov, Maria

Tennenholtz, Moshe ^{[1
,2
]}

机构：

[1] Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel

[2] Microsoft Israel R&D Ctr, IL-46725 Herzliyya, Israel

来源：

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE | 2009年 / 56卷 / 02期

关键词：

Congestion games; Failures; Tax; Pure strategy Nash-equilibrium; Algorithm;

D O I：

10.1007/s10472-009-9164-3

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper, we introduce and study Taxed Congestion Games with Failures [TCGFs], extending congestion games with failures [CGFs] to consider costly task submission. We define TCGFs, and prove that TCGFs possess a pure strategy Nash-equilibrium. Moreover, we provide an efficient algorithm for the computation of such equilibrium. We also provide a specialized, simpler, algorithm for the case in which all resources are identical.

引用

页码：133 / 151

页数：19

共 50 条

[21] Congestion Games with Capacitated Resources
Laurent Gourvès
Jérôme Monnot
Stefano Moretti
Nguyen Kim Thang
Theory of Computing Systems, 2015, 57 : 598 - 616
[22] Congestion games with mixed objectives
Feldotto, Matthias
Leder, Lennart
Skopalik, Alexander
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (04) : 1145 - 1167
[23] Congestion Games with Malicious Players
Babaioff, Moshe
Kleinberg, Robert
Papadimitriou, Christos H.
EC'07: PROCEEDINGS OF THE EIGHTH ANNUAL CONFERENCE ON ELECTRONIC COMMERCE, 2007, : 103 - 112
[24] Contention Issues in Congestion Games
Koutsoupias, Elias
Papakonstantinopoulou, Katia
AUTOMATA, LANGUAGES, AND PROGRAMMING, ICALP 2012, PT II, 2012, 7392 : 623 - 635
[25] Congestion games with mixed objectives
Matthias Feldotto
Lennart Leder
Alexander Skopalik
Journal of Combinatorial Optimization, 2018, 36 : 1145 - 1167
[26] Transfer Implementation in Congestion Games
Arieli, Itai
DYNAMIC GAMES AND APPLICATIONS, 2015, 5 (02) : 228 - 238
[27] Social context congestion games
Bilo, Vittorio
Celi, Alessandro
Flammini, Michele
Gallotti, Vasco
THEORETICAL COMPUTER SCIENCE, 2013, 514 : 21 - 35
[28] Greediness and equilibrium in congestion games
Kuniavsky, Sergey
Smorodinsky, Rann
ECONOMICS LETTERS, 2013, 121 (03) : 499 - 503
[29] Concurrent imitation dynamics in congestion games
Heiner Ackermann
Petra Berenbrink
Simon Fischer
Martin Hoefer
Distributed Computing, 2016, 29 : 105 - 125
[30] On the Performance of Approximate Equilibria in Congestion Games
George Christodoulou
Elias Koutsoupias
Paul G. Spirakis
Algorithmica, 2011, 61 : 116 - 140

← 1 2 3 4 5 →