IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1904.12422.html
   My bibliography  Save this paper

Efficiency in Truthful Auctions via a Social Network

Author

Listed:
  • Seiji Takanashi
  • Takehiro Kawasaki
  • Taiki Todo
  • Makoto Yokoo

Abstract

In this paper, we study efficiency in truthful auctions via a social network, where a seller can only spread the information of an auction to the buyers through the buyers' network. In single-item auctions, we show that no mechanism is strategy-proof, individually rational, efficient, and weakly budget balanced. In addition, we propose $\alpha$-APG mechanisms, a class of mechanisms which operate a trade-off between efficiency and weakly budget balancedness. In multi-item auctions, there already exists a strategy-proof mechanism when all buyers need only one item. However, we indicate a counter-example to strategy-proofness in this mechanism, and to the best of our knowledge, the question of finding a strategy-proof mechanism remains open. We assume that all buyers have decreasing marginal utility and propose a generalized APG mechanism that is strategy-proof and individually rational but not efficient. Importantly, we show that this mechanism achieves the largest efficiency measure among all strategy-proof mechanisms.

Suggested Citation

  • Seiji Takanashi & Takehiro Kawasaki & Taiki Todo & Makoto Yokoo, 2019. "Efficiency in Truthful Auctions via a Social Network," Papers 1904.12422, arXiv.org.
    • Handle: RePEc:arx:papers:1904.12422
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/1904.12422
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Benjamin Edelman & Michael Ostrovsky & Michael Schwarz, 2007. "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords," American Economic Review, American Economic Association, vol. 97(1), pages 242-259, March.
    2. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    3. Myerson, Roger B. & Satterthwaite, Mark A., 1983. "Efficient mechanisms for bilateral trading," Journal of Economic Theory, Elsevier, vol. 29(2), pages 265-281, April.
    4. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    5. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    6. Dirk Bergemann & Juuso Valimaki, 2002. "Information Acquisition and Efficient Mechanism Design," Econometrica, Econometric Society, vol. 70(3), pages 1007-1033, May.
    7. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jeong, Seungwon (Eugene) & Lee, Joosung, 2024. "The groupwise-pivotal referral auction: Core-selecting referral strategy-proof mechanism," Games and Economic Behavior, Elsevier, vol. 143(C), pages 191-203.
    2. Takehiro Kawasaki & Nathanael Barrot & Seiji Takanashi & Taiki Todo & Makoto Yokoo, 2019. "Strategy-Proof and Non-Wasteful Multi-Unit Auction via Social Network," Papers 1911.08809, arXiv.org.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Song, Yangwei, 2018. "Efficient Implementation with Interdependent Valuations and Maxmin Agents," Rationality and Competition Discussion Paper Series 92, CRC TRR 190 Rationality and Competition.
    2. Jeong, Seungwon (Eugene) & Lee, Joosung, 2024. "The groupwise-pivotal referral auction: Core-selecting referral strategy-proof mechanism," Games and Economic Behavior, Elsevier, vol. 143(C), pages 191-203.
    3. Song, Yangwei, 2018. "Efficient implementation with interdependent valuations and maxmin agents," Journal of Economic Theory, Elsevier, vol. 176(C), pages 693-726.
    4. Loertscher, Simon & Mezzetti, Claudio, 2021. "A dominant strategy, double clock auction with estimation-based tatonnement," Theoretical Economics, Econometric Society, vol. 16(3), July.
    5. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Mechanism design without quasilinearity," Theoretical Economics, Econometric Society, vol. 15(2), May.
    6. Philippe Jehiel & Laurent Lamy, 2018. "A Mechanism Design Approach to the Tiebout Hypothesis," Journal of Political Economy, University of Chicago Press, vol. 126(2), pages 735-760.
    7. repec:cte:werepe:we081207 is not listed on IDEAS
    8. Matsushima, Hitoshi & Noda, Shunya, 2023. "Mechanism design with general ex-ante investments," Journal of Mathematical Economics, Elsevier, vol. 106(C).
    9. Bierbrauer, Felix & Netzer, Nick, 2016. "Mechanism design and intentions," Journal of Economic Theory, Elsevier, vol. 163(C), pages 557-603.
    10. Matthias Lang, 2020. "Mechanism Design with Narratives," CESifo Working Paper Series 8502, CESifo.
    11. Michael Ostrovsky & Michael Schwarz, 2023. "Reserve Prices in Internet Advertising Auctions: A Field Experiment," Journal of Political Economy, University of Chicago Press, vol. 131(12), pages 3352-3376.
    12. Philippe Jehiel & Benny Moldovanu, 2005. "Allocative and Informational Externalities in Auctions and Related Mechanisms," Levine's Bibliography 784828000000000490, UCLA Department of Economics.
    13. Committee, Nobel Prize, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.
    14. Tuomas Sandholm & Anton Likhodedov, 2015. "Automated Design of Revenue-Maximizing Combinatorial Auctions," Operations Research, INFORMS, vol. 63(5), pages 1000-1025, October.
    15. Figueroa, Nicolás & Skreta, Vasiliki, 2012. "Asymmetric partnerships," Economics Letters, Elsevier, vol. 115(2), pages 268-271.
    16. Esther Gal-Or & Anindya Ghose, 2005. "The Economic Incentives for Sharing Security Information," Information Systems Research, INFORMS, vol. 16(2), pages 186-208, June.
    17. Carbajal, Juan Carlos, 2010. "On the uniqueness of Groves mechanisms and the payoff equivalence principle," Games and Economic Behavior, Elsevier, vol. 68(2), pages 763-772, March.
    18. Yukun Cheng & Xiaotie Deng & Dominik Scheder, 2022. "Recent studies of agent incentives in internet resource allocation and pricing," Annals of Operations Research, Springer, vol. 314(1), pages 49-76, July.
    19. Simon Loertscher & Leslie M. Marx, 2022. "To sell public or private goods," Review of Economic Design, Springer;Society for Economic Design, vol. 26(3), pages 385-415, September.
    20. Kenneth C. Wilbur & Linli Xu & David Kempe, 2013. "Correcting Audience Externalities in Television Advertising," Marketing Science, INFORMS, vol. 32(6), pages 892-912, November.
    21. Devanur, Nikhil R. & Hartline, Jason D. & Yan, Qiqi, 2015. "Envy freedom and prior-free mechanism design," Journal of Economic Theory, Elsevier, vol. 156(C), pages 103-143.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:1904.12422. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.