Skip to main content
Springer Nature Link
Log in

Removal and Threshold Pricing: Truthful Two-Sided Markets with Multi-dimensional Participants

  • Conference paper
  • First Online:
Algorithmic Game Theory (SAGT 2018)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 11059))

Included in the following conference series:

Abstract

We consider mechanisms for markets that are two-sided and have agents with multi-dimensional strategic spaces on at least one side. The agents of the market are strategic and act to optimize their own utilities, while the mechanism designer aims to optimize a social goal, i.e., the gain from trade. We focus on one example of this setting motivated by a foreseeable privacy-aware future form of online advertising.

Recently, it has been suggested that markets of user information built around information brokers could be introduced to the online advertising ecosystem to overcome online privacy concerns. Such markets give users control over which data gets shared in online advertising exchanges. We describe a model for the above form of online advertising and design two mechanisms for this model. The first is a deterministic mechanism which is related to the vast literature on mechanism design through trade reduction and allows agents with a multi-dimensional strategic space. The second is a randomized mechanism that can handle a more general version of the model. We provide theoretical analyses of our mechanisms and study their performance using simulations based on real-world data.

This work was supported by the Horizon 2020 funded project TYPES (Project number: 653449. Call Identifier H2020-DS-2014-1).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (France)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 52.74
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We often refer to agents with a multi-dimensional strategic space as multi-dimensional agents.

  2. 2.

    The sole exception for this is the work of Segal-Halevi et al. [21], which was done independently in parallel to our work. However, [21] does not offer a solution for the deterministic multi-dimensional strategic spaces case.

  3. 3.

    Here and throughout the paper, a reference to domination of strategies should be understood as a reference to weak domination. We never refer to strong domination.

  4. 4.

    The parameters \(\gamma \) and \(\alpha \) both bound the maximum capacity of the agents, and they are related by \(\alpha = \gamma /\tau \). We chose to formulate Theorems 1 and 2 in terms of the parameter that the mechanism corresponding to each theorem assumes access to.

