Loading...
Please wait, while we are loading the content...
Similar Documents
Altruism in Atomic Congestion Games
| Content Provider | ACM Digital Library |
|---|---|
| Author | Hoefer, Martin Skopalik, Alexander |
| Copyright Year | 2013 |
| Abstract | This article studies the effects of altruism, a phenomenon widely observed in practice, in the model of atomic congestion games. Altruistic behavior is modeled by a linear trade-off between selfish and social objectives. Our model can be embedded in the framework of congestion games with player-specific latency functions. Stable states are the pure Nash equilibria of these games, and we examine their existence and the convergence of sequential best-response dynamics. In general, pure Nash equilibria are often absent, and existence is NP-hard to decide. Perhaps surprisingly, if all delay functions are affine, the games remain potential games, even when agents are arbitrarily altruistic. The construction underlying this result can be extended to a class of general potential games and social cost functions, and we study a number of prominent examples. These results give important insights into the robustness of multi-agent systems with heterogeneous altruistic incentives. Furthermore, they yield a general technique to prove that stabilization is robust, even with partly altruistic agents, which is of independent interest. In addition to these results for uncoordinated dynamics, we consider a scenario with a central altruistic institution that can set incentives for the agents. We provide constructive and hardness results for finding the minimum number of altruists to stabilize an optimal congestion profile and more general mechanisms to incentivize agents to adopt favorable behavior. These results are closely related to Stackelberg routing and answer open questions raised recently in the literature. |
| Starting Page | 1 |
| Ending Page | 21 |
| Page Count | 21 |
| File Format | |
| ISSN | 21678375 |
| e-ISSN | 21678383 |
| DOI | 10.1145/2542174.2542177 |
| Volume Number | 1 |
| Issue Number | 4 |
| Journal | ACM Transactions on Economics and Computation (TEAC) |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2013-12-01 |
| Publisher Place | New York |
| Access Restriction | One Nation One Subscription (ONOS) |
| Subject Keyword | Congestion games Nash equilibrium Altruism Potential games |
| Content Type | Text |
| Resource Type | Article |
| Subject | Economics and Econometrics Marketing Computational Mathematics Statistics and Probability Computer Science |
