A Model of Winners Allocation

Yongjie YangAAAI 2021 · DOI

Introduction

Standard multiwinner voting typically focuses on selecting a single committee of $k$ candidates based on voter preferences. However, many real-world scenarios require selecting multiple distinct groups from overlapping candidate pools. This paper introduces a formal model for Winners Allocation, where the objective is to select two disjoint sets of winners (committees) from two potentially overlapping elections.

The Double-Election Model

In the proposed model, we consider two candidate sets $C_1$ and $C_2$ that may intersect. The core constraint is that the final committees $w_1$ and $w_2$ must be disjoint ($w_1 \cap w_2 = \emptyset$). This creates a dependency: selecting a popular candidate for one committee makes them unavailable for the other. This model is applicable to scenarios such as awarding different types of grants to a community, coordinating paper selection between sister conferences, or evaluating program committees.

Fairness and Social Welfare Criteria

The paper evaluates allocations based on two primary frameworks:

  1. Social Welfare:
    • Utilitarian (USW): Maximizing the total utility across both communities.
  2. Egalitarian (ESW): Maximizing the utility of the least-satisfied community.
  3. Nash (NSW): Maximizing the product of utilities.
  4. Envy-Freeness (EF): Ensuring that one community does not prefer the candidates allocated to the other. The study explores several variants, including Protective (PEF) and Replacement (REF) envy-freeness.

The research establishes a clear hierarchy among these properties, illustrating how certain optimality criteria imply others.

Hierarchy of fairness and optimality properties

As shown in Figure 1, an allocation that is optimal for Nash Social Welfare (NSWO) is also Pareto Optimal (PO), which in turn implies Protective Envy-Freeness (PEF).

Computational Complexity

A significant portion of the paper is dedicated to mapping the computational landscape of finding these optimal allocations. The complexity varies significantly depending on the utility function used (e.g., Approval Voting vs. Satisfaction Approval Voting) and the chosen welfare goal.

Key findings include:

  • Utilitarianism is generally tractable: Computing the maximum Utilitarian Social Welfare is polynomial-time solvable for "weakly additive" utility functions using dynamic programming.
  • Egalitarianism and Nash Welfare are often hard: Finding allocations that maximize the minimum utility or the product of utilities is typically NP-hard, even with simple additive utilities.
  • Fixed-Parameter Tractability (FPT): Many hard problems become manageable if the number of total votes is small, regardless of the number of candidates.

The following table summarizes the complexity results across different combinations of utility functions and welfare/fairness goals.

Complexity of finding optimal allocations for various welfare and fairness criteria

Conclusion and Future Work

This work provides a robust theoretical foundation for multi-committee selection under disjointness constraints. While it focuses on approval-based voting and two committees, future research could extend this to ranked preferences or scenarios involving three or more committees. Additionally, integrating modern axiomatic properties like "Justified Representation" into the disjoint-allocation framework remains an open challenge.

Summary updated

BibTeX
@inproceedings{yang2021model,
  author = {Yongjie Yang},
  title = {{A Model of Winners Allocation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16722},
}
Figure