Adjusted Winner: from Splitting to Selling

2026-02-12Computer Science and Game Theory

Computer Science and Game Theory
AI summary

The authors discuss the Adjusted Winner (AW) method, a way to fairly divide items between two people, which sometimes requires splitting items. To avoid this, they extend the method to sell some items within a budget and share the money fairly instead. They study how this change affects fairness concepts like equitability and envy-freeness. The authors also explore the math problems that come up, show they're complex, and create an efficient approximation method to solve them. They back up their findings with computer simulations.

Adjusted Winner methodfair divisionindivisible resourcesequityenvy-freenesscombinatorial optimizationbudget constraintcomputational complexityapproximation algorithmsFPTAS
Authors
Robert Bredereck, Bin Sun, Eyal Briman, Nimrod Talmon
Abstract
The Adjusted Winner (AW) method is a fundamental procedure for the fair division of indivisible resources between two agents. However, its reliance on splitting resources can lead to practical complications. To address this limitation, we propose an extension of AW that allows the sale of selected resources under a budget constraint, with the proceeds subsequently redistributed, thereby aiming for allocations that remain as equitable as possible. Alongside developing this extended framework, we provide an axiomatic analysis that examines how equitability and envy-freeness are modified in our setting. We then formally define the resulting combinatorial problems, establish their computational complexity, and design a fully polynomial-time approximation scheme (FPTAS) to mitigate their inherent intractability. Finally, we complement our theoretical results with computer-based simulations.