CoChat
Sign Up
Cited by 11Game Theory and Voting SystemsFacility Location and Emergency ManagementOptimization and Mathematical Programming

Assignment Mechanisms Under Distributional Constraints

Open access
Ashlagi, Itai, Saberi, Amin, Shameli, Ali·2020·Operations Research
DOI 10.1287/opre.2019.1887
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

Integrity signals

Registry

Crossref · 10.1287/opre.2019.1887

Cites

27 of 27 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The quota system gives rise to matching under distributional constraints, a known economics problem that has not received attention within the FAccT community.

    “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).”

    From Re-imagining Algorithmic Fairness in India and Beyond (2021) · cites this paper as [23]

Cites

Flagged first, then by citations

Cited by

Sorted by citations

Related

Authors
Ashlagi, I., Saberi, A., & Shameli, A.
Affiliations
  • Department of Management Science and Engineering, Stanford University, Stanford, California 94305
  • Stanford University (US)
ORCID
Venue
Operations Research
Publisher
Institute for Operations Research and the Management Sciences (INFORMS)
Published
2020-02-27
ISSN
  • 0030-364X (ISSN-L)
  • 1526-5463
DOI
10.1287/opre.2019.1887
OpenAlex
W3007179577
Cited by
11
References
27
Citations by year
2023: 3 · 2022: 2 · 2021: 3 · 2020: 3
FWCI
2.20
Type
journal article
Language
en
Open access
Locations
  • Operations Research (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (1254768, 1812919, 2012344)
  • Office of Naval Research
Topics
  • Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Game Theory and Voting Systems
  • Social Sciences › Business, Management and Accounting › Organizational Behavior and Human Resource Management › Facility Location and Emergency Management
  • Physical Sciences › Engineering › Control and Systems Engineering › Optimization and Mathematical Programming
Keywords
assignment mechanisms, distributional constraints, assignment games, fair division, resource allocation, mechanism design

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review