Premium
Activity selection games and the minimum‐cut problem
Author(s) -
Topkis Donald M.
Publication year - 1983
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230130106
Subject(s) - mathematical optimization , core (optical fiber) , selection (genetic algorithm) , context (archaeology) , monotonic function , stochastic game , mathematics , shapley value , function (biology) , mathematical economics , regular polygon , value (mathematics) , computer science , game theory , artificial intelligence , evolutionary biology , biology , telecommunications , paleontology , mathematical analysis , statistics , geometry
The connection between the minimum‐cut problem in a capacitated network and certain combinatorial problems is well‐known. This article presents and analyzes a selection problem in the context of a cooperative game, with emphasis on the key role of associated minimum‐cut problems. Each coalition selects economic activities from private activities available to its members and public activities available to all coalitions. For each coalition, a minimum‐cut problem finds an optimal selection and the value of the characteristic function. The game is a convex game. Applying the Greedy Algorithm involves solving n minimum‐cut problems, where n is the number of players. The solution of n minimum‐cut problem determines whether a proposed payoff vector is in the core. An optimal selection of activities varies monotonically with the coalition membership and with the value of each activity. The Shapley value and each extreme point of the core vary monotonically with the value of each activity.