Document Open Access Logo

Online Market Intermediation

Authors Yiannis Giannakopoulos, Elias Koutsoupias, Philip Lazos

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.47.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Yiannis Giannakopoulos
Elias Koutsoupias
Philip Lazos

Cite As Get BibTex

Yiannis Giannakopoulos, Elias Koutsoupias, and Philip Lazos. Online Market Intermediation. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.47

Abstract

We study a dynamic market setting where an intermediary interacts with an unknown large sequence of agents that can be either sellers or buyers: their identities, as well as the sequence length n, are decided in an adversarial, online way. Each agent is interested in trading a single item, and all items in the market are identical. The intermediary has some prior, incomplete knowledge of the agents' values for the items: all seller values are independently drawn from the same distribution F_S, and all buyer values from F_B. The two distributions may differ, and we make common regularity assumptions, namely that F_B is MHR and F_S is log-concave.
	
We focus on online, posted-price mechanisms, and analyse two objectives: that of maximizing the intermediary's profit and that of maximizing the social welfare, under a competitive analysis benchmark. First, on the negative side, for general agent sequences we prove tight competitive ratios of Theta(\sqrt(n)) and Theta(\ln n), respectively for the two objectives. On the other hand, under the extra assumption that the intermediary knows some bound \alpha on the ratio between the number of sellers and buyers, we design asymptotically optimal online mechanisms with competitive ratios of 1+o(1) and 4, respectively. Additionally, we study the model where the number of items that can be stored in stock throughout the execution is bounded, in which case the competitive ratio for the profit is improved to O(ln n).

Subject Classification

