IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2511.04142.html

A characterization of strategy-proof probabilistic assignment rules

Author

Listed:
  • Sai Praneeth Donthu
  • Souvik Roy
  • Soumyarup Sadhukhan
  • Gogulapati Sreedurga

Abstract

We study the classical probabilistic assignment problem, where finitely many indivisible objects are to be probabilistically or proportionally assigned among an equal number of agents. Each agent has an initial deterministic endowment and a strict preference over the objects. While the deterministic version of this problem is well understood, most notably through the characterization of the Top Trading Cycles (TTC) rule by Ma (1994), much less is known in the probabilistic setting. Motivated by practical considerations, we introduce a weakened incentive requirement, namely SD-top-strategy-proofness, which precludes only those manipulations that increase the probability of an agent's top-ranked object. Our first main result shows that, on any free pair at the top (FPT) domain (Sen, 2011), the TTC rule is the unique probabilistic assignment rule satisfying SD-Pareto efficiency, SD-individual rationality, and SD-top-strategy-proofness. We further show that this characterization remains valid when Pareto efficiency is replaced by the weaker notion of SD-pair efficiency, provided the domain satisfies the slightly stronger free triple at the top (FTT) condition (Sen, 2011). Finally, we extend these results to the ex post notions of efficiency and individual rationality. Together, our findings generalize the classical deterministic results of Ma (1994) and Ekici (2024) along three dimensions: extending them from deterministic to probabilistic settings, from full strategy-proofness to top-strategy-proofness, and from the unrestricted domain to the more general FPT and FTT domains.

Suggested Citation

  • Sai Praneeth Donthu & Souvik Roy & Soumyarup Sadhukhan & Gogulapati Sreedurga, 2025. "A characterization of strategy-proof probabilistic assignment rules," Papers 2511.04142, arXiv.org.
    • Handle: RePEc:arx:papers:2511.04142
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    2. Ekici, Özgün, 2024. "Pair-efficient reallocation of indivisible objects," Theoretical Economics, Econometric Society, vol. 19(2), May.
    3. Cho, Wonki Jo & Doğan, Battal, 2016. "Equivalence of efficiency notions for ordinal assignment problems," Economics Letters, Elsevier, vol. 146(C), pages 8-12.
    4. Ma, Jinpeng, 1994. "Strategy-Proofness and the Strict Core in a Market with Indivisibilities," International Journal of Game Theory, Springer;Game Theory Society, vol. 23(1), pages 75-83.
    5. Gibbard, Allan, 1977. "Manipulation of Schemes That Mix Voting with Chance," Econometrica, Econometric Society, vol. 45(3), pages 665-681, April.
    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. Sreedurga Gogulapati & Yadati Narahari & Souvik Roy & Soumyarup Sadhukhan, 2025. "On Probabilistic Assignment Rules," Papers 2507.09550, arXiv.org.
    2. Feng, Di, 2025. "Efficiency in multiple-type housing markets," Journal of Mathematical Economics, Elsevier, vol. 119(C).
    3. Tang, Qianfeng & Zhu, Zhan, 2025. "Ekici’s reclaim-proof allocations revisited," Journal of Mathematical Economics, Elsevier, vol. 121(C).
    4. Bettina Klaus, 2024. "Characterizing the top trading cycles rule for housing markets with lexicographic preferences," Papers 2410.16745, arXiv.org.
    5. Sumit Goel & Yuki Tamura, 2025. "TTC Domains," Papers 2501.15422, arXiv.org, revised Aug 2025.
    6. Ekici, Özgün & Sethuraman, Jay, 2024. "Characterizing the TTC rule via pair-efficiency: A short proof," Economics Letters, Elsevier, vol. 234(C).
    7. Morrill, Thayer & Roth, Alvin E., 2024. "Top trading cycles," Journal of Mathematical Economics, Elsevier, vol. 112(C).
    8. Xinquan Hu & Jun Zhang, 2025. "Local unanimity in Shapley-Scarf housing markets," Papers 2511.22027, arXiv.org.
    9. Klaus, Bettina & Klijn, Flip & Sethuraman, Jay, 2025. "A characterization of the top-trading-cycles mechanism for housing markets via respecting-improvement," Economics Letters, Elsevier, vol. 247(C).
    10. Coreno, Jacob & Feng, Di, 2025. "Characterizing TTC via endowments-swapping-proofness and truncation-proofness," Economics Letters, Elsevier, vol. 247(C).
    11. Chen, Yajing & Jiao, Zhenhua & Zhang, Chenfeng & Zhang, Luosai, 2025. "Some new characterizations of top trading cycles," Journal of Mathematical Economics, Elsevier, vol. 121(C).
    12. Bettina Klaus, 2025. "Characterizing the top trading cycles rule for housing markets with lexicographic preferences when externalities are limited," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 65(1), pages 1-26, August.
    13. Mandal, Pinaki, 2025. "Efficient reallocation of indivisible resources: Pair-efficiency versus Pareto-efficiency," Journal of Mathematical Economics, Elsevier, vol. 119(C).
    14. Pinaki Mandal, 2025. "Efficient reallocation of indivisible resources: Pair-efficiency versus Pareto-efficiency," Papers 2506.15169, arXiv.org.
    15. Harless, Patrick & Phan, William, 2022. "Efficient mixtures of priority rules for assigning objects," Games and Economic Behavior, Elsevier, vol. 132(C), pages 73-89.
    16. Abdulkadiroglu, Atila & Sonmez, Tayfun, 1999. "House Allocation with Existing Tenants," Journal of Economic Theory, Elsevier, vol. 88(2), pages 233-260, October.
    17. Tom Demeulemeester & Bettina Klaus, 2025. "Pairwise efficiency and monotonicity imply Pareto efficiency in (probabilistic) object allocation," Papers 2508.05340, arXiv.org.
    18. Hu, Xinquan & Zhang, Jun, 2024. "Characterization of Top Trading Cycles with single-dipped preferences," Economics Letters, Elsevier, vol. 241(C).
    19. Tommy Andersson & Lars Ehlers & Lars-Gunnar Svensson & Ryan Tierney, 2022. "Gale’s Fixed Tax for Exchanging Houses," Mathematics of Operations Research, INFORMS, vol. 47(4), pages 3110-3128, November.
    20. Ata Atay & Ana Mauleon & Vincent Vannetelbosch, 2025. "Limited Farsightedness in Priority‐Based Matching," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 27(4), August.

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