One-sentence Summary

This work from Harvard University addresses revenue-optimal matching in two-sided markets with unit-supply sellers and unit-demand buyers, proving the platform's problem is NP-hard even when each buyer knows at most two sellers off-platform, and providing a polynomial-time algorithm for the special case where buyers value all sellers equally and know only one seller off-platform.

Key Contributions

• The paper models platform recommendation in a two-sided market with unit-supply sellers and unit-demand buyers, representing off-platform transaction opportunities as edges in a bipartite graph and defining revenue as a fixed percentage of competitive-equilibrium prices for recommended transactions.

• The paper shows that selecting revenue-maximizing recommendations is NP-hard even when each buyer has at most two off-platform seller edges.

• The paper provides a polynomial-time algorithm that optimally solves the revenue-maximizing matching problem in the homogeneous-good case, where all buyers value sellers equally and each buyer has one off-platform seller edge.

Introduction

Two-sided platforms face a difficult recommendation problem because the choice of which sellers to present can change prices, consumer outcomes, and platform commissions. Recommending a lower-priced seller may help buyers find better deals, but it can reduce the platform’s revenue, while recommending a higher-priced seller may raise commission potential yet risk losing the transaction to an off-platform alternative. Prior work on competitive equilibrium networks, platform design, and recommender systems has not fully captured the case where a platform strategically creates transaction edges and market-clearing prices interact across the whole market. The authors model buyers and sellers as a bipartite graph, let the platform add at most one new transaction opportunity for each buyer and seller, and show that choosing which edges to add to maximize revenue is computationally hard in the general case. They also identify a tractable homogeneous goods setting and develop an efficient algorithm, clarifying both where the revenue-optimal matching problem can be solved and where it becomes complex.

Method

The authors model the marketplace as a two-sided matching environment. Formally, the market is represented by a bipartite graph $G = (B, S, E)$G=(B,S,E), where $B = \{b_1, \ldots, b_n\}$B={b1​,…,bn​} is the set of buyers with unit demand, $S = \{s_1, \ldots, s_m\}$S={s1​,…,sm​} is the set of sellers with unit supply, and $E$E is the set of feasible transaction edges. A buyer $b_i$bi​ can transact with a seller $s_j$sj​ only if $(b_i, s_j) \in E$(bi​,sj​)∈E. Each edge carries a valuation weight $v_{ij}$vij​, representing how much buyer $b_i$bi​ values seller $s_j$sj​’s item. The market clears through a competitive equilibrium, which corresponds to a maximum weight matching on $G$G together with item prices $p_j$pj​ that support the equilibrium. Sellers are assumed to extract maximal surplus while preserving equilibrium, so prices are defined by

where $W(\cdot)$W(⋅) denotes the total weight of a maximum weight matching.

To capture the role of a platform, the market is decomposed into an existing world graph $G_w = (B, S, E_w)$Gw​=(B,S,Ew​) and a set of platform edges $E_p$Ep​, where $E_p \cap E_w = \varnothing$Ep​∩Ew​=∅. The world edges represent transaction opportunities available outside the platform, while the platform selects additional recommendation edges that enable on-platform transactions. Given full knowledge of buyer valuations and the existing world graph, the platform chooses $E_p$Ep​ together with a maximum weight matching to maximize the total revenue generated by items sold through platform edges. The resulting revenue objective can be written conceptually as the sum of equilibrium item prices for sellers matched through the added platform edges.

The analysis shows that this platform intervention problem is computationally difficult in general. It remains NP-hard even under highly restricted valuation structures and even when some buyers have limited outside options. To obtain a tractable setting, the authors study the case where buyers have homogeneous valuations, meaning $v_{ij} = v_i$vij​=vi​ for every seller $j$j, and each buyer has at most one existing world edge. Under these assumptions, the intervention structure can be characterized more cleanly. Each seller defines a seller subgraph containing that seller and all buyers connected to it through world edges. After sorting these seller subgraphs by the highest buyer value within each subgraph, the revenue-optimal set of platform edges connects the subgraphs into contiguous cycles and at most one chain. The cycles have length at most three, and the chain attaches to a cycle. As shown in the figure below:

The example illustrates the structural decomposition in the homogeneous valuation case. The black links denote existing world opportunities, while the pink links denote the platform edges selected by the revenue-optimal strategy. In such markets, every transaction in the optimal outcome can be supported by platform edges alone, and the resulting cycle and chain arrangement captures how added recommendations reshape the competitive equilibrium.

Based on this structure, the algorithm reduces the optimization to a sequence of local searches over possible cycle anchors. For each candidate contiguous cycle of length at most three, the algorithm fixes the cycle and removes the involved seller subgraphs from consideration. It then computes, via dynamic programming, the best revenue obtainable by connecting an initial contiguous segment of the remaining subgraphs through cycles. It also computes the revenue achievable by linking the remaining suffix of subgraphs into a chain. The best revenue for that fixed anchor is given by

where $DP[i]$DP[i] is the optimal cycle-based revenue from the first $i$i subgraphs and $R[i]$R[i] is the chain-based revenue from the subsequent subgraphs. Repeating this procedure over all possible fixed cycle anchors yields the global optimum, with the overall algorithm running in $O(n^2)$O(n2) time for the restricted homogeneous valuation setting.