Approximations of pseudo-Boolean functions; applications to game theory. (English) Zbl 0778.41009

Hammer, P. L.; Holzman, R.

Z. Oper. Res. 36, No. 1, 3-21 (1992).

The authors characterize the best linear and low-degree polynomial approximations to a real valued function on \(\{0,1\}^ n\) and relate this to the Banzhaf power index and Shapley value in game theory.

Reviewer: K.H.Kim (Montgomery)

MSC:

41A45	Approximation by arbitrary linear expressions
91A12	Cooperative games
06E30	Boolean functions

Keywords:

Banzhaf power index; Shapley value

References:

[1]	Banzhaf JF III (1965) Weighted voting doesn’t work: A mathematical analysis. Rutgers Law Review 19:317–343
[2]	Charnes A, Golany B, Keane M, Rousseau J (1985) Extremal principle solutions of games in characteristic function form: Core, Chebychev and Shapley value generalizations. Report CCS 526. The Center for Cybernetic Studies, University of Texas, Austin · Zbl 0631.90095
[3]	Coleman RP (1961) Orthogonal functions for the logical design of switching circuits. IRE Trans EC 10:379–383 · doi:10.1109/TEC.1961.5219225
[4]	Hammer PL, Hansen P, Simeone B (1984) Roof duality, complementation and persistency in quadratic 0–1 optimization. Math Progr 28:121–155 · Zbl 0574.90066 · doi:10.1007/BF02612354
[5]	Hammer PL, Rudeanu S (1968) Boolean methods in operations research and related areas. Springer, Berlin Heidelberg New York · Zbl 0155.28001
[6]	Kaplan KR, Winder RO (1965) Chebyshev approximation and threshold functions. IEEE Trans EC 14:250–252 · Zbl 0149.12304
[7]	Owen G (1972) Multilinear extensions of games. Management Science 18:P64-P79 · Zbl 0239.90049 · doi:10.1287/mnsc.18.5.64
[8]	Shafer G (1976) A mathematical theory of evidence. Princeton University Press, Princeton · Zbl 0359.62002
[9]	Shapley LS (1953) A value forn-person games. In: Kuhn HW, Tucker AW (eds) Contributions to the theory of games II. Princeton University Press, Princeton