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

Exponential Communication Separations between Notions of Selfishness

Author

Listed:
  • Aviad Rubinstein
  • Raghuvansh R. Saxena
  • Clayton Thomas
  • S. Mathew Weinberg
  • Junyao Zhao

Abstract

We consider the problem of implementing a fixed social choice function between multiple players (which takes as input a type $t_i$ from each player $i$ and outputs an outcome $f(t_1,\ldots, t_n)$), in which each player must be incentivized to follow the protocol. In particular, we study the communication requirements of a protocol which: (a) implements $f$, (b) implements $f$ and computes payments that make it ex-post incentive compatible (EPIC) to follow the protocol, and (c) implements $f$ and computes payments in a way that makes it dominant-strategy incentive compatible (DSIC) to follow the protocol. We show exponential separations between all three of these quantities, already for just two players. That is, we first construct an $f$ such that $f$ can be implemented in communication $c$, but any EPIC implementation of $f$ (with any choice of payments) requires communication $\exp(c)$. This answers an open question of [FS09, BBS13]. Second, we construct an $f$ such that an EPIC protocol implements $f$ with communication $C$, but all DSIC implementations of $f$ require communication $\exp(C)$.

Suggested Citation

  • Aviad Rubinstein & Raghuvansh R. Saxena & Clayton Thomas & S. Mathew Weinberg & Junyao Zhao, 2020. "Exponential Communication Separations between Notions of Selfishness," Papers 2012.14898, arXiv.org, revised Jun 2021.
    • Handle: RePEc:arx:papers:2012.14898
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Ashlagi, Itai & Gonczarowski, Yannai A., 2018. "Stable matching mechanisms are not obviously strategy-proof," Journal of Economic Theory, Elsevier, vol. 177(C), pages 405-425.
    2. Shengwu Li, 2017. "Obviously Strategy-Proof Mechanisms," American Economic Review, American Economic Association, vol. 107(11), pages 3257-3287, November.
    3. Fadel, Ronald & Segal, Ilya, 2009. "The communication cost of selfishness," Journal of Economic Theory, Elsevier, vol. 144(5), pages 1895-1920, September.
    4. Shahar Dobzinski & Noam Nisan & Michael Schapira, 2010. "Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders," Mathematics of Operations Research, INFORMS, vol. 35(1), pages 1-13, February.
    5. Babaioff, Moshe & Blumrosen, Liad & Schapira, Michael, 2013. "The communication burden of payment determination," Games and Economic Behavior, Elsevier, vol. 77(1), pages 153-167.
    6. Nisan, Noam & Segal, Ilya, 2006. "The communication requirements of efficient allocations and supporting prices," Journal of Economic Theory, Elsevier, vol. 129(1), pages 192-224, 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. Ran Canetti & Amos Fiat & Yannai A. Gonczarowski, 2023. "Zero-Knowledge Mechanisms," Papers 2302.05590, arXiv.org.
    2. Yannai A. Gonczarowski & Clayton Thomas, 2022. "Structural Complexities of Matching Mechanisms," Papers 2212.08709, arXiv.org, revised Mar 2024.
    3. Yannai A. Gonczarowski & Ori Heffetz & Clayton Thomas, 2022. "Strategyproofness-Exposing Mechanism Descriptions," Papers 2209.13148, arXiv.org, revised Jul 2023.

    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. Mackenzie, Andrew & Zhou, Yu, 2022. "Menu mechanisms," Journal of Economic Theory, Elsevier, vol. 204(C).
    2. Pablo Guillen & Róbert F. Veszteg, 2021. "Strategy-proofness in experimental matching markets," Experimental Economics, Springer;Economic Science Association, vol. 24(2), pages 650-668, June.
    3. Breitmoser, Yves & Schweighofer-Kodritsch, Sebastian, 2019. "Obviousness around the clock," Discussion Papers, Research Unit: Market Behavior SP II 2019-203, WZB Berlin Social Science Center.
    4. Arribillaga, R. Pablo & Massó, Jordi & Neme, Alejandro, 2023. "All sequential allotment rules are obviously strategy-proof," Theoretical Economics, Econometric Society, vol. 18(3), July.
    5. Andrew Komo & Scott Duke Kominers & Tim Roughgarden, 2024. "Shill-Proof Auctions," Papers 2404.00475, arXiv.org, revised Nov 2024.
    6. Ryuji Sano, 2021. "Dynamic communication mechanism design," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(1), pages 163-180, July.
    7. Yannai A. Gonczarowski & Ori Heffetz & Clayton Thomas, 2022. "Strategyproofness-Exposing Mechanism Descriptions," Papers 2209.13148, arXiv.org, revised Jul 2023.
    8. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    9. Tamura, Yuki, 2023. "Object reallocation problems with single-dipped preferences," Games and Economic Behavior, Elsevier, vol. 140(C), pages 181-196.
    10. Meisner, Vincent & von Wangenheim, Jonas, 2023. "Loss aversion in strategy-proof school-choice mechanisms," Journal of Economic Theory, Elsevier, vol. 207(C).
    11. Yannai A. Gonczarowski & Clayton Thomas, 2022. "Structural Complexities of Matching Mechanisms," Papers 2212.08709, arXiv.org, revised Mar 2024.
    12. Shengwu Li, 2024. "Designing Simple Mechanisms," Papers 2403.18694, arXiv.org, revised Jul 2024.
    13. Yu Zhou & Shigehiro Serizawa, 2020. "Serial Vickrey Mechanism," ISER Discussion Paper 1095, Institute of Social and Economic Research, Osaka University.
    14. Bó, Inácio & Hakimov, Rustamdjan, 2022. "The iterative deferred acceptance mechanism," Games and Economic Behavior, Elsevier, vol. 135(C), pages 411-433.
    15. Vincent Meisner & Jonas von Wangenheim, 2022. "Loss aversion in strategy-proof school-choice mechanisms," Papers 2207.14666, arXiv.org.
    16. Mandal, Pinaki & Roy, Souvik, 2022. "On obviously strategy-proof implementation of fixed priority top trading cycles with outside options," Economics Letters, Elsevier, vol. 211(C).
    17. Gonczarowski, Yannai A. & Nisan, Noam & Ostrovsky, Rafail & Rosenbaum, Will, 2019. "A stable marriage requires communication," Games and Economic Behavior, Elsevier, vol. 118(C), pages 626-647.
    18. Arribillaga, R. Pablo & Massó, Jordi & Neme, Alejandro, 2020. "On obvious strategy-proofness and single-peakedness," Journal of Economic Theory, Elsevier, vol. 186(C).
    19. Yannai A. Gonczarowski & Ori Heffetz & Guy Ishai & Clayton Thomas, 2024. "Describing Deferred Acceptance and Strategyproofness to Participants: Experimental Analysis," Papers 2409.18166, arXiv.org.
    20. Hagenbach, Jeanne & Perez-Richet, Eduardo, 2018. "Communication with evidence in the lab," Games and Economic Behavior, Elsevier, vol. 112(C), pages 139-165.

    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:2012.14898. 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.