Keywords
  • optimal auctions
  • bilateral trade
  • sequential auctions
  • online algorithms
  • competitive analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Moshe Babaioff, Liad Blumrosen, Shaddin Dughmi, and Yaron Singer. Posting Prices with Unknown Distributions. In Innovations in Computer Science (ICS), jan 2011. URL: http://conference.itcs.tsinghua.edu.cn/ICS2011/content/paper/35.pdf.
  2. Moshe Babaioff, Shaddin Dughmi, Robert D. Kleinberg, and Aleksandrs Slivkins. Dynamic pricing with limited supply. ACM Trans. Economics and Comput., 3(1):4, 2015. URL: http://dx.doi.org/10.1145/2559152.
  3. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Online auctions and generalized secretary problems. SIGecom Exch., 7(2):7:1-7:11, June 2008. URL: http://dx.doi.org/10.1145/1399589.1399596.
  4. Ashwinkumar Badanidiyuru, Robert Kleinberg, and Yaron Singer. Learning on a budget: posted price mechanisms for online procurement. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 128-145. ACM, 2012. URL: http://dl.acm.org/citation.cfm?id=2229026.
  5. Ziv Bar-Yossef, Kirsten Hildrum, and Felix Wu. Incentive-compatible online auctions for digital goods. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'02, pages 964-970, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=545381.545506.
  6. Richard E. Barlow and Albert W. Marshall. Bounds for Distributions with Monotone Hazard Rate, I. The Annals of Mathematical Statistics, 35(3):1234-1257, sep 1964. URL: http://projecteuclid.org/euclid.aoms/1177703281, URL: http://dx.doi.org/10.1214/aoms/1177703281.
  7. Avrim Blum and Jason D. Hartline. Near-optimal online auctions. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1156-1163. Society for Industrial and Applied Mathematics, 2005. URL: http://dl.acm.org/citation.cfm?id=1070597.
  8. Avrim Blum, Tuomas Sandholm, and Martin Zinkevich. Online algorithms for market clearing. Journal of the ACM (JACM), 53(5):845-879, 2006. URL: http://dl.acm.org/citation.cfm?id=1183913.
  9. Liad Blumrosen and Shahar Dobzinski. (Almost) Efficient Mechanisms for Bilateral Trading. arXiv preprint arXiv:1604.04876, 2016. URL: http://arxiv.org/abs/1604.04876.
  10. Liad Blumrosen and Thomas Holenstein. Posted prices vs. negotiations: An asymptotic analysis. In Proceedings of the 9th ACM Conference on Electronic Commerce, EC'08, pages 49-49, New York, NY, USA, 2008. ACM. URL: http://dx.doi.org/10.1145/1386790.1386801.
  11. Liad Blumrosen and Yehonatan Mizrahi. Approximating gains-from-trade in bilateral trading. In Web and Internet Economics, pages 400-413. Springer, Berlin, Heidelberg, December 2016. URL: http://dx.doi.org/10.1007/978-3-662-54110-4_28.
  12. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998. Google Scholar
  13. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 311-320. ACM, 2010. URL: http://dl.acm.org/citation.cfm?id=1806733.
  14. Riccardo Colini-Baldeschi, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Approximately efficient double auctions with strong budget balance. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1424-1443. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  15. X Deng, P Goldberg, B Tang, and J Zhang. Revenue maximization in a bayesian double auction market. Theoretical Computer Science, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2014.04.013.
  16. Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 123-135. Society for Industrial and Applied Mathematics, 2015. Google Scholar
  17. Matthias Gerstgrasser, Paul W Goldberg, and Elias Koutsoupias. Revenue maximization for market intermediation with correlated priors. In International Symposium on Algorithmic Game Theory, pages 273-285. Springer, 2016. Google Scholar
  18. Yiannis Giannakopoulos, Elias Koutsoupias, and Philip Lazos. Online market intermediation. CoRR, abs/1703.09279, 2017. URL: http://arxiv.org/abs/1703.09279.
  19. Yiannis Giannakopoulos and Maria Kyropoulou. The VCG Mechanism for Bayesian Scheduling. In Proceedings of the 11th Conference on Web and Internet Economics, volume 9470 of Lecture Notes in Computer Science, pages 343-356. Springer, 2015. URL: http://arxiv.org/abs/1509.07455, URL: http://dx.doi.org/10.1007/978-3-662-48995-6_25.
  20. Mohammad T. Hajiaghayi. Online auctions with re-usable goods. In Proceedings of the 6th ACM conference on Electronic commerce, pages 165-174. ACM, 2005. URL: http://dl.acm.org/citation.cfm?id=1064027.
  21. Mohammad Taghi Hajiaghayi, Robert Kleinberg, and David C. Parkes. Adaptive limited-supply online auctions. In Proceedings of the 5th ACM conference on Electronic commerce, pages 71-80. ACM, 2004. URL: http://dl.acm.org/citation.cfm?id=988784.
  22. Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In AAAI, volume 7, pages 58-65, 2007. Google Scholar
  23. Robert Kleinberg and Tom Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS'03, pages 594-, Washington, DC, USA, 2003. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=946243.946352.
  24. Elias Koutsoupias and George Pierrakos. On the competitive ratio of online sampling auctions. ACM Transactions on Economics and Computation, 1(2):10, May 2013. URL: http://dl.acm.org/citation.cfm?id=2465769.2465775.
  25. R. Preston McAfee. A dominant strategy double auction. Journal of Economic Theory, 56(2):434-450, 1992. URL: http://dx.doi.org/10.1016/0022-0531(92)90091-U.
  26. Roger B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29(2):265-281, 1983. Google Scholar
  27. Rad Niazadeh, Yang Yuan, and Robert Kleinberg. Simple and near-optimal mechanisms for market intermediation. In International Conference on Web and Internet Economics, pages 386-399. Springer, 2014. Google Scholar
  28. David C. Parkes. Online mechanisms. In Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors, Algorithmic Game Theory, chapter 16. Cambridge University Press, New York, NY, USA, 2007. Google Scholar
  29. Qiqi Yan. Mechanism design via correlation gap. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'11, pages 710-719. SIAM, 2011. URL: http://dl.acm.org/citation.cfm?id=2133036.2133092.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact