On Covering Codes and Upper Bounds for the Dimension of Simple Games

Martin OlsenAAAI 2017 · DOI

Abstract

Simple games model collective decision-making processes where coalitions of players are either winning or losing. The dimension of such a game is the minimum number of weighted voting rules required to represent it. This paper establishes a novel connection between game theory and binary covering codes, significantly tightening the theoretical upper bound on game dimension. By providing a constructive algorithm, the author reduces the gap between known lower and upper bounds from a factor of $n$ to roughly $\sqrt{n}$, offering a more efficient framework for representing complex multi-agent systems.

Introduction

In the study of multi-agent systems and cooperative game theory, "simple games" are used to model scenarios where a subset of players (a coalition) either succeeds or fails in a collective action—much like a bill passing in a legislature. While some simple games are "weighted" (where each player has a weight and a quota must be met), many real-world systems are more complex. However, a fundamental result in the field is that any simple game can be expressed as the intersection of a finite number of weighted games.

The dimension of a simple game is defined as the minimum number of weighted games needed for this intersection. This metric is critical for computational efficiency; a low dimension implies that the decision procedure is easy to store and execute, whereas a high dimension makes the system unwieldy. For decades, the best-known upper bound was the Taylor-Zwicker bound, which has long been considered loose. This research seeks to close this "dimensionality gap" by introducing tighter upper bounds derived from coding theory.

Methodology: Bridging Game Theory and Coding Theory

The paper introduces a novel constructive algorithm that utilizes Binary Covering Codes to decompose a simple game into its constituent weighted games.

The Connection to Covering Codes

A binary covering code of radius 1 is a collection of bit vectors (representing coalitions) such that every possible coalition is at most one "flip" (Hamming distance 1) away from a member of the code. The author identifies that the problem of representing a game is essentially a covering problem within a Boolean hypercube.

The Decomposition Algorithm

The proposed algorithm follows three primary steps:

  1. Identify Maximal Losing Coalitions: Extract the set of all "maximal losing coalitions" ($L^M$) of the game. These coalitions form a "Sperner family," meaning no coalition in the set is a subset of another.
  2. Partitioning: Use a covering code to partition $L^M$ into smaller, manageable subsets.
  3. Representation: The author proves that each subset in this partition can be represented by a single weighted game.

Consequently, the total dimension of the game is bounded by the size of the covering code ($K_n$). The paper further refines this for specific structures using SECDED (Single Error Correction, Double Error Detection) codes.

Key Results

The primary theoretical contribution is the proof that the dimension $d_n$ is bounded by the minimum cardinality of a binary covering code of length $n$ and radius 1 ($d_n \leq K_n$). This leads to specific improvements:

  • For $n = 2^m - 1$, $d_n \leq 2^n / (n+1)$.
  • For $n = 2^m$, $d_n \leq 2^n / n$.

Quantitatively, the improvement is substantial. For a game with 15 players, the previous Taylor-Zwicker upper bound was 6,434. The new bound established in this work is 2,048—a reduction of nearly 70%.

Comparison of lower and upper bounds for the dimension of simple games for $n=6$ to $15$.

As shown in the table above, the new upper bounds consistently outperform the traditional Taylor-Zwicker bounds (rightmost column), effectively narrowing the gap between the theoretical minimum (lower bound) and maximum (upper bound) dimensions. The gap was reduced from a factor of $n$ to a factor of approximately $\ln n / \sqrt{n}$.

Discussion and Future Work

While the use of standard binary covering codes provides a significant leap forward, the author notes that this "one size fits all" approach may still be improved. The current method does not fully exploit the specific internal geometry of a particular game's maximal losing coalitions.

Future research directions include:

  • Smarter Decompositions: Developing partitioning strategies that are tailored to the specific structure of $L^M$ rather than relying on general covering codes.
  • Closing the Dimensionality Gap: There remains a $\sqrt{n}$ factor gap between the lower and upper bounds. Further investigation into the combinatorial properties of Sperner families in this context may eventually close this gap entirely.

Summary updated

BibTeX
@inproceedings{olsen2017covering,
  author = {Martin Olsen},
  title = {{On Covering Codes and Upper Bounds for the Dimension of Simple Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10572},
}
Figure