zbMATH — the first resource for mathematics

Pricing traffic in a spanning network. (English) Zbl 1294.91037
Summary: Users need to connect a pair of target nodes in the network. They share the fixed connection costs of the edge. The system manager elicits target pairs from users, builds the cheapest forest meeting all demands, and choose a cost sharing rule satisfying:
Routing-proofness: a user cannot lower his cost by reporting as several users along an alternative path connecting his target nodes;
Stand Alone core stability: no group of users pay more than the cost of a subnetwork meeting all connection needs of the group.
We construct two such rules. When all connecting costs are 0 or 1, one is derived from the random spanning tree weighted by the volume of traffic on each edge; the other is the weighted Shapley value of the Stand Alone cooperative game. Both rules are then extended by the familiar piecewise-linear technique. The former is computable in polynomial time, the latter is not.

91A43 Games involving graphs
91A12 Cooperative games
91A80 Applications of game theory
90B20 Traffic problems in operations research
Full Text: DOI
[1] Anshelevich, E.; Dasgupta, J.; Kleinberg, J.; Tardos, E.; Wexler, T.; Roughgarden, T., The price of anarchy for network design with fair cost allocation, (Proceedings IEEE Symposium on Foundations of Computer Science, (2004)), 295-304
[2] Anshelevich, E.; Dasgupta, J.; Tardos, E.; Wexler, T., Near-optimal network design with selfish agents, Theory Comput., 4, 1, 77-109, (2008) · Zbl 1213.68698
[3] Bergantiños, G.; Vidal-Puga, J. J., A fair rule in minimum cost spanning tree problems, J. Econ. Theory, 137, 326-352, (2007) · Zbl 1132.91366
[4] Berge, C., Graphs and hypergraphs, (1973), North-Holland · Zbl 0483.05029
[5] Bird, C. J., On cost allocation for a spanning tree: a game theoretic approach, Networks, 6, 335-350, (1976) · Zbl 0357.90083
[6] Bogomolnaia, A.; Moulin, H., Sharing a minimal cost spanning tree: beyond the folk solution, Games Econ. Behav., 69, 238-248, (2010) · Zbl 1230.91019
[7] Bogomolnaia, A.; Holzman, R.; Moulin, H., Sharing the cost of a capacity network, Math. Oper. Res., 35, 1, 173-192, (2010) · Zbl 1232.91063
[8] Cheng, A.; Friedman, E., Sybilproof reputation mechanisms, (SIGCOMM’05 Workshops, August 22-26, Philadelphia, (2005))
[9] Claus, A.; Kleitman, D. J., Cost allocation for a spanning tree, Networks, 3, 289-304, (1973) · Zbl 0338.90031
[10] Conitzer, V., Anonymity-proof voting rules, (Fourth Workshop on Internet and Network Economics (WINE-08), Shanghai, (2008))
[11] Dong, B., Gou, G., Wang, Y., 2008. Highway toll pricing. Mimeo. University of Windsor, Ontario.
[12] Douceur, J., The sybil attack, (Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS 2002), LNCS, vol. 2429, (2002)), 251-260 · Zbl 1014.68882
[13] Dutta, B.; Kar, A., Cost monotonicity, consistency, and minimum cost spanning tree games, Games Econ. Behav., 48, 223-248, (2004) · Zbl 1117.91308
[14] Epstein, A.; Feldman, M.; Mansour, Y., Strong equilibrium in cost sharing connection games, Games Econ. Behav., 67, 1, 51-68, (2009) · Zbl 1168.91330
[15] Feltkamp, T., Tijs, S., Muto, S., 1994. On the irreducible core and the equal remaining obligations rule of minimum cost spanning extension problems. Mimeo. University of Tilburg. CentER DP 94106.
[16] Granot, D.; Huberman, G., On the core and nucleolus of minimum cost spanning tree games, Math. Program., 29, 323-347, (1984) · Zbl 0541.90099
[17] Granot, D.; Maschler, M., Spanning network games, Int. J. Game Theory, 27, 4, 467-500, (1998) · Zbl 1058.91518
[18] Henriet, D.; Moulin, H., Traffic based cost allocation in a network, RAND J. Econ., 27, 2, 332-345, (1996)
[19] Herzog, S.; Shenker, S.; Estrin, D., Sharing the cost of multicast trees: an axiomatic analysis, IEEE/ACM Trans. Netw., 5, 6, 847-860, (December 1997)
[20] Hoefer, M., Strategic cooperation in cost sharing games, Int. J. Game Theory, 42, 1, 29-53, (2013) · Zbl 1282.91030
[21] Kalai, E.; Samet, D., On weighted Shapley values, Int. J. Game Theory, 16, 205-222, (1987) · Zbl 0633.90100
[22] Megiddo, N., Cost allocations for Steiner trees, Networks, 8, 1-6, (1978) · Zbl 0378.90118
[23] Moulin, H., On scheduling fees to prevent merging, splitting and transferring of jobs, Math. Oper. Res., 32, 2, 266-283, (2007) · Zbl 1279.90070
[24] Moulin, H.; Shenker, S., Strategyproof sharing of submodular costs: budget balance versus efficiency, Econ. Theory, 18, 3, 511-533, (2001) · Zbl 1087.91509
[25] (Nisan, N.; Rougarden, T.; Tardos, E.; Vazirani, V., Algorithmic Game Theory, (2007), Cambridge Univ. Press)
[26] Norde, H.; Moretti, S.; Tijs, S., Minimum cost spanning tree games and population monotonic allocation schemes, Europ. J. Oper. Res., 154, 1, 84-97, (2001) · Zbl 1099.90067
[27] Prim, R. C., Shortest connection network and some generalization, Bell Syst. Tech. J., 36, 1389-1401, (1957)
[28] Roughgarden, T., Selfish routing and the price of anarchy, (2005), MIT Press
[29] Sharkey, W. W., Network models in economics, (Ball, M. O.; Magnanti, T. L.; Nonma, C. L.; Nemhauser, G. L., Handbooks in Operation Research and Management Science, (1995), Elsevier New York), 713-765 · Zbl 0861.90023
[30] Sprumont, Y., Population monotonic allocation schemes for cooperative games with transferable utility, Games Econ. Behav., 2, 378-394, (1990) · Zbl 0753.90083
[31] Tamir, A., On the core of network synthesis games, Math. Program., 50, 123-135, (1991) · Zbl 0722.90091
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.