Fair allocation

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 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 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 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 2002.10764 §7. Card: FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms.

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 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 2002.10764 §4.2.

When to use which

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 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.

# 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 2002.10764 §5.2.
• Phase 2 reruns the same loop with unlimited supply, a rotated agent order and the remaining picks 2002.10764 alg. 1. The EF1 argument covers this rotated pass 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 2002.10764 §6. Check this before calling the routine.
• The paper leaves the initial agent order open 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 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 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: 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.