Computing the Proportional Veto Core

Egor Ianovski, Aleksei Y. KondratevAAAI 2021 · DOI

Abstract

The proportional veto core is a social choice concept that protects minority groups by granting them veto power proportional to their size. While theoretically appealing, computing the core has historically been an exponential-time task. This paper presents the first polynomial-time algorithm for this problem, utilizing a reduction to maximum flow. We also introduce "veto by consumption," a novel selection rule for picking a single winner from the core, and demonstrate that the core is typically large under standard preference models. Finally, we show that strategic manipulation is computationally feasible for certain voter types.

Introduction

In collective decision-making, majority-rule systems like plurality voting can lead to the "tyranny of the majority," where the preferences of significant minority groups are entirely ignored. Veto-based rules provide a safeguard by allowing groups to block candidates they find unacceptable. The proportional veto core is a formalization of this idea: a coalition of size $k$ out of $n$ voters can veto up to $\lfloor k \cdot m / n \rfloor$ candidates. A candidate belongs to the core if no coalition has both the power and the incentive to block them.

Algorithmic Contributions

The primary hurdle for the proportional veto core has been its computational complexity. A naive approach requires checking all $2^n$ possible coalitions. The authors overcome this by reducing the core membership test to a maximum flow problem in a bipartite graph. By representing voters and candidates as nodes with specific capacities, the algorithm can determine if a candidate is in the core in $O(\max(n^3, m^3))$ time. For $m$ candidates, the total complexity to find the entire core is $O(m \max(n^3, m^3))$.

To address the issue of the core containing multiple candidates, the authors propose veto by consumption. In this mechanism, candidates have a unit capacity, and voters "consume" their least-preferred candidates at a uniform rate. The last candidate to be fully consumed is declared the winner. This rule is both fair and neutral, ensuring a single outcome from the core.

Empirical Findings

Using synthetic data generated under the Impartial Culture (IC) model, the authors analyzed the properties of the core. A key finding is that the core is remarkably large, often encompassing a significant portion of the candidate set.

Average size of the proportional veto core relative to the number of candidates $m$ for various voter counts $n$.

As shown in Figure 1, the core size relative to $m$ remains substantial even as the number of voters and candidates increases, often exceeding 50% of the available candidates. This empirical evidence underscores the necessity of a secondary selection rule like "veto by consumption" to reach a final decision.

Strategic Considerations

The paper also investigates the susceptibility of the proportional veto core to strategic manipulation. They focus on "pessimistic" manipulators—voters who aim to improve the worst-case outcome within the core. The authors prove that such voters can compute their optimal strategy in polynomial time. While this indicates the rule is not strategy-proof, it provides a clear understanding of the computational bounds of strategic behavior in this context.

Conclusion

By providing efficient algorithms for computation and selection, this work moves the proportional veto core from a theoretical concept to a practical tool for fair group decision-making. Future research may explore the axiomatic properties of "veto by consumption" and extend manipulation analysis to other voter profiles, such as "optimistic" manipulators who focus on the best-case outcome in the core.

Summary updated

BibTeX
@inproceedings{ianovski2021computing,
  author = {Egor Ianovski and Aleksei Y. Kondratev},
  title = {{Computing the Proportional Veto Core}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16691},
}
Figure