A cost allocation framework for LP and GLP games

• Authors: Mariusz KALETA , Eugeniusz TOCZYŁOWSKI

Title variants

PL

Metaalgorytm alokacji kosztów dla gier LP i GLP

• Languages of publication: EN

Abstracts

EN

Cost allocation problems within the GLPG class of games (Generalized Linear Programming Games) are considered in this paper. We assume that a group of agents participate in a common project and each agent defines his requirements for his expected benefit resulting from the project. Then, the joint cost of the project must be allocated amongst the agents in order to satisfy a set of required properties

PL

Rozważono zagadnienie alokacji kosztów w ramach klasy problemów modelowanych jako GLPG (Generalized Linear Programming Games) – uogólnione gry kooperatywne bazujące na zadaniach programowania liniowego. Zakładamy, że grupa agentów uczestniczy we wspólnym przedsięwzięciu, a każdy agent określa pewne wymagania związane z jego uczestnictwem. Wówczas pojawia się problem podziału łącznych kosztów realizacji przedsięwzięcia na każdego z uczestniczących agentów przy zapewnieniu zdefiniowanych ograniczeń tych agentów. W artykule sformułowano ogólny szkielet algorytmu do wyznaczania alokacji łącznych kosztów, oparty na klasie metod alokacji generowanych przez tzw. ścieżki. Proponowane podejście jest uogólnieniem pewnych ważnych mechanizmów alokacji, bazujących na teorii gier kooperatywnych, w tym na wycenie Aummana–Shapleya. Zgodnie z naszą wiedzą dotychczas nie został opracowany żaden wydajny algorytm umożliwiający wyznaczanie alokacji dla problemów modelowanych jako gry kooperatywne bazujące na programowaniu liniowym (LPG i GLPG). Spotykane w literaturze podejścia polegają na obliczeniach niedokładnych przy jednocześnie wymaganym większym nakładzie obliczeniowym.

Keywords

EN

cost allocation; cooperative games; linear programming game

• Publisher: Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
• Journal: Operations Research and Decisions
• Year: 2009
• Volume: 19
• Issue: 4
• Pages: 27-46

Contributors

author

Mariusz KALETA

• Warsaw University of Technology, Institute of Control and Computation Engineering, ul. Nowowiejska 15/19, 00-665 Warsaw, Poland

author

Eugeniusz TOCZYŁOWSKI

• Warsaw University of Technology, Institute of Control and Computation Engineering, ul. Nowowiejska 15/19, 00-665 Warsaw, Poland

References

