--- kind: concept slug: fair-allocation title: Fair allocation summary: >- Splits indivisible items among agents so that each gets a guaranteed share and no agent prefers another's bundle by much. The core choice is the fairness notion, EF1 or maximin share, and whether the bundle size is fixed. FairRec applies it to top-k recommendation with a greedy round-robin, for any relevance model. Only one paper so far, with author-reported results. tags: [fairness, allocation, recommendation, two-sided-markets] papers: ["2002.10764"] related: [algorithmic-fairness, collaborative-filtering, learning-to-rank] status: draft updated_at: 2026-11-05 --- ## Overview Fair allocation asks how to hand out a set of indivisible items among agents so that the split is fair to each of them. Here the agents are customers and the items are producers, such as sellers or artists, which appear in each customer's list [arxiv:2002.10764 §5.1]. The invariant the variants share is a guaranteed minimum for each item, plus a bound on how much one agent may envy another. Two notions are used: envy-freeness up to one item (EF1), and the maximin share (MMS), the best worst-case value an agent can secure for herself by splitting the items into bundles [arxiv:2002.10764 §5.1, eq. 1]. ## Variants ### Greedy round-robin with copies (FairRec) Each producer is copied so that it can be guaranteed a minimum exposure. Each customer may take at most one copy of a given producer. Customers then take turns picking their most relevant remaining option, in two phases [arxiv:2002.10764 §5.2, §5.3, alg. 1]. With α = 1 the paper proves EF1, that every producer gets non-zero exposure, and that at least n − k producers get their MMS [arxiv:2002.10764 §7]. Card: [FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms](/papers/2002.10764). ### Poorest-k (naive exposure balancing) A heuristic in which each customer receives the least-exposed producers in turn. The paper uses it as a baseline. It makes exposure nearly equal, but it lowers customer utility and spreads the loss unevenly across customers [arxiv:2002.10764 §4.3]. It has no fairness guarantee stated in the paper. ### Top-k (no fairness constraint) Each customer gets the k items with the highest relevance. This is the reference point for utility. Exposure is very unequal under it: in the paper's simulation with k = 20, the 50% least-exposed producers got 32%, 5% and 11% of total exposure on three datasets [arxiv:2002.10764 §4.2]. ## When to use which | Situation | Use | Why | |---|---|---| | Every item must reach a minimum exposure and no agent should envy another by more than one item | Greedy round-robin with copies | It is the variant with the EF1 and MMS results. Bundle size is exactly k per agent [arxiv:2002.10764 §7] | | The relevance scores come from a model you cannot change | Greedy round-robin | The method takes relevance as input and works with any model [arxiv:2002.10764 §3.4] | | Fixed list length k is required | Greedy round-robin, with k < n ≤ m·k | The paper proves results only for this range [arxiv:2002.10764 §6] | | A guarantee below MMS is wanted (α < 1) | Greedy round-robin, with care | The paper's theorems are proved for α = 1 only [arxiv:2002.10764 §7]. Its α sweep is reported qualitatively [arxiv:2002.10764 §8] | | Fairness must be checked against utility loss, and a simple baseline is enough | Poorest-k as a comparison | It shows the fairness gain, but it cuts utility and the loss falls unevenly [arxiv:2002.10764 §4.3] | | Runtime budget is tight | Check before choosing | The worst case is O(mnk) [arxiv:2002.10764 §7]. The paper does not state measured runtime or memory [arxiv:2002.10764 §8] | | Exposure does not depend on position in the list | Uniform-attention model | The paper assumes uniform attention over the k items and no position bias [arxiv:2002.10764 §3.5]. Position-aware models are left to future work [arxiv:2002.10764 §9] | Reported trade-off on the authors' datasets: the MMS guarantee costs at most about 20% of exposure relative to top-k, and customer utility stays close to top-k [arxiv:2002.10764 §8]. These are the authors' numbers on three datasets. Most values are in plots, so no further figures are given here. ## Implementation sketch Python-flavoured core of the greedy round-robin. Phase 1 uses copies, phase 2 has no copy limit. The full phase-2 rule is in the card, and it matters for the guarantee. ```pseudocode # Greedy round-robin [arxiv:2002.10764 alg. 2] # Input: ordered agents, supply per item, number of picks T, value V # Output: a bundle per agent, and the index of the last agent served def greedy_round_robin(order, supply, T, V, feasible): bundle = {u: [] for u in order} while T > 0: # One round: each agent in order picks one item [alg. 2] for u in order: # Items this agent has not taken yet and that still have supply options = [p for p in feasible[u] if supply[p] > 0] if not options: return bundle # Pick the most valuable option for this agent [alg. 2] p = max(options, key=lambda q: V[u, q]) bundle[u].append(p) feasible[u].remove(p) supply[p] -= 1 T -= 1 if T == 0: return bundle return bundle ``` Notes on the sketch: - Phase 1 sets each item's supply to floor(m·k/n) copies [arxiv:2002.10764 §5.2]. - Phase 2 reruns the same loop with unlimited supply, a rotated agent order and the remaining picks [arxiv:2002.10764 alg. 1]. The EF1 argument covers this rotated pass [arxiv:2002.10764 §7]. A simpler fill from each agent's own top-k list does not carry that argument. - The paper requires k < n ≤ m·k [arxiv:2002.10764 §6]. Check this before calling the routine. - The paper leaves the initial agent order open [arxiv:2002.10764 alg. 1]. Record the choice you make. ## Contradictions Only one paper is listed on this page, so no disagreement between papers can be shown yet. Within the paper, the reported LF ranges for which items meet MMS as k grows [arxiv:2002.10764 §8] do not match the copy count floor(m·k/n) in §5.2 at every k. The text places the drop at k = 19, while the formula gives a copy count of 2 from k = 19 (with m and n as in [arxiv:2002.10764 §4.1]). Use the formula for an implementation and treat the text ranges as unverified. ## Papers - [FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms](/papers/2002.10764): applies EF1 and MMS fair allocation to top-k recommendation with a two-phase greedy round-robin, and reports exposure and utility trade-offs on three datasets.