Weighted Banzhaf power and interaction indexes through weighted approximations of games

The Banzhaf power index was introduced in cooperative game theory to measure the real power of players in a game. The Banzhaf interaction index was then proposed to measure the interaction degree inside coalitions of players. It was shown that the power and interaction indexes can be obtained as solutions of a standard least squares approximation problem for pseudo-Boolean functions. Considering certain weighted versions of this approximation problem, we define a class of weighted interaction indexes that generalize the Banzhaf interaction index. We show that these indexes define a subclass of the family of probabilistic interaction indexes and study their most important properties. Finally, we give an interpretation of the Banzhaf and Shapley interaction indexes as centers of mass of this subclass of interaction indexes.     

Approximations of Lovász extensions and their induced interaction index

The Lovász extension of a pseudo-Boolean function f:{0,1}ⁿ→R is defined on each simplex of the standard triangulation of [0,1]ⁿ as the unique affine function that interpolates f at the n+1 vertices of the simplex. Its degree is that of the unique multilinear polynomial that expresses f. In this paper we investigate the least squares approximation problem of an arbitrary Lovász extension by Lovász extensions of (at most) a specified degree. We derive explicit expressions of these approximations. The corresponding approximation problem for pseudo-Boolean functions was investigated by Hammer and Holzman [Approximations of pseudo-Boolean functions; applications to game theory, Z. Oper. Res. 36(1) (1992) 3-21] and then solved explicitly by Grabisch et al. [Equivalent representations of set functions, Math. Oper. Res. 25(2) (2000) 157-178], giving rise to an alternative definition of Banzhaf interaction index. Similarly we introduce a new interaction index from approximations of and we present some of its properties. It turns out that its corresponding power index identifies with the power index introduced by Grabisch and Labreuche [How to improve acts: an alternative representation of the importance of criteria in MCDM, Internat. J. Uncertain. Fuzziness Knowledge-Based Syst. 9(2) (2001) 145-157].     

基于2可加模糊测度的多线性效用函数建模和求解

构建合适的多属性效用函数是多属性效用分析的关键。针对不同偏好假设,文献从可加独立、效用独立、效用依赖等分别进行了多属性效用函数构建的研究。然而,由于求解的复杂性,多属性效用理论的应用绝大部分限于可加效用函数和多乘效用函数。提出一种基于2可加模糊测度的多线性效用函数建模和求解方法。首先,证明多线性效用函数和基于模糊测度的多线性模型之间的等价性,提出利用基于模糊测度的多线性模型对多线性效用函数进行表示。其次,针对多线性模型的特点和模糊测度识别的复杂性,利用Banzhaf交互指数和2可加模糊测度对多线性模型进行表示,并利用最小方法差进行模糊测度和Banzhaf交互指数识别,进而实现多线性效用函数的求解。最后,将方法用于某可穿戴医疗设备基于顾客需求的多属性效用函数构建,确认了可行性。方法为多线性效用函数的求解提供了一种新思路。     

Multilinear extensions and values for multichoice games

We define multilinear extensions for multichoice games and relate them to probabilistic values and semivalues. We apply multilinear extensions to show that the Banzhaf value for a compound multichoice game is not the product of the Banzhaf values of the component games, in contrast to the behavior in simple games. Following Owen (Manag Sci 18:64–79, 1972), we integrate the multilinear extension over a simplex to construct a version of the Shapley value for multichoice games. We compare this new Shapley value to other extensions of the Shapley value to multichoice games. We also show how the probabilistic value (resp. semivalue, Banzhaf value, Shapley value) of a multichoice game is equal to the probabilistic value (resp. semivalue, Banzhaf value, Shapley value) of an appropriately defined TU decomposition game. Finally, we explain how semivalues, probabilistic values, the Banzhaf value, and this Shapley value may be viewed as the probability that a player makes a difference to the outcome of a simple multichoice game.     

Approximations of pseudo-Boolean functions; applications to game theory

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} ⁿ , 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 ²ⁿ . 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).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).     

模糊合作博弈局中人参与水平间相互作用度量

