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

It's Not All Black and White: Degree of Truthfulness for Risk-Avoiding Agents

Author

Listed:
  • Eden Hartman
  • Erel Segal-Halevi
  • Biaoshuai Tao

Abstract

The classic notion of truthfulness requires that no agent has a profitable manipulation -- an untruthful report that, for some combination of reports of the other agents, increases her utility. This strong notion implicitly assumes that the manipulating agent either knows what all other agents are going to report, or is willing to take the risk and act as-if she knows their reports. Without knowledge of the others' reports, most manipulations are risky -- they might decrease the manipulator's utility for some other combinations of reports by the other agents. Accordingly, a recent paper (Bu, Song and Tao, ``On the existence of truthful fair cake cutting mechanisms'', Artificial Intelligence 319 (2023), 103904) suggests a relaxed notion, which we refer to as risk-avoiding truthfulness (RAT), which requires only that no agent can gain from a safe manipulation -- one that is sometimes beneficial and never harmful. Truthfulness and RAT are two extremes: the former considers manipulators with complete knowledge of others, whereas the latter considers manipulators with no knowledge at all. In reality, agents often know about some -- but not all -- of the other agents. This paper introduces the RAT-degree of a mechanism, defined as the smallest number of agents whose reports, if known, may allow another agent to safely manipulate, or $n$ if there is no such number. This notion interpolates between classic truthfulness (degree $n$) and RAT (degree at least $1$): a mechanism with a higher RAT-degree is harder to manipulate safely. To illustrate the generality and applicability of this concept, we analyze the RAT-degree of prominent mechanisms across various social choice settings, including auctions, indivisible goods allocations, cake-cutting, voting, and stable matchings.

Suggested Citation

  • Eden Hartman & Erel Segal-Halevi & Biaoshuai Tao, 2025. "It's Not All Black and White: Degree of Truthfulness for Risk-Avoiding Agents," Papers 2502.18805, arXiv.org.
    • Handle: RePEc:arx:papers:2502.18805
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Eduardo M Azevedo & Eric Budish, 2019. "Strategy-proofness in the Large," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 86(1), pages 81-116.
    2. Troyan, Peter & Morrill, Thayer, 2020. "Obvious manipulations," Journal of Economic Theory, Elsevier, vol. 185(C).
    3. Haan, Marco A. & Heijnen, Pim & Schoonbeek, Lambert & Toolsema, Linda A., 2012. "Sound taxation? On the use of self-declared value," European Economic Review, Elsevier, vol. 56(2), pages 205-215.
    4. Coles, Peter & Shorrer, Ran, 2014. "Optimal truncation in matching markets," Games and Economic Behavior, Elsevier, vol. 87(C), pages 591-615.
    5. Josué Ortega & Erel Segal-Halevi, 2022. "Obvious manipulations in cake-cutting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 59(4), pages 969-988, November.
    6. Lars Ehlers, 2008. "Truncation Strategies in Matching Markets," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 327-335, May.
    7. Arkadii Slinko & Shaun White, 2014. "Is it ever safe to vote strategically?," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 43(2), pages 403-427, August.
    8. repec:dau:papers:123456789/3900 is not listed on IDEAS
    9. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
    10. Andersson, Tommy & Ehlers, Lars & Svensson, Lars-Gunnar, 2014. "Least manipulable Envy-free rules in economies with indivisibilities," Mathematical Social Sciences, Elsevier, vol. 69(C), pages 43-49.
    11. Chen, Yiqiu & Möller, Markus, 2024. "Regret-free truth-telling in school choice with consent," Theoretical Economics, Econometric Society, vol. 19(2), May.
    12. Alvin E. Roth & Uriel G. Rothblum, 1999. "Truncation Strategies in Matching Markets--In Search of Advice for Participants," Econometrica, Econometric Society, vol. 67(1), pages 21-44, January.
    Full references (including those not matched with items on IDEAS)

    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. Paula Jaramillo & Çaǧatay Kayı & Flip Klijn, 2014. "On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(4), pages 793-811, April.
    2. Arribillaga, R. Pablo & Bonifacio, Agustín G., 2024. "Obvious manipulations of tops-only voting rules," Games and Economic Behavior, Elsevier, vol. 143(C), pages 12-24.
    3. José Alcalde & Antonio Romero-Medina, 2017. "Fair student placement," Theory and Decision, Springer, vol. 83(2), pages 293-307, August.
    4. Haris Aziz & Alexander Lam, 2021. "Obvious Manipulability of Voting Rules," Papers 2111.01983, arXiv.org, revised Jun 2022.
    5. Troyan, Peter & Morrill, Thayer, 2020. "Obvious manipulations," Journal of Economic Theory, Elsevier, vol. 185(C).
    6. Castillo, Marco & Dianat, Ahrash, 2016. "Truncation strategies in two-sided matching markets: Theory and experiment," Games and Economic Behavior, Elsevier, vol. 98(C), pages 180-196.
    7. Christian Haas & Margeret Hall, 2019. "Two-Sided Matching for mentor-mentee allocations—Algorithms and manipulation strategies," PLOS ONE, Public Library of Science, vol. 14(3), pages 1-27, March.
    8. Alcalde, José & Romero-Medina, Antonio, 2011. "Fair School Placement," QM&ET Working Papers 11-1, University of Alicante, D. Quantitative Methods and Economic Theory.
    9. Christian Haas, 2021. "Two-Sided Matching with Indifferences: Using Heuristics to Improve Properties of Stable Matchings," Computational Economics, Springer;Society for Computational Economics, vol. 57(4), pages 1115-1148, April.
    10. Chen, Yiqiu & Möller, Markus, 2024. "Regret-free truth-telling in school choice with consent," Theoretical Economics, Econometric Society, vol. 19(2), May.
    11. Ehlers, Lars & Hafalir, Isa E. & Yenmez, M. Bumin & Yildirim, Muhammed A., 2014. "School choice with controlled choice constraints: Hard bounds versus soft bounds," Journal of Economic Theory, Elsevier, vol. 153(C), pages 648-683.
    12. Yuen Leng Chow & Isa E. Hafalir & Abdullah Yavas, 2015. "Auction versus Negotiated Sale: Evidence from Real Estate Sales," Real Estate Economics, American Real Estate and Urban Economics Association, vol. 43(2), pages 432-470, June.
    13. Troyan, Peter, 2024. "(Non-)obvious manipulability of rank-minimizing mechanisms," Journal of Mathematical Economics, Elsevier, vol. 113(C).
    14. Peter Troyan, 2022. "Non-Obvious Manipulability of the Rank-Minimizing Mechanism," Papers 2206.11359, arXiv.org, revised Jun 2024.
    15. Doğan, Battal, 2016. "Responsive affirmative action in school choice," Journal of Economic Theory, Elsevier, vol. 165(C), pages 69-105.
    16. Assaf Romm, 2014. "Implications of capacity reduction and entry in many-to-one stable matching," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 43(4), pages 851-875, December.
    17. Martin Van der Linden, 2019. "Deferred acceptance is minimally manipulable," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(2), pages 609-645, June.
    18. Pathikrit Basu, 2023. "Optimal mechanism design with approximate incentive compatibility and many players," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 8(1), pages 97-106, December.
    19. Pycia, Marek & Ünver, M. Utku, 2015. "Decomposing random mechanisms," Journal of Mathematical Economics, Elsevier, vol. 61(C), pages 21-33.
    20. Mustafa Oǧuz Afacan, 2016. "Characterizations of the cumulative offer process," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 531-542, October.

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