An Ordinal Banzhaf Index for Social Ranking

Hossein Khani, Stefano Moretti, Meltem ÖztürkIJCAI 2019 · DOI

TL;DR

This paper introduces a novel "ordinal Banzhaf index" to rank individuals based on a ranked list of coalitions they can form. This new method extends traditional game theory power indices to situations where only the relative order of coalition "strength" is known, not precise numerical values. The authors demonstrate its theoretical properties and compare it to existing social ranking methods.

What Problem Does This Paper Address?

In many real-world scenarios, we have a clear understanding of which combinations of individuals (coalitions) are more influential or effective than others, but quantifying their exact "power" is difficult due to complexity, missing data, or imprecision. Traditional game theory power indices, like the Banzhaf and Shapley values, rely on precise numerical assessments of coalition "worth." This paper tackles the challenge of deriving a social ranking of individuals when only ordinal information about coalition preferences is available. Essentially, it asks: "Given a ranked list of all possible groups of people, how do we rank the individuals themselves?"

Methods

The core contribution is the development of an ordinal Banzhaf index. This is achieved by adapting the game-theoretic concepts of marginal contribution and the Banzhaf index to an ordinal framework.

  • Ordinal Marginal Contribution: Instead of calculating the exact change in a coalition's value when an individual joins, they define an ordinal marginal contribution. This is simply +1 if adding an individual to a coalition makes it "better" (according to the given power relation), -1 if it makes it "worse," and 0 if there's no change in rank.
  • Ordinal Banzhaf Score: This score is derived by summing the ordinal marginal contributions of an individual across all possible coalitions they could join.
  • Ordinal Banzhaf Relation: This relation defines the social ranking. Individual i is ranked higher than or equal to individual j if i's ordinal Banzhaf score is greater than or equal to j's.

The authors also provide an axiomatic characterization of this ordinal Banzhaf solution, defining properties like Coalitional Anonymity (CA), Neutrality (N), and Monotonicity (M) that the solution satisfies. They compare these axioms and the resulting ranking to the "Ceteris Paribus (CP) majority" solution, another approach to ordinal social ranking.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and axiomatic characterization, using illustrative examples rather than empirical datasets.

Key Insights and Ideas

  • Bridging Ordinal and Cardinal Power: The paper successfully bridges the gap between ordinal preference information (ranking of coalitions) and cardinal power indices (like Banzhaf) by creating an ordinal equivalent. This is crucial for practical applications where precise numerical values are elusive.
  • Robustness to Cardinalization: A key insight is that the ordinal Banzhaf solution is robust. Unlike cardinal Banzhaf values, which can fluctuate wildly with small changes in numerical assignments, the ordinal version relies solely on the relative order of coalitions, making it more stable in uncertain environments.
  • Axiomatic Foundation: The paper provides a strong theoretical foundation by axiomatizing the ordinal Banzhaf solution. This helps to understand its fundamental properties and its relationship to other social choice concepts.
  • Comparison with CP-Majority: The comparison with the CP-majority highlights important differences: the ordinal Banzhaf solution always yields a transitive ranking (meaning if A > B and B > C, then A > C), whereas CP-majority does not, and the domains of applicability for their axiomatic characterizations differ.

Key Results

  • The paper defines the ordinal Banzhaf index and the corresponding ordinal Banzhaf relation as a social ranking solution.
  • It is shown that the ordinal Banzhaf solution is transitive for any set of individuals, making it a reliable social ranking.
  • An axiomatic characterization is provided: the ordinal Banzhaf solution is the unique solution satisfying Coalitional Anonymity, Neutrality, and Monotonicity on the domain of linear orders of coalitions.
  • The paper demonstrates that the ordinal Banzhaf solution and the CP-majority solution are special cases of a broader family of weighted majority relations.

Limitations and Future Work

  • Domain Restriction: The axiomatic characterization of the ordinal Banzhaf solution is provided for the domain of linear orders of coalitions. The authors suggest investigating its extension to other families of power relations.
  • Generalization of Semivalues: The paper proposes future work in extending ordinal versions of other game-theoretic concepts, such as the Shapley value, to ordinal settings.
  • Computational Complexity: While the paper focuses on theoretical properties, the computational complexity of calculating the ordinal Banzhaf index for large numbers of individuals and coalitions is not explicitly discussed.

Summary updated

BibTeX
@inproceedings{khani2019ordinal,
  author = {Hossein Khani and Stefano Moretti and Meltem Öztürk},
  title = {{An Ordinal Banzhaf Index for Social Ranking}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/54},
}
Figure