本文基于经典合作博弈局中人间相互作用现象的有关度量方法,针对具有模糊联盟的合作博弈问题,给出了模糊联盟中各局中人参与水平间相互作用的度量方法,定义了水平间相互独立性概念,建立了反映局中人各参与水平间相互作用平均程度的两指标:Shapley相互作用指标及Banzhaf相互作用指标.同时对于具有k-单调性的模糊合作博弈局中人参与水平间的边缘相互作用的有关性质作了进一步研究,得出了一些新的结论.     

An axiomatization of the Banzhaf value for cooperative games on antimatroids

Cooperative games on antimatroids are cooperative games in which coalition formation is restricted by a combinatorial structure which generalizes permission structures. These games group several well-known families of games which have important applications in economics and politics. The current paper establishes axioms that determine the restricted Banzhaf value for cooperative games on antimatroids. The set of given axioms generalizes the axiomatizations given for the Banzhaf permission values. We also give an axomatization of the restricted Banzhaf value for the smaller class of poset antimatroids. Finally, we apply the above results to auction situations.     

On the convergence of random polynomials and multilinear forms

We consider different kinds of convergence of homogeneous polynomials and multilinear forms in random variables. We show that for a variety of complex random variables, the almost sure convergence of the polynomial is equivalent to that of the multilinear form, and to the square summability of the coefficients. Also, we present polynomial Khintchine inequalities for complex gaussian and Steinhaus variables. All these results have no analogues in the real case. Moreover, we study the Lp-convergence of random polynomials and derive certain decoupling inequalities without the usual tetrahedral hypothesis. We also consider convergence on “full subspaces” in the sense of Sjögren, both for real and complex random variables, and relate it to domination properties of the polynomial or the multilinear form, establishing a link with the theory of homogeneous polynomials on Banach spaces.     

The Banzhaf power index for ternary bicooperative games

In this paper we analyze ternary bicooperative games, which are a refinement of the concept of a ternary voting game introduced by Felsenthal and Machover. Furthermore, majority voting rules based on the difference of votes are simple bicooperative games. First, we define the concepts of the defender and detractor swings for a player. Next, we introduce the Banzhaf power index and the normalized Banzhaf power index. The main result of the paper is an axiomatization of the Banzhaf power index for the class of ternary bicooperative games. Moreover, we study ternary bicooperative games with two lists of weights and compute the Banzhaf power index using generating functions.     

An improvement on the complexity of factoring read-once Boolean functions

Read-once functions have gained recent, renewed interest in the fields of theory and algorithms of Boolean functions, computational learning theory and logic design and verification. In an earlier paper [M.C. Golumbic, A. Mintz, U. Rotics, Factoring and recognition of read-once functions using cographs and normality, and the readability of functions associated with partial k-trees, Discrete Appl. Math. 154 (2006) 1465-1677], we presented the first polynomial-time algorithm for recognizing and factoring read-once functions, based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrence graph is P₄-free.In this note, we improve the complexity bound by showing that the method can be modified slightly, with two crucial observations, to obtain an O(n|f|) implementation, where |f| denotes the length of the DNF expression of a positive Boolean function f, and n is the number of variables in f. The previously stated bound was O(n²k), where k is the number of prime implicants of the function. In both cases, f is assumed to be given as a DNF formula consisting entirely of the prime implicants of the function.     

Complexity of the satisfiability problem for multilinear forms over a finite field

Multilinear forms over finite fields are considered. Multilinear forms over a field are products in which each factor is the sum of variables or elements of this field. Each multilinear form defines a function over this field. A multilinear form is called satisfiable if it represents a nonzero function. We show the N P-completeness of the satisfiability recognition problem for multilinear forms over each finite field of q elements for q ≥ 3. A theorem is proved that distinguishes cases of polynomiality and NP-completeness of the satisfiability recognition problem for multilinear fields for each possible q ≥ 3.     

Gaussian Bounds for Noise Correlation of Functions

In this paper we derive tight bounds on the expected value of products of low influence functions defined on correlated probability spaces. The proofs are based on extending Fourier theory to an arbitrary number of correlated probability spaces, on a generalization of an invariance principle recently obtained with O’Donnell and Oleszkiewicz for multilinear polynomials with low influences and bounded degree and on properties of multi-dimensional Gaussian distributions.     

Derivative and factorization of holomorphic functions

