Research map / Learning theory and algorithms / Submodular and game algorithms
Strategic Recommendation: Revenue Optimal Matching for Online Platforms (Student Abstract)
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies how a revenue-maximizing platform should recommend one off-platform seller per buyer in a two-sided market with competitive-equilibrium pricing, proving NP-hardness and giving a polynomial algorithm for a homogeneous-valuation special case.
Problem
Platform choice of which seller to recommend to each buyer in a two-sided market with unit-demand buyers and unit-supply sellers, where transactions and prices form a competitive equilibrium and the platform earns a commission on recommended transactions.
Approach
Models the platform's recommendation problem as choosing added platform edges in a buyer-seller bipartite graph under competitive-equilibrium clearing, shows general hardness, and exploits seller-subgraph cycle/chain structure under homogeneous valuations to get an O(n^2) dynamic program.
Key results
- The general platform revenue problem is NP-hard, even when each buyer knows at most two sellers off platform (Theorem 1).
- With homogeneous buyer valuations and at most one off-platform edge per buyer, the platform problem is solvable in O(n^2) time (Theorem 2).
- Lemma 1 shows an optimal platform strategy whose transactions form cycles of length at most three and at most one chain over contiguous seller subgraphs.
Limitations
- General problem is NP-hard, so no efficient exact algorithm for arbitrary valuations.
- Assumes platform has complete knowledge of all buyer valuations.
- Tractable result only covers homogeneous valuations with at most one off-platform edge per buyer.
Experimental setup
Builds on: Kranton and Minehart network model Chen and Deng envy-free pricing hardness Gul and Stacchetti competitive equilibrium
Closest papers by meaning
- Nearly Optimal Competitive Ratio for Online Allocation Problems with Two-sided Resource Constraints and Finite Requests (ICML 2023 · similarity 0.86)
- Revenue Maximization Under Sequential Price Competition Via The Estimation Of $s$-Concave Demand Functions (ICLR 2026 · similarity 0.86)
- Online Market Equilibrium with Application to Fair Division (NeurIPS 2021 · similarity 0.85)
- Learning Revenue Maximization Using Posted Prices for Stochastic Strategic Patient Buyers (AAAI 2023 · similarity 0.85)
- Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets (NeurIPS 2025 · similarity 0.84)
- Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.