Abstract
This paper surveys the research area of cooperative games associated with several types of operations research problems in which various decision makers (players) are involved. Cooperating players not only face a joint optimisation problem in trying, e.g., to minimise total joint costs, but also face an additional allocation problem in how to distribute these joint costs back to the individual players. This interplay between optimisation and allocation is the main subject of the area of operations research games. It is surveyed on the basis of a distinction between the nature of the underlying optimisation problem: connection, routing, scheduling, production and inventory.
Similar content being viewed by others
References
Aadland D. and Kolpin V. (1998). Shared irrigation cost: an empirical and axiomatic analysis.Mathematical Social Sciences 35, 203–218.
Aarts H (1994). Minimum cost spanning tree games and set games. PhD thesis, University of Twente, Enschede, The Netherlands.
Aarts H. and Driessen T. (1993). The irreducible core of a minimum cost spanning tree game.Zeitschrift für Operations Research (Now:Mathematical Methods of Operations Research) 38, 163–174.
Assad A. (1978). Multicommodity network flows — a survey.Networks 8, 37–91.
Aumann R. and Maschler M. (1985). Game theoretic analysis of a bankruptcy problem from the Talmud.Journal of Economic Theory 36, 195–213.
Balinsky M. and Gale D. (1990). On the core of assignment games. In: Leifman L. (ed.),Functional analysis, optimization and mathematical economics: a collection of papers dedicated to the memory of Leonid Vatalévich Kontorovich. Oxford University Press, 274–289.
Bilbao M. (2000).Cooperative games on combinatorial structures. Kluwer Academic Publishers.
Bird C. (1976). On cost allocation for a spanning tree: a game theoretic approach.Networks 6, 335–350.
Bird G. (1981). Cores of monotonic linear production games.Mathematics of Operations Research 6, 420–423.
Bjørndal E., Koster M. and Tijs S. (1999). Weighted allocation rules for standard fixed tree games. CentER Discussion Paper 9979, Tilburg University, Tilburg, The Netherlands.
Borm P., De Waegenaere A., Rafels C., Suijs J., Tijs S., Timmer J. (2001). Cooperation in capital deposits.OR Spektrum 23, 265–281.
Borm P., Fiestras-Janeiro G., Hamers H., Sánchez E. and Voorneveld M. (1999). On the convexity of games corresponding to sequencing situations with due dates. CentER Discussion Paper 1999-49, Tilburg University, Tilburg, The Netherlands. (To appear inEuropean Journal of Operational Research).
Branzei R., Iñarra E., Tijs S. and Zarzuelo J. (2001). Cooperation by asymmetric agents in a joint project. Technical Report, Bilbao University, Bilbao, Spain.
Calleja P., Borm P., Hamers H. and Klijn F. (2001a). On a new class of parallel sequencing situations and related games. CentER Discussion Paper 2001-03, Tilburg University, Tilburg, The Netherlands.
Calleja P., Borm P. and Hendrickx R. (2001b). Multi-issue allocation games. CentER Discussion Paper 2001-30, Tilburg University, Tilburg, The Netherlands.
Claus A. and Kleitman D. (1973). Cost allocation for a spanning tree.Networks 3, 289–304.
Curiel I. (1997).Cooperative game theory and applications. Kluwer Academic Publishers.
Curiel I., Derks J. and Tijs S. (1989). On balanced games and flow games with committee control.OR Spektrum 11, 83–88.
Curiel I., Hamers H., Potters J. and Tijs S. (1997). Restricted component additive games.Mathematical Methods of Operations Research 45, 213–220.
Curiel I., Maschler M. and Tijs S. (1987). Bankruptcy games.Zeitschrift für Operations Research 31, 143–159.
Curiel I., Pederzoli G. and Tijs S. (1988). Reward allocations in production systems. In: Eiselt H. and G. Pederzoli G. (eds.),Advances in Optimization and Control. Springer Verlag, 186–199.
Curiel I., Pederzoli G. and Tijs S. (1989). Sequencing games.European Journal of Operational Research 40, 344–35.
Curiel I., Potters J., Rajendra Prasad V., Tijs S. and Veltman B. (1994). Cooperation in one machine scheduling.Zeitschrift für Operations Research 38, 113–129.
Curiel I., Potters J., Rajendra Prasad V., Tijs S. and Veltman B. (1995). Sequencing and cooperation.Operations Research 42, 566–568.
Curiel I. and Tijs S. (1986). Assignment games and permutation games.Methods of Operations Research 54, 323–334.
Debreu G. and Scarf H. (1963). A limit theorem on the core of an economy.Econometrica 53, 873–888.
Derks J. and Kuipers J. (1997). On the core of routing games.International Journal of Game Theory 26, 193–205.
Derks J. and Tijs S. (1985). Stable outcomes for multi-commodity flow games.Methods of Operations Research 50, 493–504.
Derks J. and Tijs S. (1986). Totally balanced multi-commodity games and flow games.Methods of Operations Research 54, 335–347.
Driessen T. (1988).Cooperative games, solutions and applications. Kluwer Academic Publishers.
Dubey P. (1982). The Shapley value as aircraft landing fees revisited.Management Science 28, 869–874.
Dubey P. and Shapley L. (1984). Totally balanced games arising from controlled programming problems.Mathematical Programming 29, 245–267.
Edmonds J. and Johnson E. (1973). Matching, Euler tours and the Chinese postman.Mathematical Programming 5, 88–124.
Feltkamp V. (1995). Cooperation in Controlled Network Structures. PhD thesis, Tilburg University, Tilburg, The Netherlands.
Feltkamp V., Nouweland A. van den, Borm P., Tijs S. and Koster A. (1993). Linear production with transport of products, resources and technology.Zeitschrift für Operations Research 38, 153–162.
Feltkamp V., Tijs S. and Muto S. (1994). Minimum cost spanning extension problems: the proportional rule and the decentralized rule. CentER Discussion Paper 9496, Tilburg University, Tilburg, The Netherlands.
Fishburn P. and Pollack H. (1983). Fixed route cost allocation.American Mathematical Monthly 90, 366–378.
Ford L. and Fulkerson D. (1962).Flows in networks. Princeton University Press.
Fragnelli V., Garcia-Jurado I. and Mendez-Naya L. (2000). On shortest path games.Mathematical Methods of Operations Research 52, 251–264.
Fragnelli V., Patrone F., Sideri E. and Tijs S. (1999). Balanced games arising from infinite linear models.Mathematical Methods of Operations Research 50, 385–397.
Gale D. (1984). Equilibrium in a discrete exchange economy with money.International Journal of Game Theory 13, 61–64.
Gale D. and Shapley L. (1962). College admission and the stability of marriage.American Mathematical Monthly 69, 9–15.
Galil Z. (1980). Applications of efficient mergeable heaps for optimization problems on trees.Acta Informatica 13, 53–58.
Gellekom A. van and Potters J. (1999). Consistent rules for standard tree enterprises. Technical Report 9919, Department of Mathematics, University of Nijmegen, Nijmegen, The Netherlands.
Gellekom J. van, Potters J., Reijnierse J., Tijs S. and Engel M. (2000). Characterization of the Owen set of linear production processes.Games and Economic Behavior 32, 139–156.
Graham R. and Hell P. (1985). On the history of the minimum spanning tree problem.Annals of the History of Computing 7, 43–57.
Grahn S. (2001). Core and bargaining set of shortest path games. Discussion Paper 2001:3. Department of Economics, Upssala University, Uppsala, Sweden.
Granot D. (1986). A generalized linear production model: a unifying model.Mathematical Programming 34, 212–222.
Granot D. and Granot F. (1992a). On some nerwork flow games.Mathematics of Operations Research 17, 792–841.
Granot D. and Granot F. (1992b). On the computational complexity of a cost allocation approach to a fixed cost spanning forest problem.Mathematics of Operations Research 17, 765–780.
Granot D., Granot F. and Zhu W. (2000). Naturally submodular digraphs and forbidden digraph configurations.Discrete applied mathematics 100, 67–84.
Granot D. and Hamers H. (2000). On the equivalence between some local and global Chinese postman and traveling salesman graphs. CentER Discussion Paper 2000-48, Tilburg University, Tilburg, The Netherlands.
Granot D., Hamers H. and Tijs S. (1999). On some balanced, totally balanced and submodular delivery games.Mathematical Programming 86, 355–366.
Granot D. and Huberman G. (1981). On minimum cost spanning tree games.Mathematical Programming 21, 1–18.
Granot D. and Huberman G. (1982). The relationship between convex games and minimal cost spanning tree games: A case for permutationally convex games.SIAM Journal of Algorithms and Discrete Methods 3, 288–292.
Granot D. and Huberman G. (1984). On the core and nucleolus of minimum cost spanning tree games.Mathematical Programming 29, 323–347.
Granot D. and Maschler M. (1998). Spanning network games.International Journal of Game Theory 27, 467–500.
Granot D., Maschler M., Owen G. and Zhu W. (1996). The kernel/nucleolus of a standard fixed tree game.International Journal of Game Theory 25, 219–244.
Hamers H. (1995). Sequencing and delivery situations: a game theoretic approach. PhD thesis, Tilburg University, Tilburg, The Netherlands.
Hamers H. (1997). On the concavity of delivery games.European Journal of Operational Research 99, 445–458.
Hamers H., Borm P., Leensel R. van de and Tijs S. (1999a). Cost allocation in the Chinese postman problem.European Journal of Operational Research 118, 153–163.
Hamers H., Borm P., Suijs J. and Tijs S. (1996). The split core for sequencing games.Games and Economic Behavior 15, 165–176.
Hamers H., Borm P. and Tijs S. (1995). On games corresponding to sequencing situations with ready times.Mathematical Programming 70, 1–13.
Hamers H., Klijn F., Solymosi T., Tijs S. and Vermeulen D. (1999b). On the nucleolus of neighbour games. CentER Discussion Paper 99111, Tilburg University, Tilburg, The Netherlands.
Hamers H., Klijn F., Solymosi T., Tijs S. and Villar J. (1999c). On the extreme points of the core of neighbour games and assignment games. CentER Discussion Paper 9943, Tilburg University, Tilburg, The Netherlands. (To appear inGames and Economic Behavior).
Hamers H., Klijn F. and Suijs J. (1999d). On the balancedness of multimachine sequencing games.European Journal of Operational Research 119, 678–691.
Hartman B., Dror M. and Shaked M. (2000). Cores of inventory centralization games.Games and Economic Behavior 31, 26–49.
Hax A. and Candea D. (1984).Production and inventory management. Prentice-Hall.
Herer Y. and Penn M. (1995). Characterization of naturally submodular graphs: a polynomial solvable class of the TSP.Proceedings of the AMS 123, 613–619.
Izquierdo J. and Rafels C. (1996). A generalization of the bankruptcy game: financial cooperative games. Working Paper E96/09, University of Barcelona, Barcelona, Spain.
Kalai E. and Zemel E. (1982a). Generalized network problems yielding totally balanced games.Operations Research 30, 998–1008.
Kalai E. and Zemel E. (1982b). Totally balanced games and games of flow.Mathematics of Operations Research 7, 476–478.
Kaminski M. (2000). “Hydraulic” Rationing.Mathematical Social Sciences 40, 131–155.
Kaneko M. (1982). The central assignment game and the assignment markets.Journal of Mathematical Economics 10, 205–232.
Klijn F., Tijs S. and Hamers H. (2000). Balancedness of permutation games and envy-free allocations in indivisible good economies.Economic Letters 69, 323–326.
Koster M. (1999). Cost sharing in production situations and network exploitation. PhD thesis, Tilburg University, Tilburg, The Netherlands.
Koster M., Molina E., Sprumont Y. and Tijs S. (1998). Sharing the cost of a network: core and core allocations. CentER Discussion Paper 9821, Tilburg University, Tilburg.
Koster M., Reijnierse J. and M. Voorneveld (1999). Voluntary contribution to multiple facilities: a class of ordinal potential games. CentER Discussion Paper 9988, Tilburg University, Tilburg, The Netherlands.
Kruskal J. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem.Proceedings of the American Mathematical Society 7, 48–50.
Kuipers J. (1993). A note on the 5-person traveling salesman game.Zeitschrift für Operations Research 38, 131–140.
Kuipers J., Solymosi T. and Aarts H. (2000). Computing the nucleolus of some combinatorially-structured games.Mathematical Programming 88, 541–563.
Lawler E., Lenstra J., Rinnooy Kan A. and Shmoys D. (1993). Sequencing and scheduling: algorithms and complexity. In: Graves S., Rinnooy Kan A. and Zipkin P. (eds.),Logistics of production and inventory. North Holland, 445–522.
Lawler E., Lenstra J.K., Rinnooy Kan A. and Shmoys D. (1985).The traveling salesman problem. John Wiley and Sons.
Littlechild S. (1974). A simple expression for the nucleolus in a special case.International Journal of Game Theory 3, 21–29.
Littlechild S. and Owen G. (1973). A simple expression for the Shapley value in a special case.Management Science 20, 370–372.
Littlechild S. and Owen G. (1977). A further note on the nucleolus of the airport game.International Journal of Game Theory 5, 91–95.
Littlechild S. and Thompson G. (1977). Aircraft landing fees: a game theory approach.The Bell Journal of Economics 8, 186–204.
Llorca N., Tijs S. and Timmer J. (1999). Semi-infinite assignment problems and related games. CentER Discussion Paper 9974, Tilburg University, Tilburg, The Netherlands.
Maschler M. and Potters J. and Reijnierse J. (1995). Monotonicity properties of the nucleolus of standard tree games. Technical Report 9556, Department of Mathematics, University of Nijmegen, Nijmegen, The Netherlands.
Meca A., Garcia-Jurado I. and Borm P. (2001). Cooperation and competition in inventory games. CIO Discussion Paper, Universidad Miguel Hernández, Elche, Spain.
Meca A., Timmer J., Garcia-Jurado I. and Borm P. (1999). Inventory Games. CentER Discussion Paper 9953, Tilburg University, Tilburg, The Netherlands.
Megiddo N. (1978). Computational complexity of the game theory approach to cost allocation for a tree.Mathematics of Operations Research 3, 189–196.
Mei-Ko Kwan (1962). Graphic programming using odd and even points.Chinese Mathematics 1, 273–277.
Moretti S., Norde H., Pham Do K. and Tijs S. (2001). Connection problems in mountains and monotonic cost allocation schemes. CentER Discussion Paper 2001-12, Tilburg University, Tilburg, The Netherlands.
Moulin H. and Shenker S. (1992a). Average cost pricing versus social cost sharing: an axiomatic comparison.Journal of Economic Theory 64, 178–201.
Moulin H. and Shenker S. (1992b). Serial cost sharing.Econometrica 60, 1009–1037.
Müller A., Scarsini M. and Shaked M. (2000). The newsvendor game has a non-empty core. Technical report WIOR-594, University of Karlruhe, Karlsruhe, Germany.
Nishizaki I. and Sakawa M. (2001). On computational methods for solutions of multiobjective linear production programming games.European Journal of Operational Research 129, 386–413.
Norde H., Moretti S. and Tijs S. (2001). Minimum cost spanning tree games and population monotonic allocation schemes. CentER Discussion Paper 2001-18, Tilburg University, Tilburg, The Netherlands.
Nouweland A. van den, Krabbenborg M. and Potters J. (1992). Flowshops with a dominant machine.European Journal of Operational Research 62, 38–46.
Nouweland A. van den, Maschler M. and Tijs S. (1993). Monotonic games are spanning network games.International Journal of Game Theory 21, 419–427.
Nuñez M. and Rafels C. (2000). The extreme core allocations of the assignment games. Technical report, University of Barcelona, Barcelona, Spain.
O’Neill B. (1982). A problem of rights arbitration from the Talmud.Mathematical Social Sciences 2, 345–371.
Owen G. (1975). On the core of linear production games.Mathematical Programming 9, 358–370.
Owen G. (1992). The assignment game: the reduced game.Annals of Economics and Statistics 25, 71–79.
Potters J. (1987). Linear optimization games. In: Peters H. and Vrieze O. (eds.),Surveys in games theory and related topics. CWI Tract, 251–276.
Potters J., Curiel I. and Tijs S. (1992). Traveling salesman games.Mathematical Programming 53, 199–211.
Potters J. and Sudhölter P. (1999). Airport problems and consistent allocation rules.Mathematical Social Sciences 38, 83–102.
Prim R. (1957). Shortest connection networks and some generalizations.Bell Systems Technical Journal 36, 1389–1401.
Quint T. (1991a). Characterization of cores of assignment games.International Journal of Game Theory 19, 413–420.
Quint T. (1991b). The core of anm-sided marching game.Games and Economic Behavior 3, 487–503.
Quint T. (1996). On one-sided versus two-sided matching markets.Games and Economic Behavior 16, 124–134.
Reijnierse J., Maschler M., Potters J. and Tijs S. (1996). Simple flow games.Games and Economic Behavior 16, 238–260.
Roth A. and Sotomayor M. (1989).Two sided matching: a study in game theoretic modeling and analyses. Econometric Society Monograph Series, Cambridge University Press.
Samet D. and Zemel E. (1984). On the core and the dual set of linear programming games.Mathematics of Operations Research 9, 309–316.
Sánchez-Soriano J., Llorca N., Tijs S. and Timmer J. (2000). On the core of semi-infinite transportation games with divisible goods. CentER Discussion Paper 2000-89, Tilburg University, Tilburg, The Netherlands. (To appear inEuropean Journal of Operations Research).
Sánchez-Soriano J., López M. and Garcia-Jurado I. (2001). On the core of transportation games.Mathematical Social Sciences 41, 215–225.
Sandsmark M. (1999). Production games under uncertainty.Computational Economics 14, 237–253.
Sasaki H. (1995). Consistency and monotonicity in assignment problems.International Journal of Game Theory 24, 373–397.
Schmeidler D. (1969). The nucleolus of a characteristic function game.SIAM Journal of Applied Mathematics 17, 1163–1170.
Shapley L. (1953). A value forn-person games. In: Kuhn H. and Tucker A. (eds.)Contributions to the theory of games II. Annals of Mathematics Studies, 28. Princeton University Press.
Shapley L. and Shubik M. (1967). Ownership and the production function.Journal of Economics 8, 88–111.
Shapley L. and Shubik M. (1971). The assignment game I: the core.International Journal of Game Theory 1, 111–130.
Slikker M., Fransoo J. and Wouters M. (2001). Joint ordering in multiple news-vendor problems: a game-theoretical approach. Mimeo, Technische Universteit Eindhoven, Eindhoven, The Netherlands.
Slikker M. and Nouweland A. van den (2001).Social and economic networks in cooperative game theory. Kluwer Academic Publishers.
Smith W. (1956). Various optimizers for single-stage production.Naval Research Logistics Quarterly 3, 59–66.
Solymosi T., Aarts H. and Driessen T. (1998). On computing the nucleolus of a balanced connection game.Mathematics of Operations Research 23, 983–1009.
Solymosi T. and Raghavan T. (1994). An algorithm for finding the nucleolus of assignment games.International Journal of Game Theory 23, 119–143.
Solymosi T. and Raghavan T. (2000), Stability of the core of assignment games. University of Economic Sciences and Public Administration Budapest, Budapest, Hungary.
Sprumont Y. (1990). Population monotonic allocation schemes for cooperative games with transferable utility.Games and Economic Behavior 2, 378–394.
Sprumont Y. (1998). Ordinal cost sharing.Journal of Economic Theory 81, 126–162.
Suijs J. (2000).Cooperative decision-making under risk. Kluwer Academic Publishers.
Suijs J. (2001). Cost allocation in spanning network enterprises with stochastic connection costs. Technical Report, Tilburg University, Tilburg, The Netherlands.
Suijs J., Borm P., Hamers H., Koster M. and Quant M. (2001). Communication and cooperation in public network situations. CentER Discussion Paper 2001-44. Tilburg University, Tilburg, The Netherlands.
Suijs J., Hamers H. and Tijs S. (1997). On consistency of reward allocation rules in sequencing situations. In: Klein Haneveld W., Vrieze O. and Kallenberg L. (eds.),Ten years LNMB. CWI Tract, 223–232.
Tamir, A. (1989). On the core of traveling salesman cost allocation game.Operations Research Letters 8, 31–34.
Tersine R. (1994).Principles of inventory and materials management. Elsevier North Holland.
Tijs S., Meca A. and López M. (2000). Benefit sharing in holding situations. CIO Discussion Paper I-2000-01, Universidad Miguel Hernández, Elche, Spain.
Tijs S., Parthasarathy T., Potters J. and Rajendra Prasad V. (1984). Permutation games: another class of totally balanced games.OR Spektrum 6, 119–123.
Tijs S., Timmer J., Llorca N. and Sánchez-Soriano J. (2001). The Owen set and the core of semi-infinite linear production situations. In: Goberna M. and López M. (eds.),Semi-infinite programming: recent advances. Kluwer, 365–386.
Timmer J. (2001). Cooperative behaviour, uncertainty and operations research. PhD thesis, Tilburg University, Tilburg, The Netherlands.
Timmer J., Borm P. and Suijs J. (2000a). Linear transformation of products: games and economies.Journal of Optimization Theory and Applications 105, 677–706.
Timmer J., Llorca N., Tijs S. (2000b). Games arising from infinite production situations.International Game Theory Review 2, 97–106.
Velzen B. van and Hamers H. (2001). On the balancedness of one player relaxed sequencing games. Technical Report, Tilburg University, Tilburg, The Netherlands.
Voorneveld M. and Grahn S. (2000). Cost allocation in shortest path games. Preprint 1142, Department of Mathematics, Utrecht University, Utrecht, The Netherlands.
Young H. (1998). Distributive Justice in Taxation.Journal of Economic Theory 48, 321–335.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Borm, P., Hamers, H. & Hendrickx, R. Operations research games: A survey. Top 9, 139–199 (2001). https://doi.org/10.1007/BF02579075
Issue Date:
DOI: https://doi.org/10.1007/BF02579075