For a holomorphic function f of bounded type on a complex Banach space E, we show that its derivative df:E→E^∗ takes bounded sets into certain families of sets if and only if f may be factored in the form f=g○S, where S is in some associated operator ideal, and g is a holomorphic function of bounded type. We also prove that the multilinear and polynomial mappings factor in an analogous way if and only if they are “K-bounded.”     

On the Complexity of Multivalued Logic Functions over Some Infinite Basis

Under study is the complexity of the realization of k-valued logic functions (k ≥ 3) by logic circuits in the infinite basis consisting of the Post negation (i.e., the function (x + 1) mod k) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function f, we find the lower and upper bounds of complexity, which differ from one another at most by 1 and have the form 3 log₃(d(f)+ 1)+O(1), where d(f) is the maximal number of the decrease of the value of f taken over all increasing chains of tuples of values of the variables. We find the exact value of the corresponding Shannon function which characterizes the complexity of the most complex function of a given number of variables.     

Voting power in the European Union enlargement

The Shapley–Shubik power index in a voting situation depends on the number of orderings in which each player is pivotal. The Banzhaf power index depends on the number of ways in which each voter can effect a swing. If there are n players in a voting situation, then the function which measures the worst case running time for computing these indices is in O(n2ⁿ). We present a combinatorial method based in generating functions to compute these power indices efficiently in weighted double or triple majority games and we study the time complexity of the algorithms. Moreover, we calculate these power indices for the countries in the Council of Ministers of the European Union under the new decision rules prescribed by the Treaty of Nice.     

Determination of a matrix function using the divided difference method of Newton and the interpolation technique of Hermite

Computing a function f(A) of an n-by-n matrix A is a frequently occurring problem in control theory and other applications. In this paper we introduce an effective approach for the determination of matrix function f(A). We propose a new technique which is based on the extension of Newton divided difference and the interpolation technique of Hermite and using the eigenvalues of the given matrix A. The new algorithm is tested on several problems to show the efficiency of the presented method. Finally, the application of this method in control theory is highlighted.     

Geometric properties of the scattering map of a normally hyperbolic invariant manifold

Given a normally hyperbolic invariant manifold Λ for a map f, whose stable and unstable invariant manifolds intersect transversally, we consider its associated scattering map. That is, the map that, given an asymptotic orbit in the past, gives the asymptotic orbit in the future.We show that when f and Λ are symplectic (respectively exact symplectic) then, the scattering map is symplectic (respectively exact symplectic). Furthermore, we show that, in the exact symplectic case, there are extremely easy formulas for the primitive function, which have a variational interpretation as difference of actions.We use this geometric information to obtain efficient perturbative calculations of the scattering map using deformation theory. This perturbation theory generalizes and extends several results already obtained using the Melnikov method. Analogous results are true for Hamiltonian flows. The proofs are obtained by geometrically natural methods and do not involve the use of particular coordinate systems, hence the results can be used to obtain intersection properties of objects of any type.We also reexamine the calculation of the scattering map in a geodesic flow perturbed by a quasi-periodic potential. We show that the geometric theory reproduces the results obtained in [Amadeu Delshams, Rafael de la Llave, Tere M. Seara, Orbits of unbounded energy in quasi-periodic perturbations of geodesic flows, Adv. Math. 202 (1) (2006) 64-188] using methods of fast-slow systems. Moreover, the geometric theory allows to compute perturbatively the dependence on the slow variables, which does not seem to be accessible to the previous methods.     

Transcendental values of class group <Emphasis Type="Italic">L</Emphasis>-functions

Let K be an algebraic number field and f a complex-valued function on the ideal class group of K. Then, f extends in a natural way to the set of all non-zero ideals of the ring of integers of K and we can consider the Dirichlet series \({L(s,f) =\sum_{{\mathfrak a}} f({\mathfrak a}){\bf N}({\mathfrak a})^{-s}}\) which converges for \({{\mathfrak R}(s) >1 }\). After extending this function to \({{\mathfrak R}(s)=1}\), and in the case that f does not contain the trivial character, we study the special value L(1, f) when f is algebraic valued and K is an imaginary quadratic field. Applying Kronecker’s limit formula and Baker’s theory of linear forms in logarithms, we derive a variety of results related to the transcendence of this special value.