Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings

We study fair allocation of indivisible goods and chores for agents with ordinal preferences and arbitrary entitlements. In the case of both goods and chores, we show that there always exist allocations that are weighted necessarily proportional up to one item (WSD-PROP1), that is, allocations that are WPROP1 under all additive valuations consistent with agents' ordinal preferences. We give a polynomial-time algorithm to find such allocations by reducing it to a problem of finding perfect matchings in a bipartite graph. We give a complete characterization of these allocations as extreme points of a perfect matching polytope. Using this polytope, we can optimize any linear objective function over all WSD-PROP1 allocations, for example, to find a min-cost WSD-PROP1 allocation of goods or most efficient WSD-PROP1 allocation of chores. Additionally, we show the existence and computation of sequencible (SEQ) WSD-PROP1 allocation using rank-maximal perfect matchings and show the incompatibility of Pareto optimality under all valuations with the WSD-PROP1 notion. We also consider the notion of Best-of-Both-Worlds (BoBW) fairness. Using our characterization, we give a polynomial-time algorithm to compute Ex-ante envy-free (WSD-EF) and Ex-post WSD-PROP1 allocations for both goods and chores.