Congestion games with load-dependent failures: Identical resources

• 成果类型: Article; Proceedings Paper
• 署名作者: Penn, Michal; Polukarov, Maria; Tennenholtz, Moshe
• 署名单位: Technion Israel Institute of Technology; University of Southampton; Microsoft; MICROSOFT ISRAEL
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2009.03.004
• 发表日期: 2009
• 页码: 156-173
• 关键词: Congestion games; Load-dependent resource failures; Pure strategy Nash equilibrium; algorithms

摘要

We define a new class of games, congestion games with load-dependent failures (CGLFs). In a CGLF each player can choose a subset of a set of available resources in order to try and perform his task, We assume that the resources are identical but that players' benefits from successful completion of their tasks may differ. Each resource is associated with a cost of use and a failure probability which are load-dependent. Although CGLFs in general do not have a pure strategy Nash equilibrium, we prove the existence of a pure strategy Nash equilibrium in every CGLF with nondecreasing cost functions. Moreover, we present a polynomial time algorithm for computing such an equilibrium. Crown Copyright (C) 2009 Published by Elsevier Inc. All rights reserved.