Fair and Efficient Balanced Allocation for Indivisible Goods
This work provides the first polynomial-time solutions for achieving both EF1 and fPO under balanced constraints for specific valuation types, which is important for fair division problems in real-world scenarios like team drafts or asset division.
This paper addresses the problem of allocating indivisible goods among agents with additive valuations under a balanced constraint, where each agent receives the same number of goods. The authors establish the existence and provide polynomial-time algorithms for allocations that are simultaneously envy-free up to one good (EF1) and fractionally Pareto optimal (fPO) for two specific valuation settings: personalized bivalued valuations and at most two distinct valuation types.
We study the problem of allocating indivisible goods among agents with additive valuation functions to achieve both fairness and efficiency under the constraint that each agent receives exactly the same number of goods (the \emph{balanced constraint}). While this constraint is common in real-world scenarios such as team drafts or asset division, it significantly complicates the search for allocations that are both fair and efficient. Envy-freeness up to one good (EF1) is a well-established fairness notion for indivisible goods. Pareto optimality (PO) and its stronger variant, fractional Pareto optimality (fPO), are widely accepted efficiency criteria. Our main contribution establishes both the existence and polynomial-time computability of allocations that are simultaneously EF1 and fPO under balanced constraints in two fundamental cases: (1) when each agent has a personalized bivalued valuation, and (2) when agents have at most two distinct valuation types,. Our algorithms leverage novel applications of maximum-weight matching in bipartite graphs and duality theory, providing the first polynomial-time solutions for these cases and offering new insights for constrained fair division problems.