Abstract
Many important values for cooperative games are known to arise from least square optimization problems. The present investigation develops an optimization framework to explain and clarify this phenomenon in a general setting. The main result shows that every linear value results from some least square approximation problem and that, conversely, every least square approximation problem with linear constraints yields a linear value. This approach includes and extends previous results on so-called least square values and semivalues in the literature. In particular, it is demonstrated how known explicit formulas for solutions under additional assumptions easily follow from the general results presented here.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
References
Banzhaf, J.F.: Weighted voting does not work: a mathematical analysis. Rutgers Law Rev. 19, 317–343 (1965)
Charnes, A., Golany, B., Keane, M., Rousseau, J.: Extremal principle solutions of games in characteristic function form: core, Chebychev and Shapley value generalizations. In: Sengupta, J.K., Kadekodi, G.K. (eds.) Econometrics of Planning and Efficiency, pp. 123–133. Kluwer Academic Publisher (1988)
Derks, J., Haller, H., Peters, H.: The selectope for cooperative games. Int. J. Game Theory 29, 23–38 (2000)
Ding, G., Lax, R., Chen, J., Chen, P., Marx, B.: Transforms of pseudo-Boolean random variables. Discrete Appl. Math. 158, 13–24 (2010)
Faigle, U., Kern, W., Still, G.: Algorithmic Principles of Mathematical Programming. Springer, Dordrecht (2002)
Faigle, U., Voss, J.: A system-theoretic model for cooperation, interaction and allocation. Discrete Appl. Math. 159, 1736–1750 (2011)
Grabisch, M.: Set Functions, Games and Capacities in Decision Making. Theory and Decision Library C, vol. 46, Springer (2016)
Grabisch, M., Labreuche, C.: Fuzzy measures and integrals in MCDA. In: Figueira, J., Greco, S., Ehrgott, M. (eds.) Multiple Criteria Decision Analysis, pp. 563–608. Kluwer Academic Publishers (2005)
Grabisch, M., Marichal, J.-L., Roubens, M.: Equivalent representations of set functions. Math. Oper. Res. 25(2), 157–178 (2000)
Hammer, P.L., Holzman, R.: On approximations of pseudo-Boolean functions. RUTCOR Research Report RRR 29–87. State University of New Jersey (1987)
Hammer, P.L., Holzman, R.: On approximations of pseudo-Boolean functions. ZOR—Methods Models Oper. Res. 36, 3–21 (1992)
Hammer, P.L., Rudeanu, S.: Boolean Methods in Operations Research and Related Areas. Springer, Berlin (1968)
Kultti, K., Salonen, H.: Minimum norm solutions for cooperative games. Int. J. Game Theory 35, 591–602 (2007)
Marichal, J.-L., Mathonet, P.: Weighted Banzhaf power and interaction indexes through weighted approximations of games. Eur. J. Oper. Res. 211, 352–358 (2011)
Peleg, B., Sudhölter, P.: Introduction to the Theory of Cooperative Games. Kluwer Academic Publisher (2003)
Ruiz, L.M., Valenciano, F., Zarzuelo, J.M.: The family of least-square values for transferable utility games. Games Econ. Behav. 24, 109–130 (1998)
Ruiz, L.M., Valenciano, F., Zarzuelo, J.M.: Some new results on least square values for TU games. TOP 6, 139–158 (1998)
Schmeidler, D.: Subjective probability and expected utility without additivity. Econometrica 57(3), 571–587 (1989)
Shapley, L.S.: A value for \(n\)-person games. In: Kuhn, H.W., Tucker, A.W. (eds.) Contributions to the Theory of Games, Vol. II, Number 28 in Annals of Mathematics Studies, pp. 307–317. Princeton University Press (1953)
Sun, H., Hao, Z., Xu, G.: Optimal Solutions for TU-Games with Decision Approach. Preprint, Northwestern Polytechnical University, Xi’an, Shaanxi, China (2013)
Tanino, T.: One-point solutions obtained from best approximation problems for cooperative games. Kybernetika 49, 395–403 (2013)
Weber, R.J.: Probabilistic values for games. In: Roth, A.E. (ed.) The Shapley Value, pp. 101–120. Cambridge University Press, Cambridge (1988)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Faigle, U., Grabisch, M. (2020). Least Square Approximations and Linear Values of Cooperative Games. In: Nguyen, H., Kreinovich, V. (eds) Algebraic Techniques and Their Use in Describing and Processing Uncertainty. Studies in Computational Intelligence, vol 878. Springer, Cham. https://doi.org/10.1007/978-3-030-38565-1_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-38565-1_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-38564-4
Online ISBN: 978-3-030-38565-1
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)