• AADLAND D.D., KOLPIN V., Shared irrigation costs: en empirical and axiomatic analysis, Mathematical Social Sciences, 1998, Vol. 35, No. 2, 203–218.
• AUMANN R.J, SHAPLEY L.S., Values of Non-Atomic Games, Princeton University Press, 1974.
• CHAMPSAUR P., How to share the cost of a public good? Int. J. Game Theory, 1975, Vol. 4, No.3, 113–129.
• CHEN X., ZHANG J., A stochastic programming duality approach to inventory centralization games, Operations Research, 2009, Vol. 57, No. 4.
• CLARKE D., SHENKER S., ZHANG L., Supporting real-time applications in an integrated services packet network: Architecture and mechanism, Comput. Comm. Rev., 1992, Vol. 22, No. 4, 14–26.
• FARIA E., BARROSO L. A., KELMAN R., GENVILLE S., PEREIRA M.V., ILIADIS N., Allocation of firmenergy rights among hydro agents using cooperative game theory: an Aumann-Shapley approach, Mini-EURO Conference, Operation Research Models and Methods in Energy Sector, 2006, University of Coimbra, Portugal.
• FRIEDMAN E., Paths and consistency in additive cost sharing, International Journal of Game Theory, 2004, Vol. 32, No. 4, 501–518.
• FRIEDMAN E, MOULIN H., Three methods to share joint costs or surplus, Journal of Economic Theory, 1999, Vol. 87, No. 2, 275–312.
• GAMBLE A.B., PAZGAL A.I., A linear programming framework for network games, Center for Mathematical Studies in Economics and Management Science, Discussion Paper No. 1119, 1995, Northwestern University.
• GILLIES D.B., Some theorems on n-person games, Ph.D. thesis, Department of Mathematics, Princeton University, 1953.
• HENRIET D., MOULIN H., Traffic based cost allocation in a network, RAND J. Econ., 1996, Vol. 27, No. 2, 332–345.
• HERZOG S., SHENKER S., ESTRIN D., Sharing the cost of multicast trees: An axiomatic analysis, IEEE ACM Transactions on Networking, 1997, Vol. 5, No. 6, 847–860.
• HOGAN W.W., Contract networks for electricity power transmission, Journal of Regulatory Economics, 1992, Vol. 4, No. 3, 211–242.
• ISRAELSEN D., Collectives, communes, and incentives, J. Compar. Econ., 1980, Vol. 4, 99–124.
• JAMES L.D., LEE R.R., Economics of Water Resource Planning, McGraw-Hill, 1971.
• KALETA M., Selected models and optimization algorithms for local power energy market, Ph.D. Thesis, Institute of Control and Computation Engineering, Warsaw University of Technology, 2004.
• KALETA M., Subsidize-free cost allocation method for infrastructure market game, Proceedings of13th IEEE International Conference on Methods and Models in Automation and Robotics, 2007, 1171–1175.
• KALETA M., TOCZYŁOWSKI E., A method for system constraint cost evaluation on the balancing energy market, Proceedings of APE 2005 XII International Scientific Conference on Present-day Problems of Power Engineering, III, 2005, 163–170.
• KALETA M. TOCZYŁOWSKI E., Parametric analysis of resource cost allocation in market balancing (in Polish), Z. Bubnicki, R. Kulikowski, J. Kacprzyk: XV Krajowa Konferencja Automatyki, III, 2005, 341–346.
• KRUŚ L., BRONISZ P., Cooperative game solution concepts to a cost allocation problem, European Journal of Operational Research, 2000, Vol. 122, No. 2, 258–271.
• LENG M.M., PARLAR M., Game theoretic applications in supply chain management: A review, Infor., 2005, Vol. 43, No. 3, 187–220.
• LIMA J.W.M., Allocation of transmission fixed charges: an overview, IEEE Trans. Power Syst., 1996, Vol. 11, No. 4, 1409–1418.
• LIMA J., PEREIRA M., PEREIRA J., An integrated framework for cost allocation in a multi-owned transmission system, IEEE Trans. Power Syst., 1995, Vol. 10, No. 2, 971–977.
• LOEHMAN E., WHINSTON A., An axiomatic approach for cost allocation of public investement, Public Finanse Quartely, 1974, Vol. 2, No. 2, 236–251.
• MAS-COLELL A., Remarks on the game theoretic analysis of a simple distribution of surplus problem, Int. J. Game Theory, 1980, Vol. 9, No. 3, 125–140.
• MILLS H.D., Marginal values of matrix games and linear programming, Linear Inequalities and Related Systems, 1956, 183–193.
• OWEN G., On the core of linear production games, Mathematical Programming, 1975, Vol. 9, No.1, 358–370.
• RAMSEY F., A contribution to the theory of taxation, Economic Journal, 1927, Vol. 37, No. 45, 47–61.
• ROEMER J., A public ownership resolution of the tragedy of the commons, Tech. Rep. University of California, 1988.
• SAMET D., TAUMAN Y., ZANG I., An application of the Aumann–Shapley prices for cost allocation in transportation problems, Mathematics of Operations Research, 1984, Vol. 9, No. 1, 25–42.
• SCARF H., Notes on the core of a productive economy, Contributions to Mathematical Economics in Honor of Gerard Debreu, North-Holland, 1986.
• SCHMEIDLER D., The nucleous of a characteristic function game, SIAM Journal on Applied Mathematics, 1969, Vol. 17, 1163–1170.
• SEN A., Labour allocation in a cooperative enterprise, Rev. Econ. Stud., 1966, Vol. 33, 361–371.
• SHANG W., VOLIJ O., Transmission investment cost allocation within the cooperative game framework, Proceedings of Power Systems Conference and Exposition (PSCE’06), 2006, 1971–1977.
• SHAPLEY L.S., A value for n-person games, Contributions to the Theory of Games in Annals of Mathematics Studies, II, 1953, No. 28, 307–317.
• SHAPLEY L.S., Cores of convex games, International Journal of Game Theory, 1971, Vol. 1, No. 1, 11–26.
• SHAPLEY L.S., SHUBIK M., The assignment game I: The Core, International Journal of Game Theory, 1971, Vol. 1, No. 1, 111–130.
• SHENKER S., Efficient network allocations with selfish users, Performance, 1990. SHENKER S., Making greed work in networks: A game-theoretic analysis of gateway service disciplines, IEEE ACM Trans. Networking, 1995, Vol. 3, No. 45, 819–831.
• SKORIN-KAPOV D., SKORIN-KAPOV J., Threshold based discounting networks: The cost allocation provided by the nucleolus, European Journal of Operational Research, 2005, Vol. 166, No. 1, 154–159.
• STAMTSIS G.C., ERLICH I. Use of cooperative game theory in power system fixed-cost allocation, IEE Proc.-Gener. Transm. Distrib., 2004, Vol. 151, No. 3.
• TAN X.H., LIE T.T., Allocation of transmission loss cost using cooperative game theory in the context of open transmission access, IEEE, Power Engineering Society Winter Meeting, 2001, 3, 1215–1219.
• TAUMAN Y. The Aumann-Shapley prices: a survey, The Shapley Value: Essays in Honor of Lloyd S. Shapley., Cambridge University Press.
• TOCZYŁOWSKI E., Optimisation of turnover of many commodities linked by resources (in Polish), Zesz. Nauk. Polit. Śląskiej, seria Automatyka, 2000, Vol. 130, 171–179.
• WEBER R., Probabilistic values for games, The Shapley Value, Cambridge University Press, 1988.
• YOUNG H.P., Cost Allocation: Methods, Principles, Applications, Elseviers Science Publishers B.V., 1985.