Dynamic Fair Division with Partial Information

Gerdus Benade, Daniel Halpern, Alexandros PsomasNeurIPS 2022 · OpenReview

In the realm of resource allocation, "Dynamic Fair Division" presents a unique challenge: allocating items to individuals as they arrive sequentially, without knowing what items will appear next. While previous research often assumed agents could provide exact numerical (cardinal) values for items, this paper demonstrates that we can achieve high levels of fairness and efficiency using only simple, ordinal comparisons—such as an agent stating, "I prefer this new item over the one I received yesterday."

TL;DR

The authors prove that exact numerical valuations are not strictly necessary for fair and efficient dynamic resource allocation. By utilizing epoch-based algorithms that learn item distributions through ordinal rankings, the system achieves envy-freeness and near-optimal social welfare, even in constrained settings where agents can only remember a single previous item.

The Challenge of Partial Information

Fair division is a classic problem at the intersection of economics and computer science, seeking to distribute goods such that everyone is satisfied (fairness) and the total value is maximized (efficiency). The "dynamic" variant complicates this by introducing items one by one; once an item is allocated, the decision is irrevocable.

Most existing solutions require agents to report cardinal values (e.g., "This item is worth exactly 4.2 units to me"). However, humans are notoriously poor at assigning absolute numbers to preferences, functioning much better with ordinal comparisons (e.g., "I prefer item A to item B"). The core question this paper addresses is whether we can still guarantee fairness and efficiency relying solely on these relative rankings.

Algorithmic Approach

The researchers propose algorithms grounded in the concept of quantiles. Instead of eliciting an absolute value, the algorithms estimate where a new item sits within an agent's overall distribution of preferences.

1. Unbounded Memory Algorithm

The first approach tracks the relative rank of every item an agent has ever seen. It operates in progressively longer "epochs." Each epoch consists of a sampling phase (distributing items to learn agent preferences) and a ranking phase (allocating items to the agent who ranks them highest relative to their history).

Algorithm 1: EF + (1-ε)-Welfare

By making the ranking (exploitation) phases significantly longer than the sampling (exploration) phases, the algorithm effectively "washes out" any unfairness or inefficiency generated while it was still learning the distribution.

2. Limited Memory Algorithm

The second approach models a more realistic, "human-like" constraint where each agent only remembers one previous item. The algorithm employs a threshold strategy: it identifies a "benchmark" item for each agent representing a high quantile (e.g., the top $1/n$ of items). If a new item surpasses that benchmark, it becomes a candidate for allocation.

Using rigorous probabilistic analysis—specifically the Dvoretzky–Kiefer–Wolfowitz inequality—the authors prove that the errors made during the learning phases become negligible over time compared to the total welfare generated.

Key Insights

  • The Impossibility of Perfection: The authors establish a formal "separation" between cardinal and ordinal settings. In a cardinal world, perfect Pareto efficiency and envy-freeness are simultaneously achievable. In the ordinal world, they are not. One must settle for an approximation of efficiency to guarantee fairness.
  • Quantiles Over Values: Knowing whether an item is worth "10" or "100" is less important than knowing if it falls in the agent's top 10% of items. Ordinal information serves as a highly effective proxy for this.
  • The Power of One Item: Surprisingly, remembering just a single benchmark item is sufficient to achieve a constant approximation of the maximum possible social welfare. A massive historical database is not strictly required for effective decision-making.

Summary of Results

The paper provides a hierarchy of theoretical guarantees based on the available information and memory constraints, evaluated under both i.i.d. (independent and identically distributed) and non-i.i.d. stochastic models.

Summary of Possibility and Impossibility Results

Crucially, the authors prove asymptotic tightness for these bounds. For instance, they demonstrate that no 1-item memory algorithm can ever achieve more than a 0.999 approximation of welfare, making their constant approximation of 0.399 (via the Limited Memory algorithm) a significant theoretical milestone.

Limitations and Future Directions

  • Independence Assumption: The current model assumes item values are independent. In reality, preferences are often correlated (e.g., valuing a left shoe highly implies a high value for the right shoe). Handling correlated items remains a major open challenge.
  • Additive Preferences: The framework assumes the value of a bundle is simply the sum of its individual items, ignoring "complements" (items that are better together) or "substitutes."
  • Strategic Behavior: The algorithms assume agents report their rankings honestly. Future research must investigate "truthfulness"—designing mechanisms where agents have no incentive to misreport their rankings to secure better items.

Summary updated

Abstract

We consider the fundamental problem of fairly and efficiently allocating $T$ indivisible items among $n$ agents with additive preferences. The items become available over a sequence of rounds, and every item must be allocated immediately and irrevocably before the next one arrives. Previous work shows that when the agents' valuations for the items are drawn from known distributions, it is possible (under mild technical assumptions) to find allocations that are envy-free with high probability and Pareto efficient ex-post. We study a \emph{partial-information} setting, where it is possible to elicit ordinal but not cardinal information. When a new item arrives, the algorithm can query each agent for the relative rank of this item with respect to a subset of the past items. When values are drawn from i.i.d.\ distributions, we give an algorithm that is envy-free and $(1-\epsilon)$-welfare-maximizing with high probability. We provide similar guarantees (envy-freeness and a constant approximation to welfare with high probability) even with minimally expressive queries that ask for a comparison to a single previous item. For independent but non-identical agents, we obtain envy-freeness and a constant approximation to Pareto efficiency with high probability. We prove that all our results are asymptotically tight.
BibTeX
@inproceedings{benade2022dynamic,
  author = {Gerdus Benade and Daniel Halpern and Alexandros Psomas},
  title = {{Dynamic Fair Division with Partial Information}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=YiFQqYAk1xH},
}
Figure