FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms

In plain words

Recommendation systems usually show each customer the items they are most likely to like. On a marketplace, that can leave some sellers, artists or shops almost never shown, and those sellers may leave the platform. Giving every seller a fixed share of attention can in turn make customers see worse suggestions.

FairRec tries to balance both sides. It treats the shown slots like indivisible prizes that must be handed out among customers. Every seller is promised a minimum number of views, and no customer should feel that another customer's list is clearly better than their own, apart from at most one item. A greedy round-robin, where customers take turns picking their best remaining option, does the handing out. It does not depend on how the relevance scores are produced.

TL;DR

FairRec builds top-k lists for all customers at once, with exactly k items per customer. It gives each producer a minimum exposure, the maximin share, to most producers, and makes the allocation envy-free up to one item for customers §1. It is a greedy round-robin run in two phases, with a worst-case cost of O(mnk) §6, §7. Author-reported results show a loss of at most about 20% in exposure against top-k, and customer utility close to top-k §8.

Problem

Under top-k recommendation, exposure is very unequal. In the paper's simulation (k = 20), the 50% least-exposed producers get only 32%, 5% and 11% of the total exposure m·k on GL-CUSTOM, GL-FACT and LF §4.2. Exposure is the number of customer lists a producer appears in §3.5, and the authors argue that low exposure drives producers away and so harms the platform §4.2.

The naive fix, poorest-k, which recommends the least-exposed producers, makes exposure nearly equal but lowers customer utility and spreads that loss unevenly across customers §4.3. The paper assumes uniform attention over the k shown items and no position bias §3.5.

Method

Setting. There are m customers U and n producers P. Each list R_u has k distinct producers. Relevance V_u(p) comes from any model. The utility of a list is the sum of relevance, normalised by the top-k sum §3.4. Exposure of p is the number of lists containing p, E_p, and the total is m·k §3.5.

Desiderata. Producers get a guaranteed minimum exposure Ē. Customers should be envy-free up to one item (EF1) §4.4.

Reduction to fair allocation. Producers become items and customers become agents. Making Ē copies of each producer gives a minimum exposure of Ē, and Ē ≤ MMS, where MMS = floor(m·k/n) §5.2. The copies are non-shareable, and a customer may get at most one copy of a producer §5.3. The exact count of items for each customer is k, which is an extra constraint beyond classic allocation §5.3.

Fairness notions. EF1 holds if for each pair of customers, u's own bundle is at least as good as w's bundle with one item removed §5.1. The maximin share of agent u is the best worst-bundle value u can guarantee herself by partitioning the items into |U| bundles §5.1, eq. 1.

Algorithm. FairRec runs two phases of Greedy-Round-Robin alg. 1, alg. 2. Phase 1 gives each producer ℓ copies and takes ℓ·n items. If the customer after the last served one still has fewer than k items, phase 2 runs again with all copies unlimited, a rotated customer order and the remaining slots alg. 1.

# FairRec  [alg. 1]
# Input:  customers U (m), producers P (n), k with k < n <= m*k,
#         relevance V[u, p]
# Output: exactly k producers per customer

def fair_rec(U, P, k, V):
    m = len(U)
    # Customers in a fixed, arbitrary order  [alg. 1]
    order = list(U)
    # Each customer may take each producer at most once  [§5.3]
    feasible = {u: set(P) for u in U}
    allocation = {u: [] for u in U}

    # Phase 1: each producer has ell copies, ell = floor(m*k/n)  [§5.2]
    ell = (m * k) // n
    supply = {p: ell for p in P}
    batch, feasible, last = greedy_round_robin(
        order, supply, ell * n, V, feasible)
    for u in U:
        allocation[u] += batch[u]

    # Phase 2 runs only if the customer after `last` is short of k  [alg. 1]
    next_user = order[last % m]
    count = len(allocation[next_user])
    if count < k:
        # Copies are now unlimited  [alg. 1]
        supply = {p: m for p in P}
        items = 0
        if last < m:
            # Rotate the order so it starts at the next customer  [alg. 1]
            order = order[last:] + order[:last]
            items = m - last
            count += 1
        items += m * (k - count)
        batch, feasible, last = greedy_round_robin(
            order, supply, items, V, feasible)
        for u in U:
            allocation[u] += batch[u]

    return allocation

