The Algorithmic Landscape of Priority-Respecting Allocations

Abstract

In applications from rationing medical care to university admissions, the decision of who is allocated is justified by various normative criteria. Such settings motivate the following priority-respecting allocation problem: several categories wish to allocate their quota of interchangeable items to a set of agents. The goal is to find a Pareto efficient allocation that respects quotas and adheres to eligibility and priority requirements stipulated by the categories. We exhibit a bijection between such allocations and maximum-weight matchings under carefully chosen weights. This clean characterization recovers known results in this space and demonstrates that the problem straddles a fine line of computational efficiency. Some extensions of priority-respecting allocation are handled by specializations of our algorithm, while related extensions are NP-hard.

Date
Oct 18, 2022 12:30 PM
Location
Indianapolis Convention Center
100 S Capitol Ave, Indianapolis, IN 46225