Source-linked AI summary
Online Fair Division: analysing a Food Bank problem
Martin Aleksandrov, Haris Aziz, Serge Gaspers, Toby Walsh
TL;DR
The paper studies online fair division motivated by allocating donated food among charities. It analyzes two like-based mechanisms, their axiomatic properties, welfare effects, competitive performance, and price of anarchy, under an online allocation model.
Problem
Real-world food allocation among charities has indivisible goods, no money, and online arrivals that standard fair-division categories do not fully capture.
Method
The paper models sequential item arrivals with like-or-not declarations and analyzes LIKE and BALANCED LIKE using axioms, welfare comparisons, competitive analysis, and price-of-anarchy calculations.
Results
LIKE is strategy-proof for the studied setting, while both mechanisms can have equilibria with welfare k times worse than sincere play; LIKE’s price of anarchy is k for egalitarian welfare and at most k for utilitarian welfare.
Takeaways & Limitations
Mechanism choice matters: BALANCED LIKE improves egalitarian welfare over LIKE under sincere or strategic play in the reported experiments.
Takeaways & Limitations
The strategic analysis assumes agents know future items, their order, and other agents’ private utilities, although limited knowledge may reduce strategic behavior.
Abstract
from arXiv · showhide
We study an online model of fair division designed to capture features of a real world charity problem. We consider two simple mechanisms for this model in which agents simply declare what items they like. We analyse several axiomatic properties of these mechanisms like strategy-proofness and envy-freeness. Finally, we perform a competitive analysis and compute the price of anarchy.
1 Introduction
The paper studies online fair-division mechanisms to address the limits of simple abstract models in capturing real-world resource-allocation problems.
- Fair division models classify allocation problems along dimensions such as divisibility, centralization, and preference representation.
- The paper responds to calls for more realistic models by studying mechanisms for an online fair-division problem.
2 The Food Bank problem
The Food Bank problem concerns allocating donated, mostly indivisible food fairly among charities under urgent online arrivals and growing demand.
- Food banks face increasing demand as people in poverty struggle to feed themselves.Food Bank Australia reported demand increasing by over 10% per annum.
- Donated food must be allocated almost immediately because items arrive throughout the day before future donations are known.
- The allocation problem involves mostly indivisible goods, no money, and charities serving different community sectors.
3 Online fair division
The paper models sequential item arrivals and compares LIKE with BALANCED LIKE, which randomize among agents who value each item while the latter favors agents with fewer allocations.
- One item appears at each of m time steps and must be assigned to one of k agents before the next item is revealed.
- LIKE allocates each item uniformly among agents declaring that they like it.
- BALANCED LIKE randomizes among valuing agents who have received the fewest items so far.
- The mechanisms' realized outcomes can be computed in O(k) time per item, while BALANCED LIKE probabilities and expected utilities use dynamic programming in O(mk) space and time.
4 Strategy-proofness
LIKE is strategy-proof, whereas BALANCED LIKE generally permits profitable strategic reporting, though it is strategy-proof with two agents and 0/1 utilities under the paper’s knowledge assumption.
- LIKE is strategy-proof when agents know future item order, remaining items, and other agents’ private utilities.
- BALANCED LIKE is not strategy-proof even with 0/1 utilities because withholding a current bid can bias future allocations favorably.
- The complete-knowledge assumption is strong, and partial knowledge can reduce an agent’s willingness to act strategically.
- With two agents and 0/1 utilities, BALANCED LIKE is strategy-proof even under complete knowledge of future items and other agents’ utilities.
- The strategy-proofness analysis uses allocation-tree induction and lemmas comparing expected utility across states.
- Strategic behavior can increase an agent’s expected utility from 1/2 to 3/4 without changing egalitarian welfare in a two-agent, two-item example.
5 Impact on welfare
Strategic behavior can substantially change welfare outcomes. For BALANCED LIKE, simple pure Nash equilibria can produce either lower or higher egalitarian welfare than sincere play, while utilitarian welfare remains unchanged.
- Pure Nash equilibria can have much smaller egalitarian and utilitarian welfare than sincere play for both mechanisms.
- Sincere play is the only simple pure Nash equilibrium for LIKE, so simple equilibria do not change its welfare.
- For BALANCED LIKE, every simple pure Nash equilibrium has the same utilitarian welfare as sincere play because each item goes to an agent who likes it.
- BALANCED LIKE admits instances where sincere play has strictly greater expected egalitarian welfare than every simple pure Nash equilibrium.
- BALANCED LIKE also admits instances where sincere play has strictly smaller expected egalitarian welfare than every simple pure Nash equilibrium.
6 Fairness
The mechanisms differ in their fairness guarantees across utility models and fairness notions. LIKE is ex ante envy-free under sincere play but can have unbounded ex post envy, whereas BALANCED LIKE provides stronger guarantees for 0/1 utilities and weaker guarantees for general utilities.
- No mechanism allocating all indivisible items can be envy-free ex post.
- LIKE is envy-free ex ante under sincere play but is not bounded envy-free ex post, even with 0/1 utilities and two agents.
- With 0/1 utilities, BALANCED LIKE is envy-free ex ante and bounded envy-free ex post under sincere play.
- For general utilities, BALANCED LIKE is not envy-free ex ante or bounded envy-free ex post because balancing can prevent allocation of a highly valued item.
- With utilities restricted to 0/1 or close to it, BALANCED LIKE may be somewhat fairer than LIKE; with more varied utilities, it may be somewhat less fair.
7 Competitive analysis
Competitive analysis measures the efficiency loss from online arrival, while the price of anarchy considers strategic bidding. LIKE has a bounded competitive ratio with k agents, but BALANCED LIKE has no constant competitive ratio for general utilities even with two agents.
- The competitive ratio captures efficiency loss caused by online item arrival, and the analysis assumes sincere bidding.
- LIKE is k-competitive from both egalitarian and utilitarian perspectives with k agents.
- The LIKE bound is tight: its expected egalitarian welfare can be 1 versus an optimal offline welfare of k, and its expected utilitarian welfare can approach 1 versus k.
- BALANCED LIKE is not c-competitive from either perspective for any constant c, even with two agents and general utilities.
- For a two-agent instance, BALANCED LIKE can attain egalitarian welfare 2ε while the optimal offline allocation attains 1−ε.
- With 0/1 utilities, every allocation produced by LIKE or BALANCED LIKE achieves the optimal offline utilitarian welfare.
8 Price of anarchy
The price of anarchy compares optimal social welfare with the worst equilibrium welfare, revealing substantial strategic losses for both mechanisms under egalitarian and utilitarian objectives. The LIKE mechanism reaches a factor-k egalitarian loss, while BALANCED LIKE has matching lower bounds in key settings.
- The price of anarchy is the ratio between optimal welfare and the smallest welfare achieved by any equilibrium strategy.The paper considers both egalitarian and utilitarian welfare and restricts attention to simple pure Nash equilibria.
- k is the LIKE mechanism’s egalitarian price of anarchy, while its utilitarian price of anarchy is at most k and greater than k − ϵ.
- The LIKE mechanism’s egalitarian bound is achieved when optimal welfare is k but equilibrium welfare is 1.
- With 0/1 utilities, BALANCED LIKE has egalitarian price of anarchy at least k.
- With general utilities, BALANCED LIKE has utilitarian price of anarchy greater than k − ϵ for any ϵ > 0.
- With 0/1 utilities, both mechanisms achieve optimal utilitarian welfare and therefore have no utilitarian price of anarchy in those cases.
9 Experiments
Experiments compare the mechanisms across randomly generated 0/1 instances using competitive ratios, prices of anarchy, and welfare ratios. BALANCED LIKE consistently outperforms LIKE, including under sincere and strategic play.
- The experiments varied agents from 2 to 5 and items from 2 to 10, sampling 100 instances at each data point.
- The evaluation plotted competitive ratios, the BALANCED LIKE price of anarchy, and the ratio of best-equilibrium egalitarian welfare to optimal welfare.
- BALANCED LIKE improved egalitarian welfare over LIKE under both sincere and strategic play.
- BALANCED LIKE remained superior to LIKE in all reported experiments.
- Strategic play often increased social welfare in the worst case for BALANCED LIKE, although the effect was small.
10 Related work
The paper extends fair-division research to an online setting with arriving indivisible heterogeneous items, contrasting itemcentric mechanisms with earlier models involving arriving agents or divisible goods. It also relates bounded envy-freeness to an offline fairness property.
- Earlier fair-division studies generally assume that all goods are initially available, unlike this online model.
- Walsh’s online cake-cutting model has arriving agents and divisible goods, whereas this paper studies arriving indivisible items.
- Kash, Procaccia, and Shah study arriving agents with multiple homogeneous divisible goods, differing from this paper’s heterogeneous indivisible goods.
- Bounded envy-freeness is related to the single-unit utility difference property achievable with envy-free ex ante randomized offline allocation.
- LIKE and BALANCED LIKE are itemcentric, iterating over items rather than agents as sequential allocation mechanisms do.
11 Conclusions
The paper studies an online fair-division model motivated by Food Bank allocation and evaluates LIKE and BALANCED LIKE through axiomatic and welfare analyses. Its practical guidance favors BALANCED LIKE when item packages give agents similar utilities, and LIKE otherwise.
- The study analyzes strategy-proofness, envy-freeness, competitive performance, and price of anarchy for two online mechanisms.
- BALANCED LIKE may be preferred when items can be packaged so agents have similar utility for each package.
- LIKE may be preferred when packaging items into similarly valued packages is not possible.
- Future work will model charities with different entitlements and examine the resulting axiomatic properties.