Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-12-04T09:14:03.330Z Has data issue: false hasContentIssue false
  • English
  • Français

Bounds for Owen's Multilinear Extension

Part of: Operations research and management science Game theory Mathematical economics

Published online by Cambridge University Press:  14 July 2016

Josep Freixas
Josep Freixas*
Affiliation:
Engineering School of Manresa and Technical University of Catalonia
*
∗Postal address: Department of Applied Mathematics 3, Engineering School of Manresa, Av. Bases de Manresa 61-73, E-08242 Manresa, Spain. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Owen's multilinear extension (MLE) of a game is a very important tool in game theory and particularly in the field of simple games. Among other applications it serves to efficiently compute several solution concepts. In this paper we provide bounds for the MLE. Apart from its self-contained theoretical interest, the bounds offer the means in voting system studies of approximating the probability that a proposal is approved in a particular simple game having a complex component arrangement. The practical interest of the bounds is that they can be useful for simple games having a tedious MLE to evaluate exactly, but whose minimal winning coalitions and minimal blocking coalitions can be determined by inspection. Such simple games are quite numerous.

Keywords

Simple gamesOwen's multilinear extensionboundsapproximations

MSC classification

Secondary: 91A12: Cooperative games 90B50: Management decision making, including multiple objectives 90C59: Approximation methods and heuristics 91B12: Voting theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 44 , Issue 4 , December 2007 , pp. 852 - 864
Copyright
Copyright © Applied Probability Trust 2007 

References

[1] Carreras, F. (2004). α-decisiveness in simple games. Theory Decision 56, 77–91.Google Scholar
[2] Carreras, F. (2005). A decisiveness index for simple games. Europ. J. Operat. Res. 163, 370–387.Google Scholar
[3] Carreras, F. and Freixas, J. (1996). Complete simple games. Math. Social Sci. 32, 139–155.CrossRefGoogle Scholar
[4] Carreras, F. and Freixas, J. (1999). Some theoretical reasons for using regular semivalues. In Logic, Game Theory and Social Choice (Proc. Internat. Conf. LGS), Tilburg, The Netherlands, pp. 140–154.Google Scholar
[5] Coleman, J. S. (1971). Control of collectivities and the power of a collectivity to act. In Social Choice, ed. Lieberman, B., Gordon and Breach, New York, pp. 269–300.Google Scholar
[6] Dubey, P. and Shapley, L. S. (1979). Mathematical properties of the Banzhaf power index. Math. Operat. Res. 4, 99–131.CrossRefGoogle Scholar
[7] Dubey, P., Neyman, P. and Weber, R. J. (1981). Value theory without efficiency. Math. Operat. Res. 6, 122–128.Google Scholar
[8] Felsenthal, D. S. and Machover, M. (1998). The Measurement of Voting Power. Theory and Practice, Problems and Paradoxes. Edward Elgar, Cheltenham.CrossRefGoogle Scholar
[9] Freixas, J. and Pons, M. (2005). Two measures of circumstantial power: influences and bribes. Homo Oeconomicus 22, 569–588.Google Scholar
[10] Freixas, J. and Pons, M. (2008). Circumstantial power: optimal persuadable voters. Europ. J. Operat. Res. 186, 1114–1126.CrossRefGoogle Scholar
[11] Freixas, J. and Puente, M. A. (2002). Reliability importance of the components in a system based on semivalues and probabilistic values. Ann. Operat. Res. 109, 331–342.Google Scholar
[12] Hammer, P. L. and Holzman, R. (1992). Approximations of pseudoboolean functions; applications to game theory. Z. Operat. Res. 36, 3–21.Google Scholar
[13] Isbell, J. R. (1956). A class of majority games. Quart. J. Math. Oxford Ser. 7, 183–187.CrossRefGoogle Scholar
[14] Laruelle, A. and Valenciano, F. (2005). A critical reappraisal of some voting power paradoxes. Public Choice, 125, 17–41.Google Scholar
[15] Laruelle, A., Martı´nez, R. and Valenciano, F. (2006). Success versus decisiveness, conceptual discussion and case study. J. Theoret. Politics 18, 185–205.Google Scholar
[16] Owen, G. (1972). Multilinear extensions of games. Manag. Sci. 18, 64–79.Google Scholar
[17] Owen, G. (1975). Multilinear extensions and the Banzhaf value. Naval Res. Logistics Quart. 22, 741–750.Google Scholar
[18] Owen, G. (1995). Game Theory, 3rd edn. Academic Press, San Diego, CA.Google Scholar
[19] Shapley, L. S. (1962). Simple games: an outline of the descriptive theory. Behavioral Sci. 7, 59–66.Google Scholar
[20] Straffin, P. D. (1988). The Shapley–Shubik and Banzhaf power indices. In The Shapley Value: Essays in Honor of Lloyd S. Shapley, ed. Roth, A. E., Cambridge University Press, pp. 71–81.CrossRefGoogle Scholar
[21] Taylor, A. D. and Zwicker, W. S. (1999). Simple Games: Desirability Relations, Trading, and Pseudoweightings. Princeton University Press.Google Scholar
[22] Weber, R. J. (1988). Probabilistic values for games. In Contributions to the Theory of Games II, eds Tucker, A. W. and Kuhn, H. W., Princeton University Press, pp. 101–119.Google Scholar