# Greedy-Round-Robin  [alg. 2]
# Input:  ordered customers, supply per producer, number of items T,
#         relevance V, feasible sets F
# Output: batch per customer, updated F, index of the last customer served

def greedy_round_robin(order, supply, T, V, feasible):
    # Empty batches; the last index starts at m  [alg. 2]
    batch = {u: [] for u in order}
    last = len(order)
    while T > 0:
        # One round: each customer in order picks one item  [alg. 2]
        for i, u in enumerate(order, start=1):
            # Producers still open to u and with copies left  [alg. 2]
            options = [p for p in feasible[u] if supply[p] > 0]
            if not options:
                # Stop; the last served customer is i-1, unless i = 1  [alg. 2]
                if i != 1:
                    last = i - 1
                return batch, feasible, last
            # Most relevant option for u  [alg. 2]
            p = max(options, key=lambda q: V[u, q])
            batch[u].append(p)
            feasible[u].remove(p)
            supply[p] -= 1
            T -= 1
            if T == 0:
                last = i
                return batch, feasible, last
    return batch, feasible, last

Guarantees (all proved for α = 1 §7). The greedy procedure satisfies four properties: an earlier customer never envies a later one; the result is EF1; each customer gets at most one copy of each producer; and any two customers' batch sizes differ by at most 1 §7, Proposition. The EF1 argument uses the inequality eq. 2. The main theorem says that, for k < n ≤ m·k, FairRec gives an EF1 allocation with exactly k items per customer, gives every producer non-zero exposure, and gives the MMS value to at least n − k producers §7, Theorem. A corollary says that if k ≤ βn then at least (1 − β)n producers get MMS §7, Corollary. The worst case is O(mnk) §7, Lemma.

Producer and customer metrics used in the experiments §8:

\mathrm{MMS}_u = \max_{\mathcal{A}} \min_{w \in \mathcal{U}} \mathcal{V}_u(A_w) eq. 1

H = \frac{1}{|P|} \sum_{p \in P} \mathbb{1}[E_p \ge \bar{E}] eq. 3

Z = -\sum_{p \in P} \frac{E_p}{m k} \log_n \frac{E_p}{m k} eq. 4

L = \frac{1}{n} \sum_{p \in P} \max\left(\frac{E^{\text{top-}k}_p - E_p}{E^{\text{top-}k}_p}, 0\right) eq. 5

Y = \frac{1}{n} \sum_{u \in U} \frac{1}{n-1} \sum_{u' \ne u} \mathrm{envy}(u, u') eq. 6

Here envy(u, u') = max(φ_u(R_u') − φ_u(R_u), 0) §8. The paper also reports μ_φ, the mean of the normalised utilities, and std_φ, their standard deviation §8. Eq. 6 prints n where the sum is over customers. See Pitfalls.

Baselines §8: Top-k; Random-k; Mixed-k (the top ⌈k/2⌉ items, then random items for the rest); PR-k (poorest-k, which gives each customer the k least-exposed producers in turn).

Hyperparameters

Results

Author-reported. Setup: three datasets (GL-CUSTOM, GL-FACT, LF) with the relevance models above; baselines Top-k, Random-k, Mixed-k and PR-k; the metrics above. Hardware and run counts are not stated. Most results are in plots, and no values were extracted from the figures.

The paper's summary: FairRec gives good producer fairness at a marginal loss of customer quality, and α trades producer fairness against customer utility and popular producers' exposure §8.

Paper vs code

The official repository at ad2c4550 README.md has three Python files and a README. It has no LICENSE file.

