Papers for

allocation platform developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Matching mechanisms enable simple access to desired outcomes

Singleton-Attainability and Transparent Access in Matching

Abstract: Matching mechanisms differ in how much of an agent's preference ranking must be determined and reported to obtain a particular object. A mechanism is singleton-attainable (SA) if every object that an agent can obtain through some report can also be obtained by reporting only that object as acceptable. With an SA mechanism, once an attainable object has been identified, the agent need not rank or report any other object. Singleton-attainability identifies a distinct dimension in matching theory and market design: transparent access to attainable outcomes, separate from incentives, stability, welfare or equity. We establish general conditions for SA and derive its strategic implications. Top-lift invariance and truncation invariance together imply SA, while strategyproofness and stability each imply SA. By contrast, no Pareto improvement over a strategyproof, individually rational, and non-wasteful mechanism is SA. In particular, every Pareto improvement over Deferred Acceptance violates SA. We introduce report width, which measures how many acceptable objects may have to be reported to obtain an object. SA mechanisms have report width one. Report width is unbounded for a large class of efficient mechanisms that Pareto-improve Deferred Acceptance. Stable selection with report-induced priorities has width one when priorities are monotone and maximal width under reverse priority dominance. Rank-welfare maximization has width one when the outside-option rank is fixed and maximal width when it is report-dependent. These results reveal a structural divide, which we call the width dichotomy: across all mechanisms and families in our classification and all structural classes we study, report width is either one or unbounded.

Wed 23 SeptComputer Science and Game Theory
The gist
Matching systems decide how people get assigned to things like schools or jobs based on preferences. This paper looks at how much a person needs to list their choices to get a certain outcome. The authors identify a type of system where someone can get an object just by saying that object is acceptable, without listing others. They explore the implications and conditions of these systems, showing a sharp divide between mechanisms that need only one acceptable choice and those that require many.
Open → 2609.27293v1