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:
- Social Welfare:
- Utilitarian (USW): Maximizing the total utility across both communities.
- Egalitarian (ESW): Maximizing the utility of the least-satisfied community.
- Nash (NSW): Maximizing the product of utilities.
- 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.
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.
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