The Shapley value for airport and irrigation games

Márkus, Judit and Pintér, Miklós and Radványi, Anna (2011): The Shapley value for airport and irrigation games.

Abstract

In this paper cost sharing problems are considered. We focus on problems given by rooted trees, we call these problems cost-tree problems, and on the induced transferable utility cooperative games, called irrigation games. A formal notion of irrigation games is introduced, and the characterization of the class of these games is provided. The well-known class of airport games Littlechild and Thompson (1977) is a subclass of irrigation games. The Shapley value Shapley (1953) is probably the most popular solution concept for transferable utility cooperative games. Dubey (1982) and Moulin and Shenker (1992) show respectively, that Shapley's Shapley (1953) and Young (1985)'s axiomatizations of the Shapley value are valid on the class of airport games.

In this paper we show that Dubey (1982)'s and Moulin and Shenker (1992)'s results can be proved by applying Shapley (1953)'s and Young (1985)'s proofs, that is those results are direct consequences of Shapley (1953)'s and Young (1985)'s results. Furthermore, we extend Dubey (1982)'s and Moulin and Shenker (1992)'s results to the class of irrigation games, that is we provide two characterizations of the Shapley value for cost sharing problems given by rooted trees. We also note that for irrigation games the Shapley value is always stable, that is it is always in the core Gillies (1959).

• Item Type: MPRA Paper
• Language: English
• Keywords: TU games, Shapley value, Axiomatization, Cost Sharing
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

Aadland D, Kolpin V (1998) Shared irrigation costs: An empirical and axiomatic analysis. Mathematica Social Sciences 35:203-218

Ambec S, Ehlers L (2006) Sharing a river among satiable countries. Cahiers de recherche 07-2006, Centre interuniversitaire de recherche en Eeconomie quantitative, CIREQ

Ambec S, Sprumont Y (2002) Sharing a river. Journal of Economic Theory 107:453-462

Chun Y (1991) On the symmetric and weighted shapley values. International Journal of Game Theory 20:183-190

Dinar A, Ratner A, Yaron D (1992) Evaluating cooperative game theory in water resources. Theory and Decisions 32:1-20

Dinar A, Yaron D (1986) Treatment optimization of municipal wastewater, and reuse for regional irrigation. Water Resources Research 22:331-338

Dubey P (1982) The shapley value as aircraft landing fees-revisited. Management Science 28:869-874

Gillies DB (1959) Solutions to general non-zero-sum games. Contributions to the Theory of Games IV. Princeton University Press

Granot D, Maschler M, Owen G, Zhu W (1996) The kernel/nucleolus of a standard tree game. International Journal of Game Theory 25:219-244

Ichiishi T (1981) Super-modularity: Applications to convex games and the greedy algorithm for LP. Journal of Economic Theory 25:283-286

Kayi C (2007) Strategic and normative analysis of queueing, matching, and cost allocation. Ph.D. Thesis

Koster M, Molina E, Sprumont Y, Tijs S (2001) Sharing the cost of a network: core and core allocations. International Journal of Game Theory 30:567-599

Littlechild SC, Owen G (1973) A simple expression for the Shapley value in a special case. Management Science 20:370-372

Littlechild SC, Thompson GF (1977) Aircraft landing fees: a game theory approach. The Bell Journal of Economics 8:186-204

Megiddo N (1978) Computational complexity of the game theory approach to cost allocation for a tree. Mathematics of Operations Research 3(3):189-196

Moulin H (1988) Axioms of cooperative decision making Cambridge University Press

Moulin H, Shenker S (1992) Serial cost sharing. Econometrica 60:1009-1037

Ni D, Wang Y (2007) Additive cost sharing on a tree. Mimeo, University of Windsor, ON

Peleg B, Sudholter P (2003) Introduction to the theory of cooperative games Kluwer

Pinter M (2011) Young's axiomatization of the shapley value - a new proof. International Journal of Game Theory. forthcoming

Shapley LS (1953) A value for n-person games. In: Kuhn HW, Tucker AW (eds.) Contributions to the theory of games II, Annals of Mathematics Studies 28. Princeton University Press, Princeton pp. 307-317

Shapley LS (1971) Cores of convex games. International Journal of Game Theory 1:11-26

Thomson W (2007) Cost allocation and airport problems. Rochester Center for Economic Research, Working Paper No. 538

van den Brink R (2001) An axiomatization of the shapley value using a fairness property. International Journal of Game Theory 30:309-319

Young HP (1985) Monotonic solutions of cooperative games. International Journal of Game Theory 14:65-72