Parameterized Analysis of Assignment Under Multiple Preferences

Barak Steindl, Meirav Zehavi

Introduction

The classic Assignment Problem involves matching a set of agents to a set of items such that the resulting allocation is Pareto optimal—meaning no agent can be made better off without making another worse off. However, real-world scenarios often involve multiple criteria. For instance, when selecting housing, an agent might rank options based on price, proximity to work, and school quality simultaneously.

In "Parameterized Analysis of Assignment Under Multiple Preferences," Barak Steindl and Meirav Zehavi explore the computational complexity of finding assignments that satisfy optimality across multiple preference "layers." They introduce the concept of $\alpha$-global optimality, where a matching must be Pareto optimal in at least $\alpha$ out of $\ell$ distinct preference layers.

Problem Definition and Methodology

The core challenge lies in determining if a "globally optimal" assignment exists when agents juggle conflicting priority lists. While the single-layer problem is solvable in polynomial time via mechanisms like serial dictatorship, the multi-layered variant quickly becomes NP-hard.

The authors utilize Parameterized Complexity analysis to identify which variables—such as the number of agents ($n$), items ($m$), or layers ($\ell$)—govern the problem's tractability. Key methodological components include:

  • Serial Dictatorship Mapping: Leveraging the fact that every Pareto optimal assignment corresponds to some permutation of agents, the search space can be bounded by $n!$.
  • Trading Graphs: To verify optimality within a specific layer, the authors construct directed graphs. A matching is Pareto optimal if and only if its corresponding trading graph contains no cycles, indicating no mutually beneficial swaps are possible.
Figure 1: A trading graph used to verify Pareto optimality by checking for cycles among agents and items.
  • Kernelization: The researchers developed data reduction rules to compress large instances into smaller "kernels," facilitating more efficient computation.

Key Insights

A pivotal discovery is the "Top-$n$" Rule: in any Pareto optimal assignment, an agent will receive either nothing or one of their top $n$ preferred items. This observation allows for significant pruning of preference lists, leading to a polynomial kernel of size $O(\ell n^2)$.

The analysis reveals a stark contrast in difficulty based on the parameter chosen. If the number of agents ($n$) is small, the problem is Fixed-Parameter Tractable (FPT). Conversely, if the number of items ($m$) is small but the number of layers is large, the problem remains W[1]-hard, suggesting no efficient general solution exists for these cases.

Results and Complexity Landscape

The paper provides a comprehensive taxonomy of the problem's complexity across various parameter combinations. Notably, finding an $\alpha$-globally optimal assignment is FPT with respect to $n$, and the authors prove that their $O^*(n!)$ algorithm is near-optimal under the Exponential Time Hypothesis (ETH).

Extracted table from page 4 of Parameterized Analysis of Assignment Under Multiple Preferences

Conclusion and Future Directions

While this work maps the theoretical boundaries of multi-preference assignments, several avenues remain open. Future research could explore weighted preference layers, where certain criteria carry more significance, or shift from a decision-based approach to an optimization one that maximizes the number of optimal layers. Additionally, investigating the existence of smaller kernels for parameters like $m + \ell$ remains a significant open question in the field.

Summary updated

Abstract

The Assignment problem is a fundamental and well-studied problem in the intersection of Social Choice, Computational Economics and Discrete Allocation. In the Assignment problem, a group of agents expresses preferences over a set of items, and the task is to find a pareto optimal allocation of items to agents. We introduce a generalized version of this problem, where each agent is equipped with multiple incomplete preference lists: each list (called a layer) is a ranking of items in a possibly different way according to a different criterion. We introduce the concept of global optimality, which extends the notion of pareto optimality to the multi-layered setting, and we focus on the problem of deciding whether a globally optimal assignment exists. We study this problem from the perspective of Parameterized Complexity: we consider several natural parameters such as the number of layers, the number of agents, the number of items, and the maximum length of a preference list. We present a comprehensive picture of the parameterized complexity of the problem with respect to these parameters.
BibTeX
@inproceedings{steindl2021parameterized,
  author = {Barak Steindl and Meirav Zehavi},
  title = {{Parameterized Analysis of Assignment Under Multiple Preferences}},
  booktitle = {EUMAS},
  year = {2021},
  doi = {10.1007/978-3-030-82254-5\_10},
}
Figure