Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Discrete Applied Mat...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Discrete Applied Mathematics
Article
License: Elsevier Non-Commercial
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Discrete Applied Mathematics
Article . 2000
License: Elsevier Non-Commercial
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Discrete Applied Mathematics
Article . 2000 . Peer-reviewed
License: Elsevier Non-Commercial
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2000
Data sources: zbMATH Open
DBLP
Article
Data sources: DBLP
versions View all 6 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

The influence of variables on pseudo-Boolean functions with applications to game theory and multicriteria decision making

Authors: Marichal, Jean-Luc;

The influence of variables on pseudo-Boolean functions with applications to game theory and multicriteria decision making

Abstract

The paper analyzes situations in which each of \(n\) participants can make a binary (``yes''-``no'') decision \(x_i\), and the outcome \(f(x)\) of these decisions \(x=(x_1,\ldots,x_n)\) is characterized by a real number. The function \(f\) that maps Boolean vectors \(x\) into real numbers is called a pseudo-Boolean function. In such a situation, how can we gauge the influence of a coalition \(S\subseteq\{1,\ldots,n\}\)? For each selection \(x_{-S}\) of decisions \(x_j\), \(j\not\in S\), it is natural to characterize the influence as the width of the interval \(\Delta(x_{-S}) =[\min_{x_S} f(x_S,x_{-S}), \max_{x_S} f(x_S,x_{-S})]\) of possible values of \(f\). If we do not know the decisions of the participants outside \(S\), it is reasonable to consider all these \(2^{n-s}\) possible decisions \(x_{-S}\) and define the influence \(I_f(S)\) of the coalition \(S\) as the arithmetic average of the corresponding widths \(\Delta(x_{-S})\). For a cooperative game in which the decision \(x_i\) is whether to join the coalition or not, the outcome \(f(x)\) can be defined as the guaranteed gain \(v(S)\) corresponding to the resulting coalition \(S=\{i\mid x_i=1\}\); then, the above ``influence'' coincides with the Banzhaf power index. Instead of describing the function \(f\) by its values \(f(x)\), we can describe it by the coefficients \(a(T)\) of its Taylor series expansion \(f(x)=\sum a(T)\cdot \prod_{i\in T}x_i\); these coefficients \(a(T)\) form a Möbius transform of \(f\). It turns out that the influence can be explicitly described in terms of this Möbius transform: \(I_f(S)= \sum_{T\cap S\neq\emptyset}a(T)\cdot 2^{-|T\backslash S|}.\) Every function \(f:\{0,1\}^n\to R\) can be extended to \([0,1]^n\) (e.g., as a multi-linear function). For this extension, we can also define the influence as the average range. The authors show how the resulting influence is related to the influence of the original pseudo-Boolean function. As an interesting practical application, they consider the design of a voting system in which all coalition have influence. It is worth mentioning that from this viewpoint, majority voting is not optimal -- because minority has no influence.

Country
Luxembourg
Keywords

game theory, Management decision making, including multiple objectives, multi-criteria decision making, Applied Mathematics, pseudo-Boolean functions, : Quantitative methods in economics & management [B09] [Business & economic sciences], Power and interaction indices, power and interaction indices, Cooperative games, : Méthodes quantitatives en économie & gestion [B09] [Sciences économiques & de gestion], Multicriteria decision making, multicriteria decision making, : Mathematics [G03] [Physical, chemical, mathematical & earth Sciences], Discrete Mathematics and Combinatorics, : Mathématiques [G03] [Physique, chimie, mathématiques & sciences de la terre], Game theory, Pseudo-Boolean functions

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    63
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
63
Top 10%
Top 10%
Average
Green
hybrid