Abstract
This paper studies the approximation of pseudo-Boolean functions by linear functions and more generally by functions of (at most) a specified degree. Here a pseudo-Boolean function means a real valued function defined on {0,1}n, and its degree is that of the unique multilinear polynomial that expresses it; linear functions are those of degree at most one. The approximation consists in choosing among all linear functions the one which is closest to a given function, where distance is measured by the Euclidean metric onR 2n. A characterization of the best linear approximation is obtained in terms of the average value of the function and its first derivatives. This leads to an explicit formula for computing the approximation from the polynomial expression of the given function. These results are later generalized to handle approximations of higher degrees, and further results are obtained regarding the interaction of approximations of different degrees. For the linear case, a certain constrained version of the approximation problem is also studied. Special attention is given to some important properties of pseudo-Boolean functions and the extent to which they are preserved in the approximation. A separate section points out the relevance of linear approximations to game theory and shows that the well known Banzhaf power index and Shapley value are obtained as best linear approximations of the game (each in a suitably defined sense).
Zusammenfassung
In dieser Arbeit wird die Approximation Pseudo-Boole'scher Funktionen lineare Funktionen bzw. allgemeiner durch Funktion kleiner/gleich eines festen Grades studiert. Dabei ist eine Pseudo-Boole'sche Funktion eine reellwertige Funktion definiert auf {0,1}n und ihr Grad ist jener des eindeutig bestimmten multilinearen Polynoms, durch die sie dargestellt werden kann. Lineare Funktionen sind jene mit einem Grad kleiner oder gleich Eins. Die Approximation besteht darin, daß unter allen linearen Funktionen jene mit dem kleinsten Euklidischen Abstand inR 2n gewählt wird. Es wird eine Charakterisierung der besten linearen Approximation durch den Mittelwert der Funktion und ihrer ersten Ableitungen angegeben. Sie führt auf eine explizite Formel, um die Approximation aus der Polynomform gegebenen Funktion zu berechnen. Diese Ergebnisse werden später verallgemeinert, um Approximationen höheren Grades zu behandeln. Ferner werden Ergebnisse bezüglich des Zusammenhanges von Approximationen verschiedenen Grades gewonnen. Im linearen Fall wird auch eine im gewissen Sinne eingeschränkte Approximationsaufgabe behandelt. Spezielle Betrachtung wird jenen wichtigen Eigenschaften Pseudo-Boole'scher Funktionen gezollt, die bei der Approximation erhalten bleiben. Ein weiterer Abschnitt zeigt die Relevanz linearer Approximationen in der Spieltheorie auf und zeigt Verbindungen zwischen den hier erzielten Ergebnissen und dem wohlbekannten Banzhaf Index auf.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Banzhaf JF III (1965) Weighted voting doesn't work: A mathematical analysis. Rutgers Law Review 19:317–343
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
Coleman RP (1961) Orthogonal functions for the logical design of switching circuits. IRE Trans EC 10:379–383
Hammer PL, Hansen P, Simeone B (1984) Roof duality, complementation and persistency in quadratic 0–1 optimization. Math Progr 28:121–155
Hammer PL, Rudeanu S (1968) Boolean methods in operations research and related areas. Springer, Berlin Heidelberg New York
Kaplan KR, Winder RO (1965) Chebyshev approximation and threshold functions. IEEE Trans EC 14:250–252
Owen G (1972) Multilinear extensions of games. Management Science 18:P64-P79
Shafer G (1976) A mathematical theory of evidence. Princeton University Press, Princeton
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
Author information
Authors and Affiliations
Additional information
Supported by the Air Force Office of Scientific Research (under grant number AFOSR 89-0512 and AFOSR 90-0008 to Rutgers University), as well as the National Science Foundation (under grant number DMS 89-06870).
Rights and permissions
About this article
Cite this article
Hammer, P.L., Holzman, R. Approximations of pseudo-Boolean functions; applications to game theory. ZOR Zeitschrift für Operations Research Methods and Models of Operations Research 36, 3–21 (1992). https://doi.org/10.1007/BF01541028
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01541028