Assignment Mechanisms under Distributional Constraints

By Itai Ashlagi, Amin Saberi, Ali Shameli. 2018

26 citations recorded by the source corpus.

We study the assignment problem of objects to agents with heterogeneous preferences under distributional constraints. Each agent is associated with a publicly known type and has a private ordinal ranking over objects. We are interested in assigning as many agents as possible. Our first contribution is a generalization of the well-known and widely used serial dictatorship. Our mechanism maintains several desirable properties of serial dictatorship, including strategyproofness, Pareto efficiency, and computational tractability while satisfying the distributional constraints with a small error. We also propose a generalization of the probabilistic serial algorithm, which finds an ordinally efficient and envy-free assignment, and also satisfies the distributional constraints with a small error. We show, however, that no ordinally efficient and envy-free mechanism is also weakly strategyproof. Both of our algorithms assign at least the same number of students as the optimum fractional assignment.

Subfields: Artificial Intelligence, Economics and Econometrics, Management Science and Operations Research, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Ben Hutchinson
2. Vinodkumar Prabhakaran

In Management Science and Operations Research

1. Erin Arnesen
2. Ben Hutchinson
3. Tulsee Doshi
4. Nithya Sambasivan
5. Vinodkumar Prabhakaran

Citations in the corpus

• Re-imagining Algorithmic Fairness in India and Beyond (2021, background): “The quota system gives rise to the problem of matching under distributional constraints, a known problem in economics [23, 79, 105], but has not received attention within the FAccT community (although [51] is related).”