2024/11/24 by Dan Nissim, Nissim, Dan, Danny Segev +3 · 1 citation
Business, Management and Accounting · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Consumer Market Behavior and Pricing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2411.15727
openalex publication_date 2024/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The primary contribution of this paper resides in devising constant-factor approximation guarantees for revenue maximization in two-sided matching markets, under general pairwise rewards. A major distinction between our work and state-of-the-art results in this context (Ashlagi et al., 2022; Torrico et al., 2023) is that, for the first time, we are able to address reward maximization, reflected by assigning each customer-supplier pair an arbitrarily-valued reward. The specific type of performance guarantees we attain depends on whether one considers the customized model or the inclusive model. The fundamental difference between these settings lies in whether the platform should display to each supplier all selecting customers, as in the inclusive model, or whether the platform can further personalize this set, as in the customized model. Technically speaking, our algorithmic approach and its analysis revolve around presenting novel linear relaxations, leveraging convex stochastic orders, employing approximate dynamic programming, and developing tailor-made analytical ideas. In both models considered, these ingredients allow us to overcome the lack of submodularity and subadditivity that stems from pairwise rewards, plaguing the applicability of existing methods.