[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3465456.3467632acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article

Truthful Mechanisms for Two-Sided Markets via Prophet Inequalities

Published: 18 July 2021 Publication History

Abstract

We design novel mechanisms for welfare-maximization in two-sided markets. That is, there are buyers willing to purchase items and sellers holding items initially, both acting rationally and strategically in order to maximize utility. Our mechanisms are designed based on a powerful correspondence between two-sided markets and prophet inequalities. They satisfy individual rationality, dominant-strategy incentive compatibility, budget-balance constraints and give constant-factor approximations to the optimal social welfare. We improve previous results in several settings: Our main focus is on matroid double auctions, where the set of buyers who obtain an item needs to be independent in a matroid. We construct two mechanisms, the first being a 1/3-approximation of the optimal social welfare satisfying strong budget-balance and requiring the agents to trade in a customized order, the second being a 1/2-approximation, weakly budget-balanced and able to deal with online arrival determined by an adversary. In addition, we construct constant-factor approximations in two-sided markets when buyers need to fulfill a knapsack constraint. Also, in combinatorial double auctions, where buyers have valuation functions over item bundles instead of being interested in only one item, using similar techniques, we design a mechanism which is a $1/2$-approximation of the optimal social welfare, strongly budget-balanced and can deal with online arrival of agents in an adversarial order.

References

[1]
L. Blumrosen and S. Dobzinski. Reallocation mechanisms. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC '14, page 617, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450325653. 10.1145/2600057.2602843. URL https://doi.org/10.1145/2600057.2602843.
[2]
L. Blumrosen and S. Dobzinski. (almost) efficient mechanisms for bilateral trading. CoRR, abs/1604.04876, 2016. URL http://arxiv.org/abs/1604.04876.
[3]
A. Braun and T. Kesselheim. Truthful mechanisms for two-sided markets via prophet inequalities, 2021. URL https://arxiv.org/abs/2105.15032.
[4]
R. Colini-Baldeschi, B. de Keijzer, S. Leonardi, and S. Turchetta. Approximately efficient double auctions with strong budget balance. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, page 1424--1443, USA, 2016. Society for Industrial and Applied Mathematics. ISBN 9781611974331.
[5]
R. Colini-Baldeschi, P. W. Goldberg, B. d. Keijzer, S. Leonardi, T. Roughgarden, and S. Turchetta. Approximately efficient two-sided combinatorial auctions. ACM Trans. Econ. Comput., 8 (1), Mar. 2020. ISSN 2167--8375. 10.1145/3381523. URL https://doi.org/10.1145/3381523.
[6]
P. Duetting, M. Feldman, T. Kesselheim, and B. Lucier. Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. In C. Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15--17, 2017, pages 540--551. IEEE Computer Society, 2017. 10.1109/FOCS.2017.56. URL https://doi.org/10.1109/FOCS.2017.56.
[7]
ing et al.(2014)Dütting, Roughgarden, and Talgam-Cohen]10.1145/2600057.2602854P. Dütting, T. Roughgarden, and I. Talgam-Cohen. Modularity and greed in double auctions. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC '14, page 241--258, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450325653. 10.1145/2600057.2602854. URL https://doi.org/10.1145/2600057.2602854.
[8]
M. Feldman, N. Gravin, and B. Lucier. Combinatorial auctions via posted prices. In P. Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4--6, 2015, pages 123--135. SIAM, 2015. 10.1137/1.9781611973730.10. URL https://doi.org/10.1137/1.9781611973730.10.
[9]
M. Gerstgrasser, P. W. Goldberg, B. de Keijzer, P. Lazos, and A. Skopalik. Multi-unit bilateral trade. Proceedings of the AAAI Conference on Artificial Intelligence, 33 (01): 1973--1980, Jul. 2019. 10.1609/aaai.v33i01.33011973. URL https://ojs.aaai.org/index.php/AAAI/article/view/4025.
[10]
R. Kleinberg and S. M. Weinberg. Matroid prophet inequalities. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 123----136, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450312455. 10.1145/2213977.2213991. URL https://doi.org/10.1145/2213977.2213991.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
EC '21: Proceedings of the 22nd ACM Conference on Economics and Computation
July 2021
950 pages
ISBN:9781450385541
DOI:10.1145/3465456
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 July 2021

Check for updates

Author Tags

  1. bilateral trade
  2. double auctions
  3. mechanism design
  4. prophet inequalities
  5. two-sided markets

Qualifiers

  • Research-article

Conference

EC '21
Sponsor:

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25
The 25th ACM Conference on Economics and Computation
July 7 - 11, 2025
Stanford , CA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)22
  • Downloads (Last 6 weeks)4
Reflects downloads up to 31 Dec 2024

Other Metrics

Citations

Cited By

View all

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media