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

On Sybil Proofness in Competitive Combinatorial Exchanges

Author

Listed:
  • Abhimanyu Nag

Abstract

We study Sybil manipulation in BRACE, a competitive equilibrium mechanism for combinatorial exchanges, by treating identity creation as a finite perturbation of the empirical distribution of reported types. Under standard regularity assumptions on the excess demand map and smoothness of principal utilities, we obtain explicit linear bounds on price and welfare deviations induced by bounded Sybil invasion. Using these bounds, we prove a sharp contrast: strategyproofness in the large holds if and only if each principal's share of identities vanishes, whereas any principal with a persistent positive share can construct deviations yielding strictly positive limiting gains. We further show that the feasibility of BRACE fails in the event of an unbounded population of Sybils and provide a precise cost threshold that ensures disincentivization of such attacks in large markets.

Suggested Citation

  • Abhimanyu Nag, 2025. "On Sybil Proofness in Competitive Combinatorial Exchanges," Papers 2512.10203, arXiv.org.
    • Handle: RePEc:arx:papers:2512.10203
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2512.10203
    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. Eric Budish, 2011. "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes," Journal of Political Economy, University of Chicago Press, vol. 119(6), pages 1061-1103.
    3. Hylland, Aanund & Zeckhauser, Richard, 1979. "The Efficient Allocation of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 87(2), pages 293-314, April.
    4. Haim Levy, 1992. "Stochastic Dominance and Expected Utility: Survey and Analysis," Management Science, INFORMS, vol. 38(4), pages 555-593, April.
    5. Jaya Klara Brekke, 2021. "Hacker-engineers and Their Economies: The Political Economy of Decentralised Networks and ‘Cryptoeconomics’," New Political Economy, Taylor & Francis Journals, vol. 26(4), pages 646-659, July.
    6. Federico Echenique & Antonio Miralles & Jun Zhang, 2021. "Constrained Pseudo-Market Equilibrium," American Economic Review, American Economic Association, vol. 111(11), pages 3699-3732, November.
    7. Fahad Saleh & Wei Jiang, 2021. "Blockchain without Waste: Proof-of-Stake [Proof of Work vs Proof of Stake]," The Review of Financial Studies, Society for Financial Studies, vol. 34(3), pages 1156-1190.
    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. Th`anh Nguyen & Alexander Teytelboym & Shai Vardi, 2025. "Efficiency, Envy, and Incentives in Combinatorial Assignment," Papers 2509.13198, arXiv.org, revised Oct 2025.
    2. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    3. Shende, Priyanka & Purohit, Manish, 2023. "Strategy-proof and envy-free mechanisms for house allocation," Journal of Economic Theory, Elsevier, vol. 213(C).
    4. Hashimoto, Tadashi, 2018. "The generalized random priority mechanism with budgets," Journal of Economic Theory, Elsevier, vol. 177(C), pages 708-733.
    5. Balbuzanov, Ivan, 2022. "Constrained random matching," Journal of Economic Theory, Elsevier, vol. 203(C).
    6. Xiang Han & Onur Kesten & M. Utku Ünver, 2021. "Blood Allocation with Replacement Donors: A Theory of Multi-unit Exchange with Compatibility-based Preferences," Boston College Working Papers in Economics 1038, Boston College Department of Economics.
    7. Daniel Kornbluth & Alexey Kushnir, 2024. "Undergraduate Course Allocation through Competitive Markets," Papers 2412.05691, arXiv.org, revised Dec 2025.
    8. Th`anh Nguyen & Alexander Teytelboym & Shai Vardi, 2023. "Dynamic Combinatorial Assignment," Papers 2303.13967, arXiv.org.
    9. Aygün, Orhan & Turhan, Bertan, 2021. "How to De-reserve Reserves," ISU General Staff Papers 202103100800001123, Iowa State University, Department of Economics.
    10. Julien Combe & Vladyslav Nora & Olivier Tercieux, 2021. "Dynamic assignment without money: Optimality of spot mechanisms," Working Papers 2021-11, Center for Research in Economics and Statistics.
    11. Eun Jeong Heo & Vikram Manjunath, 2017. "Implementation in stochastic dominance Nash equilibria," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(1), pages 5-30, January.
    12. Kojima, Fuhito, 2013. "Efficient resource allocation under multi-unit demand," Games and Economic Behavior, Elsevier, vol. 82(C), pages 1-14.
    13. Condorelli, Daniele, 2013. "Market and non-market mechanisms for the optimal allocation of scarce resources," Games and Economic Behavior, Elsevier, vol. 82(C), pages 582-591.
    14. Eric Budish & Judd B. Kessler, 2022. "Can Market Participants Report Their Preferences Accurately (Enough)?," Management Science, INFORMS, vol. 68(2), pages 1107-1130, February.
    15. Yusuke Narita, 2018. "Experiment-as-Market: Incorporating Welfare into Randomized Controlled Trials," Cowles Foundation Discussion Papers 2127r, Cowles Foundation for Research in Economics, Yale University, revised May 2019.
    16. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    17. Sandomirskiy, Fedor & Ushchev, Philip, 2024. "The geometry of consumer preference aggregation," CEPR Discussion Papers 19100, C.E.P.R. Discussion Papers.
    18. Canidio, Andrea, 2025. "Auctions with tokens: Monetary policy as a mechanism design choice," Journal of Economic Theory, Elsevier, vol. 230(C).
    19. Piotr Dworczak & Scott Duke Kominers & Mohammad Akbarpour, 2021. "Redistribution Through Markets," Econometrica, Econometric Society, vol. 89(4), pages 1665-1698, July.
    20. Cole, Richard & Tao, Yixin, 2021. "On the existence of Pareto Efficient and envy-free allocations," Journal of Economic Theory, Elsevier, vol. 193(C).

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