2026-07-23T19:58:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15597 2024-03-06T10:55:42Z ddc:004 open_access

Maximizing Revenue in the Presence of Intermediaries Aggarwal, Gagan Bhawalkar, Kshipra Guruganesh, Guru Perlroth, Andres Mechanism Design Revenue Maximization Posted Price Mechanisms We study the mechanism design problem of selling k items to unit-demand buyers with private valuations for the items. A buyer either participates directly in the auction or is represented by an intermediary, who represents a subset of buyers. Our goal is to design robust mechanisms that are independent of the demand structure (i.e. how the buyers are partitioned across intermediaries), and perform well under a wide variety of possible contracts between intermediaries and buyers. We first consider the case of k identical items where each buyer draws its private valuation for an item i.i.d. from a known λ-regular distribution. We construct a robust mechanism that, independent of the demand structure and under certain conditions on the contracts between intermediaries and buyers, obtains a constant factor of the revenue that the mechanism designer could obtain had she known the buyers' valuations. In other words, our mechanism’s expected revenue achieves a constant factor of the optimal welfare, regardless of the demand structure. Our mechanism is a simple posted-price mechanism that sets a take-it-or-leave-it per-item price that depends on k and the total number of buyers, but does not depend on the demand structure or the downstream contracts. Next we generalize our result to the case when the items are not identical. We assume that the item valuations are separable, i.e. v_{i j} = η_j v_i for buyer i and item j, with each private v_i drawn i.i.d. from a known λ-regular distribution. For this case, we design a mechanism that obtains at least a constant fraction of the optimal welfare, by using a menu of posted prices. This mechanism is also independent of the demand structure, but makes a relatively stronger assumption on the contracts between intermediaries and buyers, namely that each intermediary prefers outcomes with a higher sum of utilities of the subset of buyers represented by it. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gagan Aggarwal and Kshipra Bhawalkar and Guru Guruganesh and Andres Perlroth 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.1 urn:nbn:de:0030-drops-155979 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.1 eng https://creativecommons.org/licenses/by/4.0/legalcode