  In many applications such as rationing medical care and supplies, university
admissions, and the assignment of public housing, the decision of who receives
an allocation can be justified by various normative criteria. Such settings
have motivated the following priority-respecting allocation problem: several
categories, each with a quota of interchangeable items, wish to allocate the
items among a set of agents. Each category has a list of eligible agents and a
priority ordering over these agents; agents may be eligible in multiple
categories. The goal is to select a valid allocation: one that respects quotas,
eligibility, and priorities and ensures Pareto efficiency. We provide an
algorithmic characterization of all valid allocations, exhibiting a bijection
between sets of agents who can be allocated and maximum-weight matchings under
carefully chosen rank-based weights. While prior work provides a
polynomial-time algorithm to locate a valid allocation, our characterization
admits a simpler algorithm that enables two wide-reaching extensions: 1.
Selecting valid allocations that satisfy additional criteria: Via three
examples -- inclusion/exclusion of some chosen agent; agent-side Pareto
efficiency vs. welfare maximization; and fairness from the perspective of
allocated vs. unallocated agents -- we show that finding priority-respecting
allocations subject to some secondary constraint straddles a complexity
knife-edge; in each example, one problem variant can be solved efficiently,
while its variant is NP-hard. 2. Efficiency-envy tradeoffs in dynamic
allocation: In settings where allocations must be made to T agents arriving
sequentially via some stochastic process, we show that while insisting on zero
priority violations leads to an Omega(T) loss in efficiency, one can design
allocation policies ensuring that the sum of the efficiency loss and priority
violations in hindsight is O(1).
