Allocating Indivisible Items in Categorized Domains

Erika Mackin, Lirong XiaIJCAI 2016

Introduction

In many resource allocation scenarios, agents are not simply assigned a single item, but rather a "bundle" of items across multiple distinct categories. For example, a university student may need to be assigned both a thesis topic and a presentation date; a cloud computing client requires a combination of CPU, RAM, and storage; and a hospital must coordinate the assignment of surgeons, nurses, and operating rooms. These scenarios are formally defined as Categorized Domain Allocation Problems (CDAPs).

This paper introduces a formal framework for CDAPs and addresses the inherent difficulties in designing mechanisms that are fair, efficient, and easy for agents to navigate. The authors specifically focus on Basic CDAPs, where $n$ agents must each receive exactly one item from each of $p$ categories.

The Bottlenecks of Multi-Category Allocation

Standard allocation theory often fails in multi-category domains due to three primary bottlenecks:

  1. Preference Bottleneck: As the number of categories grows, the number of possible bundles increases exponentially. If there are 10 topics and 10 dates, an agent must rank 100 bundles. This becomes cognitively impossible for agents as $p$ increases.
  2. Computational Bottleneck: Finding an optimal allocation that satisfies all agents is often NP-hard in combinatorial settings.
  3. Strategic Behavior: In the absence of robust mechanisms, agents may misreport their preferences to "game" the system, leading to outcomes that are globally inefficient.

Axiomatic Characterization and the Serial Dictatorship

The authors begin by defining three desirable properties (axioms) for any allocation mechanism:

  • Strategy-proofness: No agent can obtain a better bundle by lying about their preferences.
  • Non-bossiness: An agent cannot change another agent's allocation without also changing their own.
  • Category-wise Neutrality: The mechanism is independent of the specific labels of the items; swapping item names results in a corresponding swap in the outcome.

One of the paper’s most significant theoretical contributions is Theorem 1, which proves that for any domain with at least two categories ($p \ge 2$) and two agents ($n \ge 2$), the only mechanism that satisfies these three axioms is a serial dictatorship. In a serial dictatorship, agents are ordered, and each agent picks their most preferred remaining bundle in sequence. While this provides a clear mathematical boundary, it also highlights a limitation: to achieve these properties, one must accept the inherent hierarchy of a dictatorship.

Categorical Sequential Allocation Mechanisms (CSAMs)

To address the preference bottleneck, the authors propose Categorical Sequential Allocation Mechanisms (CSAMs). Instead of requiring agents to rank every possible bundle upfront, CSAMs utilize a sequential "picking" protocol. Agents take turns selecting a single item from a specific category based on a pre-defined order.

This approach drastically reduces the communication complexity. While a direct mechanism requires $\Theta(n^{p+1} p \log n)$ bits of information to capture full bundle rankings, a CSAM only requires $\Theta(n^2 p \log np)$. This shift moves the problem from exponential complexity to a manageable polynomial-time solution.

Agent Psychology: Optimism vs. Pessimism

Because CSAMs are sequential, an agent’s choice in an early round depends on their expectations for future rounds. The authors analyze two psychological profiles:

  • Optimistic Agents: These agents select an item that belongs to their favorite remaining bundle, assuming they will get their preferred items in subsequent categories.
  • Pessimistic Agents: These agents follow a "maximin" strategy, selecting the item that ensures the best possible "worst-case" outcome, regardless of what others pick later.

The paper provides the first formal characterization of how these profiles affect rank efficiency (how highly the assigned bundle ranks on an agent's true preference list). They identify a fundamental efficiency trade-off: serial dictatorships with optimistic agents favor "utilitarian" efficiency (maximizing total group satisfaction) but often fail "egalitarian" efficiency (the satisfaction of the agent who picks last).

Limitations and Future Directions

While the framework provides a robust foundation for CDAPs, several areas remain for future exploration:

  • Strategic Sophistication: The current analysis of CSAMs largely assumes "myopic" agents who look only one step ahead. Modeling fully strategic, forward-looking agents in these sequential games remains a complex challenge.
  • General CDAPs: The "Basic" model assumes exactly one item per category. Real-world applications often require more flexible constraints, such as agents needing multiple items (e.g., several elective courses) or a minimum number of resources.
  • Preference Languages: The authors suggest integrating more sophisticated preference modeling tools, such as CP-nets (Conditional Preference networks), to allow agents to express conditional desires (e.g., "If I am assigned the morning slot, I prefer the easier topic").

By formalizing the constraints and possibilities of multi-category allocation, this research provides a vital roadmap for designing efficient and strategy-proof systems in complex, real-world environments.

Summary updated

BibTeX
@inproceedings{mackin2016allocating,
  author = {Erika Mackin and Lirong Xia},
  title = {{Allocating Indivisible Items in Categorized Domains}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure