×

Public congestion network situations and related games. (English) Zbl 1200.91052

Summary: This article analyses congestion in network situations from a cooperative game theoretic perspective. In network situations, players have to connect themselves to a source. As we consider publicly available networks, any group of players is allowed to use the entire network to establish their connections. We deal with the problem of finding an optimal network and discuss the associated cost allocation problem. For the latter, we introduce two different transferable utility cost games. For concave cost functions, we use the direct cost game, in which coalition costs are based on what a coalition can do in the absence of other players. This article, however, mainly discusses network situations with convex cost functions, which are analyzed by the use of the marginal cost game. In this game, the cost of a coalition is defined as the additional cost it induces when it joins the complementary group of players. We prove that this game is concave. Furthermore, we define a cost allocation by means of three equal treatment principles and show that this allocation is an element of the core of the marginal cost game. These results are extended to a class of continuous network situations and associated games.

MSC:

91A43 Games involving graphs
91A10 Noncooperative games

References:

[1] Braess, Über ein paradoxen aus der verkehrsplanung, Unternehmensforschung 12 pp 258– (1968) · Zbl 0167.48305
[2] Cormen, Introduction to algorithms (1990)
[3] Johari, Efficiency loss in a network resource allocation game, Math Oper Res 3 pp 407– (2004) · Zbl 1082.90015
[4] Kamien, Betrand competition with subcontracting, RAND J Econ 4 pp 553– (1989)
[5] Matsubayashi, A cost allocation problem arising in hub-spoke network systems, Eur J Oper Res 160 pp 821– (2005) · Zbl 1061.90015
[6] Milchtaich, Social optimality and cooperation in nonatomic congestion games, J Econ Theory 114 pp 56– (2004) · Zbl 1072.91011
[7] Monderer, Potential games, Games Econ Behav 14 pp 124– (1996) · Zbl 0862.90137
[8] O’Neill, A problem of rights arbitration from the Talmud, Math Soc Sci 2 pp 345– (1982)
[9] Quant, Congestion network problems and related games, Eur J Oper Res 172 pp 919– (2006) · Zbl 1111.90019
[10] Rosenthal, A class of games possessing pure-strategy Nash equilibria, Int J Game Theory 2 pp 65– (1973) · Zbl 0259.90059
[11] Spiegel, Horizontal subcontracting, RAND J Econ 4 pp 570– (1993)
[12] Thomson, Axiomatic and game theoretic analysis of bankruptcy and taxation problems: A survey, Math Soc Sci 45 pp 249– (2003) · Zbl 1042.91014
[13] Vöcking, Proceedings of the 2nd algorithms and complexity in Durham workshop pp 9– (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.