New algorithm learns fair item allocation via limited feedback in polynomial time

A team of researchers from the University of Pittsburgh and the University of Toronto has developed a novel algorithm for learning fair allocations of indivisible items when the algorithm has no prior knowledge of agent valuations. The paper, accepted to the ACM Conference on Economics and Computation (EC 2026), addresses a realistic scenario where an allocator must propose allocations and learn about preferences from limited, potentially adversarial feedback about fairness violations. The algorithm maintains a polytope of candidate valuations consistent with all past feedback. Each proposed allocation generates a fairness violation (e.g., envy), which defines a separating hyperplane, allowing the algorithm to iteratively refine its estimates using an ellipsoid method.

For additive valuations (including mixed goods and chores), the algorithm provably finds an allocation satisfying EF1 (envy-free up to one item) or PROP1 (proportional up to one item) in polynomial time. For general monotone valuations, the algorithm guarantees an EF1 allocation in polynomially many iterations by restricting to allocations where each agent receives an interval plus one extra item from an arbitrary ordering. While the number of rounds is polynomial, the internal computational steps may not be polynomial. The work provides a bridge between algorithmic fairness and online learning, with potential applications in automated resource allocation, matching markets, and AI systems that must learn user preferences on the job.