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 条
  • [41] Taxes for Linear Atomic Congestion Games
    Caragiannis, Ioannis
    Kaklamanis, Christos
    Kanellopoulos, Panagiotis
    ACM TRANSACTIONS ON ALGORITHMS, 2010, 7 (01)
  • [42] Weighted congestion games with separable preferences
    Milchtaich, Igal
    GAMES AND ECONOMIC BEHAVIOR, 2009, 67 (02) : 750 - 757
  • [43] Stackelberg pricing games with congestion effects
    Harks, Tobias
    Schedel, Anja
    MATHEMATICAL PROGRAMMING, 2024, 203 (1-2) : 763 - 799
  • [44] On the Performance of Approximate Equilibria in Congestion Games
    Christodoulou, George
    Koutsoupias, Elias
    Spirakis, Paul G.
    ALGORITHMICA, 2011, 61 (01) : 116 - 140
  • [45] Stackelberg Strategies for Atomic Congestion Games
    Fotakis, Dimitris
    THEORY OF COMPUTING SYSTEMS, 2010, 47 (01) : 218 - 249
  • [46] Stackelberg pricing games with congestion effects
    Tobias Harks
    Anja Schedel
    Mathematical Programming, 2024, 203 : 763 - 799
  • [47] On the Impact of Combinatorial Structure on Congestion Games
    Ackermann, Heiner
    Roegln, Heiko
    Voecking, Berthold
    JOURNAL OF THE ACM, 2008, 55 (06)
  • [48] On Stackelberg Strategies in Affine Congestion Games
    Bilo, Vittorio
    Vinci, Cosimo
    THEORY OF COMPUTING SYSTEMS, 2019, 63 (06) : 1228 - 1249
  • [49] Internalization of social cost in congestion games
    Milchtaich, Igal
    ECONOMIC THEORY, 2021, 71 (02) : 717 - 760
  • [50] Restoring Pure Equilibria to Weighted Congestion Games
    Kollias, Konstantinos
    Roughgarden, Tim
    Automata, Languages and Programming, ICALP, Pt II, 2011, 6756 : 539 - 551
12345