• Phase 2 is not the paper's procedure. Algorithm 1 reruns greedy round-robin with a rotated order, unlimited copies and the remaining item count alg. 1. FairRec.py instead fills each customer who has fewer than k items independently, from their top 2k relevance scores, skipping items already held FairRec.py. The EF1 proof in §7 covers the greedy phase 2, so it does not cover this code. I did not test EF1 numerically.
• Phase 1 masks infeasible producers as 0. The code computes relevance times a feasibility/supply mask, so infeasible producers score 0, then takes argmax FairRec.py. The paper takes the argmax over feasible producers only alg. 2. If the best feasible relevance is ≤ 0, argmax can return an infeasible producer, and the code then stops phase 1 early FairRec.py. This matters only if relevance can be ≤ 0; the paper does not say.
• Copies scale with α. The code uses ℓ = floor(α·m·k/n) FairRec.py. Algorithm 1 prints ℓ = floor(m·k/n), but §5.2 and §8 say copies equal Ē. The code follows the text, not the printed algorithm.
• Round count. The code caps phase 1 at ceil(ℓ·n/m) rounds FairRec.py and then stops on T = 0 or no feasible producer. The paper's loop has the same outcome, so there is no discrepancy here.
• Customer order is the index order range(m) FairRec.py, and the paper allows any fixed order.
• FairRecPlus.py is a different method. It adds envy-cycle removal after each greedy round FairRecPlus.py, FairRecPlus.py. The README runs it next to FairRec and cites arXiv:2201.01180, a journal extension, without saying which version each script implements README.md README.md. Do not cite FairRecPlus as this paper's method.
• Baselines. Top-k baselines.py and Random-k baselines.py match the text. Mixed-k matches baselines.py. PR-k baselines.py gives each customer in turn the least-exposed producer not yet in their list. baselines.py also has a Mixed-TP-k variant baselines.py, which the paper does not describe.
• No evaluation code. The repository has no code for H, Z, L, Y, μ_φ or std_φ, and no plotting code. The figures cannot be reproduced from the repo.
• Data is external. The relevance matrices are on Zenodo, and the repo does not include the datasets or the latent factorization code README.md.
• No seeds. random is used without seeds baselines.py baselines.py. Random-k and Mixed-k results will vary between runs.

No discrepancy was found in the core greedy selection rule: feasibility, supply, most-relevant choice, and stopping at T = 0 or on an infeasible customer match alg. 2 FairRec.py.

Pitfalls

• Phase 2 is the step that carries the EF1 claim. An implementation that only fills customers from their top-k (the code's approach) will not have the §7 guarantee. Implement Algorithm 1's rotated greedy pass, not the code's fill-in.
• Copy counts with α < 1. The guarantee is for α = 1 §7. With α < 1, the theorems are not proved in the paper. The text says copies equal Ē, which is floor(α·m·k/n) §5.2 §8.
• Constraints the code does not check. The method needs k < n ≤ m·k, and the paper excludes k = n and k > n §6. FairRec.py does not check these.
• MMS is only partly guaranteed. The theorem gives MMS for at least n − k producers, not all of them §7. The paper reports this in practice for LF: MMS holds for all producers only up to k = 9 §8.
• LF MMS ranges in the text. The paper gives MMS = 0 for k < 10, 1 for k ∈ [10, 18], and 2 for k ∈ [20, 29] §8. But the paper also says the drop happens at k = 19 §8. With m = 1892 and n = 17632 §4.1, floor(m·k/n) is 2 from k = 19 (1892·19/17632 ≈ 2.04), and 3 by k = 29. So the text's ranges are off, and the k = 19 drop matches floor(m·k/n).
• Eq. 6 uses n for customers. The sum in eq. 6 runs over customers, but the printed denominators use n (the number of producers, with n − 1). Section §3.2 defines |U| = m, and μ_φ is written with 1/m. Implement Y with m and m − 1, and state that choice, since the paper does not.
• Zero exposure in Z and L. Z uses E_p log E_p, which is undefined at 0 unless the convention 0 log 0 = 0 is used. L divides by E^top-k_p, which is 0 if top-k never shows p. The paper says neither.
• Cost. The worst-case time is O(mnk) §7. Memory use and measured runtime are not stated.
• Exposure model. Exposure is uniform over the k items, with no position bias §3.5. The paper leaves attention models that handle position bias to future work §9.
• Normalised utility. The utility of a list is relative to the top-k list, so μ_φ is 1 for top-k by construction §3.4 §8.

Lineage

• Builds on: fair allocation of indivisible goods, EF1 and MMS from Budish (2011), cardinality-constrained fair allocation from Biswas and Barman (2018), and the greedy round-robin from Caragiannis et al. (2016) §1 §2 §5.3 §6. These papers are named only; they are not in this wiki and no ids are given.
• Compared against: Top-k, Random-k, Mixed-k and poorest-k (PR-k) §8.
• Related journal version: arXiv:2201.01180, cited in the code README README.md. The README does not say which version FairRecPlus.py implements.
• Superseded by: not known from content in this wiki.