Byzantine Game Theory: Sun Tzus Boxes

Andrei Constantinescu, Roger Wattenhofer

Abstract

The Byzantine Selection Problem addresses the challenge of selecting a subset of candidates when an adversary can maliciously "empty" or invalidate a fixed number of choices. This paper, published by researchers at ETH Zürich, bridges classical game theory and fault-tolerant distributed computing. It demonstrates that while deterministic strategies are easily defeated by Byzantine actors, randomized strategies provide robust performance guarantees. The authors introduce a linear-time algorithm to compute optimal selection probabilities using a "water-filling" metaphor.

Introduction: The Selection Puzzle

In standard game theory, players are typically assumed to be rational agents seeking to maximize their own utility. However, in distributed computing, systems must often withstand Byzantine actors—participants who may be malicious, broken, or unpredictable, and whose goal is to minimize system performance.

The authors formalize this as a selection problem: an organizer must choose $\ell$ boxes from a set of $n$ boxes, each containing a specific value. A Byzantine adversary, knowing the organizer's strategy, can "empty" up to $t$ of these boxes. If the organizer chooses deterministically and $t \ge \ell$, the adversary can always ensure a reward of zero by targeting the most valuable selections.

An example instance of the selection problem with $n=7$ boxes, where the organizer must pick $\ell=5$ boxes while an adversary can ruin $t=1$ of them.

Methodology: From Probabilities to Water-Filling

To counter the adversary, the organizer must employ a randomized strategy. The paper moves from simple cases to a generalized algorithmic solution through several key steps:

  1. Marginal Probabilities: Instead of dealing with the combinatorial complexity of picking sets of boxes, the authors focus on the marginal probability $p_i$ that any specific box $i$ is included. They prove that any valid set of marginals can be converted into a concrete selection strategy.
  2. The Water-Filling Metaphor: The core of the solution is a physical analogy. Imagine $n$ vessels where each vessel $i$ has a width of $1/v_i$ and a height of $v_i$, resulting in an area of 1. By "pouring" $\ell$ units of probability into these vessels, the goal is to find a "water level" (expected value) that is optimized across the selections.
  3. Two-Pointer Algorithm: The authors developed a linear-time ($O(n)$) algorithm to simulate this process, identifying the optimal distribution that maximizes the worst-case expected reward.
The water-filling metaphor applied to the selection problem, where the optimal strategy involves balancing expected values (represented by the water level E) across a subset of boxes.

Key Results

  • Deterministic Vulnerability: The study proves that deterministic mechanisms fail completely (payoff of 0) whenever the number of faults $t$ meets or exceeds the number of selections $\ell$.
  • Optimal Randomization: The proposed randomized strategy is proven optimal against an "oblivious" adversary—one who knows the strategy but not the specific outcome of the random selection.
  • Computational Efficiency: The optimal marginal probabilities can be computed in $O(n)$ time. If an explicit probability distribution over specific sets is required, it can be derived in $O(n^2)$.

Discussion and Future Work

A primary insight of this work is that randomization serves as a necessary defense mechanism in Byzantine environments, forcing the adversary to spread their attacks and ensuring some value is always preserved. Interestingly, the optimal strategy often involves completely ignoring low-value boxes to avoid "diluting" the probability of selecting high-value ones.

Current limitations include the assumption that the number of faults $t$ is known and that the adversary is oblivious. Future research may extend this "Byzantine lens" to other algorithmic problems, such as the Secretary Problem or stable matching, where participants may act as malicious imposters rather than rational agents.

Summary updated

BibTeX
@inproceedings{constantinescu2025byzantine,
  author = {Andrei Constantinescu and Roger Wattenhofer},
  title = {{Byzantine Game Theory: Sun Tzus Boxes}},
  booktitle = {AAMAS},
  year = {2025},
}
Figure