The study of equilibrium concepts in congestion games and two-sided markets with ties has been a primary topic in game theory, economics, and computer science. Ackermann, Goldberg, Mirrokni, Röglin, Vöcking (2008) gave a common generalization of these two models, in which a player more prioritized by a resource produces an infinite delay on less prioritized players. While presenting several theorems on pure Nash equilibria in this model, Ackermann et al. posed an open problem of how to design a model in which more prioritized players produce a large but finite delay on less prioritized players. In this paper, we present a positive solution to this open problem by combining the model of Ackermann et al. with a generalized model of congestion games due to Bilò and Vinci (2023). In the model of Bilò and Vinci, the more prioritized players produce a finite delay on the less prioritized players, while the delay functions are of a specific kind of affine functions, and all resources have the same priorities. By unifying these two models, we achieve a model in which the delay functions may be finite and non-affine, and the priorities of the resources may be distinct. We prove some positive results on the existence and computability of pure Nash equilibria in our model, which extend those for the previous models and support the validity of our model.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Unified Model of Congestion Games with Priorities

  • Kenjiro Takazawa

摘要

The study of equilibrium concepts in congestion games and two-sided markets with ties has been a primary topic in game theory, economics, and computer science. Ackermann, Goldberg, Mirrokni, Röglin, Vöcking (2008) gave a common generalization of these two models, in which a player more prioritized by a resource produces an infinite delay on less prioritized players. While presenting several theorems on pure Nash equilibria in this model, Ackermann et al. posed an open problem of how to design a model in which more prioritized players produce a large but finite delay on less prioritized players. In this paper, we present a positive solution to this open problem by combining the model of Ackermann et al. with a generalized model of congestion games due to Bilò and Vinci (2023). In the model of Bilò and Vinci, the more prioritized players produce a finite delay on the less prioritized players, while the delay functions are of a specific kind of affine functions, and all resources have the same priorities. By unifying these two models, we achieve a model in which the delay functions may be finite and non-affine, and the priorities of the resources may be distinct. We prove some positive results on the existence and computability of pure Nash equilibria in our model, which extend those for the previous models and support the validity of our model.