References

  1. Ashlagi, I., Monderer, D., Tennenholtz, M.: Mediators in position auctions. Games Econ. Behav. 67, 2–21 (2009)

    Article  MathSciNet  Google Scholar 

  2. Babaioff, M., Nisan, N., Pavlov, E.: Mechanisms for a spatially distributed market. Games Econ. Behav. 66(2), 660–684 (2009)

    Article  MathSciNet  Google Scholar 

  3. Babaioff, M., Walsh, W.E.: Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation. Decis. Support Syst. 39(1), 123–149 (2005)

    Article  Google Scholar 

  4. Blumrosen, L., Dobzinski, S.: Reallocation mechanisms. In: EC, pp. 617–640. ACM, New York (2014)

    Google Scholar 

  5. Blumrosen, L., Mizrahi, Y.: Approximating gains-from-trade in bilateral trading. In: WINE, pp. 400–413 (2016)

    Google Scholar 

  6. Brustle, J., Cai, Y., Wu, F., Zhao, M.: Approximating gains from trade in two-sided markets via simple mechanisms. In: EC, pp. 589–590 (2017)

    Google Scholar 

  7. Chaib-draa, B., Müller, J. (eds.): Multiagent Based Supply Chain Management. SCI, vol. 28. Springer, Heidelberg (2006). https://doi.org/10.1007/978-3-540-33876-5

    Book  MATH  Google Scholar 

  8. Chen, R.R., Roundy, R.O., Zhang, R.Q., Janakiraman, G.: Efficient auction mechanisms for supply chain procurement. Manag. Sci. 51(3), 467–482 (2005)

    Article  Google Scholar 

  9. Clarke, E.H.: Multipart pricing of public goods. Public Choice 2, 17–33 (1971)

    Article  Google Scholar 

  10. Colini-Baldeschi, R., Goldberg, P., de Keijzer, B., Leonardi, S., Turchetta, S.: Fixed price approximability of the optimal gain from trade. In: Devanur, N.R., Lu, P. (eds.) WINE 2017. LNCS, vol. 10660, pp. 146–160. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71924-5_11

    Chapter  Google Scholar 

  11. Colini-Baldeschi, R., Goldberg, P.W., de Keijzer, B., Leonardi, S., Roughgarden, T., Turchetta, S.: Approximately efficient two-sided combinatorial auctions. In: EC, pp. 591–608. ACM, New York (2017)

    Google Scholar 

  12. Colini-Baldeschi, R., de Keijzer, B., Leonardi, S., Turchetta, S.: Approximately efficient double auctions with strong budget balance. In: SODA, pp. 1424–1443. Society for Industrial and Applied Mathematics, Philadelphia (2016)

    Google Scholar 

  13. Facebook: CEO Mark Zuckerberg testifies before senate on user data (2018). https://m.youtube.com/watch?v=qAZiDRonYZI

  14. Feldman, J., Mirrokni, V.S., Muthukrishnan, S., Pai, M.M.: Auctions with intermediaries: extended abstract. In: EC, pp. 23–32. ACM, New York (2010)

    Google Scholar 

  15. Feldman, M., Gonen, R.: Double-sided markets with strategic multi-dimensional players. CoRR abs/1603.08717 (2016). http://arxiv.org/abs/1603.08717

  16. Gonen, M., Gonen, R., Pavlov, E.: Generalized trade reduction mechanisms. In: EC, pp. 20–29. ACM, New York (2007)

    Google Scholar 

  17. Gonen, R., Egri, O.: DYCOM: a dynamic truthful budget balanced double-sided combinatorial market. In: The 16th Conference on Autonomous Agents and Multi Agent Systems (AAMAS), May 2017, Brazil, pp. 1556–1558 (2017)

    Google Scholar 

  18. Groves, T.: Incentives in teams. Econometrica 41, 617–631 (1973)

    Article  MathSciNet  Google Scholar 

  19. McAfee, R.P.: A dominant strategy double auction. J. Econ. Theory 56, 434–450 (1992)

    Article  MathSciNet  Google Scholar 

  20. Myerson, R.B., Satterthwaite, M.A.: Efficient mechanisms for bilateral trading. J. Econ. Theory 29, 265–281 (1983)

    Article  MathSciNet  Google Scholar 

  21. Segal-Halevi, E., Hassidim, A., Aumann, Y.: MUDA: a truthful multi-unit double-auction mechanism. In: Proceeding of AAAI (2018)

    Google Scholar 

  22. Stavrogiannis, L.C., Gerding, E.H., Polukarov, M.: Auction mechanisms for demand-side intermediaries in online advertising exchanges. In: AAMAS, pp. 5–9. International Foundation for Autonomous Agents and Multiagent Systems, Richland (2014)

    Google Scholar 

  23. Vickrey, W.: Counterspeculation, auctions and competitive sealed tenders. J. Financ. 16, 8–37 (1961)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, The Open University of Israel, The Dorothy de Rothschild Campus, 1 University Road, 43107, Raanana, Israel

    Moran Feldman

  2. Department of Management and Economics, The Open University of Israel, The Dorothy de Rothschild Campus, 1 University Road, 43107, Raanana, Israel

    Rica Gonen

Authors
  1. Moran Feldman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rica Gonen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Moran Feldman or Rica Gonen .

Editor information

Editors and Affiliations

  1. Peking University, Beijing, China

    Xiaotie Deng

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Feldman, M., Gonen, R. (2018). Removal and Threshold Pricing: Truthful Two-Sided Markets with Multi-dimensional Participants. In: Deng, X. (eds) Algorithmic Game Theory. SAGT 2018. Lecture Notes in Computer Science(), vol 11059. Springer, Cham. https://doi.org/10.1007/978-3-319-99660-8_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-99660-8_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-99659-2

  • Online ISBN: 978-3-319-99660-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation