zbMATH — the first resource for mathematics

Sharing costs in highways: a game theoretic approach. (English) Zbl 1332.91016
Summary: This paper introduces a new class of games, highway games, which arise from situations where there is a common resource that agents will jointly use. That resource is an ordered set of several indivisible sections, where each section has an associated fixed cost and each agent requires some consecutive sections. We present an easy formula to calculate the Shapley value, and we present an efficient procedure to calculate the nucleolus for this class of games.

91A12 Cooperative games
91A80 Applications of game theory
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
Full Text: DOI
[1] Algaba, E.; Bilbao, J.; Fernández-García, J.; López, J., Computing power indices in weighted multiple majority games, Mathematical Social Sciences, 46, 63-80, (2003) · Zbl 1053.91009
[2] Arin, J.; Iñarra, E., A characterization of the nucleolus for convex games, Games and Economic Behavior, 23, 12-24, (1998) · Zbl 0911.90363
[3] Brânzei, R.; Fragnelli, V.; Tijs, S., Tree-connected peer group situations and peer group games, Mathematical Methods of Operations Research, 55, 93-106, (2002) · Zbl 1052.91013
[4] Brânzei, R.; Solymosi, T.; Tijs, S., Strongly essential coalitions and the nucleolus of peer group games, International Journal of Game Theory, 33, 447-460, (2005) · Zbl 1121.91009
[5] Castaño-Pardo, A.; Garcı´a-Dı´az, A., Highway cost allocation: an application of the theory of nonatomic games, Transportation Research, 29, 187-203, (1995)
[6] Curiel, I.; Pederzoli, G.; Tijs, S., Sequencing games, European Journal of Operational Research, 40, 344-351, (1989) · Zbl 0674.90107
[7] Dong, B.; Guo, G.; Wang, Y., Highway toll pricing, European Journal of Operational Research, 220, 744-751, (2012) · Zbl 1253.91015
[8] Faigle, U.; Kern, W.; Kuipers, J., On the computation of the nucleolus of a cooperative game, International Journal of Game Theory, 30, 79-98, (2001) · Zbl 1060.91011
[9] Fragnelli, V.; García-Jurado, I.; Norde, H.; Patrone, F.; Tijs, S., How to share railways infrastructure costs?, (Patrone, F.; García-Jurado, I.; Tijs, S., Game Practice: Contributions from Applied Game Theory, (2000), Kluwer Academic Publishers), 91-101 · Zbl 0980.91046
[10] Granot, D.; Kuipers, J.; Chopra, S., Cost allocation for a tree network with heterogeneous customers, Mathematics of Operations Research, 27, 647-661, (2002) · Zbl 1082.91035
[11] Granot, D.; Maschler, M.; Owen, G.; Zhu, W. R., The kernel/nucleolus of a standard tree game, International Journal of Game Theory, 25, 219-244, (1996) · Zbl 0846.90136
[12] Çiftçi, B.; Borm, P.; Hamers, H., Highway games on weakly cyclic graphs, European Journal of Operational Research, 204, 117-124, (2010) · Zbl 1195.91015
[13] Koster, M.; Reijnierse, H.; Voorneveld, M., Voluntary contributions to multiple public projects, Journal of Public Economic Theory, 5, 25-50, (2003)
[14] Kuipers, J., 1996. A Polynomial Time Algorithm for Computing the Nucleolus of Convex Games. Tech. Rep. M 96-12, Maastricht University.
[15] Littlechild, S. C., A simple expression for the nucleolus in a special case, International Journal of Game Theory, 3, 21-29, (1974) · Zbl 0281.90108
[16] Littlechild, S. C.; Owen, G., A simple expression for the Shapley value in a special case, Management Science, 20, 370-372, (1973) · Zbl 0307.90095
[17] Littlechild, S. C.; Thompson, G. F., Aircraft landing fees: a game theory approach, The Bell Journal of Economics, 8, 186-204, (1977)
[18] Luskin, D., Garcı´a-Dı´az, A., Lee, D., Zhang, Z., Walton, C.M., 2001. A Framework for the Texas Highway Cost Allocation Study. Tech. Rep. 0-1801-1, Center for Transportation Research, the University of Texas at Austin, and Texas Transportation Institute, Texas A&M University System.
[19] Makrigeorgis, C.N., 1991. Development of an optimal durability-based highway cost allocation model. In: Ph.D. dissertation. Department of Industrial Engineering, Texas A&M University, College Station, TX.
[20] Maschler, M.; Peleg, B.; Shapley, L. S., The kernel and bargaining set for convex games, International Journal of Game Theory, 1, 73-93, (1972) · Zbl 0251.90056
[21] Megiddo, N., Computational complexity of the game theory approach to cost allocation for a tree, Mathematics of Operations Research, 3, 189-196, (1978) · Zbl 0397.90111
[22] Muto, S.; Nakayama, M.; Potters, J.; Tijs, S., On big boss games, The Economic Studies Quarterly, 39, 303-321, (1988)
[23] Potters, J.; Reijnierse, H.; Biswas, A., The nucleolus of balanced simple flow networks, Games and Economic Behavior, 54, 205-225, (2006) · Zbl 1129.91006
[24] Rosenthal, R. W., A class of games possessing pure-strategy Nash equilibria, International Journal of Game Theory, 2, 65-67, (1973) · Zbl 0259.90059
[25] Sandholm, W. H., Evolutionary implementation and congestion pricing, The Review of Economic Studies, 69, 667-689, (2002) · Zbl 1025.91002
[26] Schmeidler, D., The nucleolus of a characteristic function game, SIAM Journal on Applied Mathematics, 17, 1163-1170, (1969) · Zbl 0191.49502
[27] Shapley, L. S., A value for n-person games, (Kuhn, H. W.; Tucker, A. W., Contributions to the Theory of Games, Annals of Mathematics Studies, vol. 2, (1953), Princeton University Press Princeton, NJ), 307-317 · Zbl 0050.14404
[28] Sobolev, A. I., A characterization of optimality principles in cooperative games by functional equations, Mathematical Methods in the Social Sciences, 6, 94-151, (1975), (in Russian)
[29] Solymosi, T.; Raghavan, T. E.S., An algorithm for finding the nucleolus of assignment games, International Journal of Game Theory, 23, 119-143, (1994) · Zbl 0811.90128
[30] US Federal Highway Administration, 1997. Federal Highway Cost Allocation Study Final Report. Tech. Rep., Department of Transportation, Washington, DC.
[31] Villarreal-Cavazos, A.; García-Díaz, A., Development and application of new highway cost allocation procedures, Transportation Research Record, 1009, 34-45, (1985)
[32] Young, H. P., Cost allocation: methods, principles, applications, (1985), North-Holland New York
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.