Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

The randomized communication complexity of revenue maximization

The randomized communication complexity of revenue maximization We study the communication complexity of incentive compatible auction-protocols between a monopolist seller and a single buyer with a combinatorial valuation function over n items [Rubinstein and Zhao 2021]. Motivated by the fact that revenue-optimal auctions are randomized [Thanassoulis 2004; Manelli and Vincent 2010; Briest et al. 2010; Pavlov 2011; Hart and Reny 2015] (as well as by an open problem of Babaioff, Gonczarowski, and Nisan [Babaioff et al. 2017]), we focus on the randomized communication complexity of this problem (in contrast to most prior work on deterministic communication). We design simple, incentive compatible, and revenue-optimal auction-protocols whose expected communication complexity is much (in fact infinitely) more efficient than their deterministic counterparts. We also give nearly matching lower bounds on the expected communication complexity of approximately-revenue-optimal auctions. These results follow from a simple characterization of incentive compatible auction-protocols that allows us to prove lower bounds against randomized auction-protocols. In particular, our lower bounds give the first approximation-resistant, exponential separation between communication complexity of incentivizing vs implementing a Bayesian incentive compatible social choice rule, settling an open question of Fadel and Segal [Fadel and Segal 2009]. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

The randomized communication complexity of revenue maximization

Rubinstein, Aviad; Zhao, Junyao
ACM SIGecom Exchanges , Volume 19 (2): 9 – Dec 6, 2021
Download PDF
9 pages

Loading next page...
 
/lp/association-for-computing-machinery/the-randomized-communication-complexity-of-revenue-maximization-IbrN96o0cM
Publisher
Association for Computing Machinery
Copyright
Copyright © 2021 Copyright is held by the owner/author(s)
ISSN
1551-9031
eISSN
1551-9031
DOI
10.1145/3505156.3505165
Publisher site
See Article on Publisher Site

Abstract

We study the communication complexity of incentive compatible auction-protocols between a monopolist seller and a single buyer with a combinatorial valuation function over n items [Rubinstein and Zhao 2021]. Motivated by the fact that revenue-optimal auctions are randomized [Thanassoulis 2004; Manelli and Vincent 2010; Briest et al. 2010; Pavlov 2011; Hart and Reny 2015] (as well as by an open problem of Babaioff, Gonczarowski, and Nisan [Babaioff et al. 2017]), we focus on the randomized communication complexity of this problem (in contrast to most prior work on deterministic communication). We design simple, incentive compatible, and revenue-optimal auction-protocols whose expected communication complexity is much (in fact infinitely) more efficient than their deterministic counterparts. We also give nearly matching lower bounds on the expected communication complexity of approximately-revenue-optimal auctions. These results follow from a simple characterization of incentive compatible auction-protocols that allows us to prove lower bounds against randomized auction-protocols. In particular, our lower bounds give the first approximation-resistant, exponential separation between communication complexity of incentivizing vs implementing a Bayesian incentive compatible social choice rule, settling an open question of Fadel and Segal [Fadel and Segal 2009].

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: Dec 6, 2021

Keywords: approximation

References

  • The menu-size complexity of revenue approximation
    Babaioff, ; M., ; Gonczarowski, ; A., Y.; Nisan, ; N.,
  • Pricing randomized allocations
    Briest, ; P., ; Chawla, ; S., ; Kleinberg, ; R., ; Weinberg, ; M., S.
  • A duality based unified approach to bayesian mechanism design
    Cai, ; Y., ; Devanur, ; N., ; Weinberg, ; M., S.
  • Simple mechanisms for subadditive buyers via duality
    Cai, ; Y., ; Zhao, ; M.,
  • Mechanism design for subadditive agents via an ex ante relaxation
    Chawla, ; S., ; Miller, ; B., J.
  • On the complexity of optimal lottery pricing and randomized mechanisms
    Chen, ; X., ; Diakonikolas, ; I., ; Orfanou, ; A., ; Paparas, ; D., ; Sun, ; X., ; Yannakakis, ; M.,
  • The complexity of optimal multidimensional pricing
    Chen, ; X., ; Diakonikolas, ; I., ; Paparas, ; D., ; Sun, ; X., ; Yannakakis, ; M.,
  • The Complexity of Optimal Mechanism Design
    Daskalakis, ; C., ; Deckelbaum, ; A., ; Tzamos, ; C.,
  • Strong duality for a multiple-good monopolist
    Daskalakis, ; C., ; Deckelbaum, ; A., ; Tzamos, ; C.,
  • Computational efficiency requires simple taxation
    Dobzinski, ; S.,
  • The communication cost of selfishness
    Fadel, ; R., ; Segal, ; I.,
  • Near-optimal communication lower bounds for approximate nash equilibria
    Göös, ; M., ; Rubinstein, ; A.,
  • Selling multiple correlated goods: Revenue maximization and menu-size complexity
    Hart, ; S., ; Nisan, ; N.,
  • Maximizing Revenue with Multiple Goods: Nonmonotonicity and Other Observations
    Hart, ; S., ; Reny, ; J., P.
  • Combinatorial assortment optimization
    Immorlica, ; N., ; Lucier, ; B., ; Mao, ; J., ; Syrgkanis, ; V., ; Tzamos, ; C.,
  • Approximation schemes for a buyer with independent items via symmetries
    Kothari, ; P., ; Mohan, ; D., ; Schvartzman, ; A., ; Singla, ; S., ; Weinberg, ; M., S.
  • Bayesian and Dominant-Strrategy Implementation in the Independent Private-Values Model
    Manelli, ; M., A.; Vincent, ; R., D.
  • On the hardness of being truthful
    Papadimitriou, ; H., C.; Schapira, ; M., ; Singer, ; Y.,
  • Optimal mechanism for selling two goods
    Pavlov, ; G.,
  • Simple mechanisms for a subadditive buyer and applications to revenue monotonicity
    Rubinstein, ; A., ; Weinberg, ; M., S.
  • The randomized communication complexity of randomized auctions
    Rubinstein, ; A., ; Zhao, ; J.,
  • Haggling over substitutes
    Thanassoulis, ; J.,