IDEAS home Printed from https://ideas.repec.org/p/dpr/wpaper/0943.html
   My bibliography  Save this paper

Efficiency and strategy-proofness in object assignment problems with multi demand preferences

Author

Listed:
  • Tomoya Kazumura
  • Shigehiro Serizawa

Abstract

Consider the problem of allocating objects to agents and how much they should pay. Each agent has a preference relation over pairs of a set of objects and a payment. Preferences are not necessarily quasi-linear. Non-quasi-linear preferences describe environments where payments influence agents' abilities to utilize objects. This paper is to investigate the possibility of designing efficient and strategy-proof rules in such environments. A preference relation is single demand if an agent wishes to receive at most one object; it is multi demand if whenever an agent receives one object, an additional object makes him better off. We show that if a domain contains all the single demand preferences and at least one multi demand preference relation, and there are more agents than objects, then no rule satisfies efficiency, strategy-proofness, individual rationality, and no subsidy for losers on the domain.

Suggested Citation

  • Tomoya Kazumura & Shigehiro Serizawa, 2015. "Efficiency and strategy-proofness in object assignment problems with multi demand preferences," ISER Discussion Paper 0943, Institute of Social and Economic Research, Osaka University.
    • Handle: RePEc:dpr:wpaper:0943
    as

    Download full text from publisher

    File URL: https://www.iser.osaka-u.ac.jp/library/dp/2015/DP0943.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Itai Ashlagi & Shigehiro Serizawa, 2012. "Characterizing Vickrey allocation rule by anonymity," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 38(3), pages 531-542, March.
    2. Hiroki Saitoh & Shigehiro Serizawa, 2008. "Vickrey allocation rule with income effect," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 35(2), pages 391-401, May.
    3. Demange, Gabrielle & Gale, David, 1985. "The Strategy Structure of Two-sided Matching Markets," Econometrica, Econometric Society, vol. 53(4), pages 873-888, July.
    4. Masso, Jordi & Neme, Alejandro, 2001. "Maximal Domain of Preferences in the Division Problem," Games and Economic Behavior, Elsevier, vol. 37(2), pages 367-387, November.
    5. Ausubel Lawrence M & Milgrom Paul R, 2002. "Ascending Auctions with Package Bidding," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 1(1), pages 1-44, August.
    6. Berga, Dolors & Serizawa, Shigehiro, 2000. "Maximal Domain for Strategy-Proof Rules with One Public Good," Journal of Economic Theory, Elsevier, vol. 90(1), pages 39-61, January.
    7. Ning Sun & Zaifu Yang, 2006. "Equilibria and Indivisibilities: Gross Substitutes and Complements," Econometrica, Econometric Society, vol. 74(5), pages 1385-1402, September.
    8. Alkan, Ahmet & Gale, David, 1990. "The core of the matching game," Games and Economic Behavior, Elsevier, vol. 2(3), pages 203-212, September.
    9. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    10. Andersson, Tommy & Ehlers, Lars & Svensson, Lars-Gunnar, 2014. "Transferring Ownership of Public Housing to Existing Tenants: A Mechanism Design Approach," Working Papers 2014:23, Lund University, Department of Economics.
    11. Andersson, Tommy & Ehlers, Lars & Svensson, Lars-Gunnar, 2016. "Transferring ownership of public housing to existing tenants: A market design approach," Journal of Economic Theory, Elsevier, vol. 165(C), pages 643-671.
    12. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    13. , & ,, 2015. "Strategy-proofness and efficiency with non-quasi-linear preferences: a characterization of minimum price Walrasian rule," Theoretical Economics, Econometric Society, vol. 10(2), May.
    14. Tsuyoshi Adachi, 2014. "Equity and the Vickrey allocation rule on general preference domains," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(4), pages 813-830, April.
    15. Sprumont, Yves, 2013. "Constrained-optimal strategy-proof assignment: Beyond the Groves mechanisms," Journal of Economic Theory, Elsevier, vol. 148(3), pages 1102-1121.
    16. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    17. Baisa, Brian, 2017. "Auction design without quasilinear preferences," Theoretical Economics, Econometric Society, vol. 12(1), January.
    18. Lawrence M. Ausubel, 2004. "An Efficient Ascending-Bid Auction for Multiple Objects," American Economic Review, American Economic Association, vol. 94(5), pages 1452-1475, December.
    19. Tommy Andersson & Lars‐Gunnar Svensson, 2014. "Non‐Manipulable House Allocation With Rent Control," Econometrica, Econometric Society, vol. 82(2), pages 507-539, March.
    20. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    21. Ning Sun & Zaifu Yang, 2014. "An Efficient and Incentive Compatible Dynamic Auction for Multiple Complements," Journal of Political Economy, University of Chicago Press, vol. 122(2), pages 422-466.
    22. de Vries, Sven & Schummer, James & Vohra, Rakesh V., 2007. "On ascending Vickrey auctions for heterogeneous objects," Journal of Economic Theory, Elsevier, vol. 132(1), pages 95-118, January.
    23. Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
    24. Gul, Faruk & Stacchetti, Ennio, 2000. "The English Auction with Differentiated Commodities," Journal of Economic Theory, Elsevier, vol. 92(1), pages 66-95, May.
    25. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    26. Ning Sun & Zaifu Yang, 2009. "A Double-Track Adjustment Process for Discrete Markets With Substitutes and Complements," Econometrica, Econometric Society, vol. 77(3), pages 933-952, May.
    27. Satterthwaite, Mark Allen, 1975. "Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions," Journal of Economic Theory, Elsevier, vol. 10(2), pages 187-217, April.
    28. Toyotaka Sakai, 2008. "Second price auctions on general preference domains: two characterizations," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 37(2), pages 347-356, November.
    29. Szilvia Pápai, 2003. "Groves sealed bid auctions of heterogeneous objects with fair prices," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 20(3), pages 371-385, June.
    30. Ching, Stephen & Serizawa, Shigehiro, 1998. "A Maximal Domain for the Existence of Strategy-Proof Rules," Journal of Economic Theory, Elsevier, vol. 78(1), pages 157-166, January.
    31. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    32. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
    33. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    34. Ehlers, Lars, 2002. "Coalitional Strategy-Proof House Allocation," Journal of Economic Theory, Elsevier, vol. 105(2), pages 298-317, August.
    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. Yuya Wakabayashi & Ryosuke Sakai & Shigehiro Serizawa, 2022. "A Characterization of the Minimum Price Walrasian Rule with Reserve Prices for an Arbitrary Number of Agents and Objects," ISER Discussion Paper 1161, Institute of Social and Economic Research, Osaka University.
    2. Ryosuke Sakai & Shigehiro Serizawa, 2023. "Strategy-proof mechanism design with non-quasi-linear preferences: ex-post revenue maximization for an arbitrary number of objects," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 60(1), pages 103-120, January.
    3. Bichler, Martin & Merting, Sören, 2018. "Truthfulness in advertising? Approximation mechanisms for knapsack bidders," European Journal of Operational Research, Elsevier, vol. 270(2), pages 775-783.
    4. Tomoya KAZUMURA, 2020. "When can we design efficient and strategy-proof rules in package assignment problems?," Discussion papers e-21-008, Graduate School of Economics , Kyoto University.
    5. Komal Malik & Debasis Mishra, 2018. "Pareto efficient combinatorial auctions: dichotomous preferences without quasilinearity," Discussion Papers 18-06, Indian Statistical Institute, Delhi.
    6. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Mechanism design without quasilinearity," Theoretical Economics, Econometric Society, vol. 15(2), May.
    7. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object auction design: Ex-post revenue maximization with no wastage," Discussion Papers 17-03, Indian Statistical Institute, Delhi.
    8. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object allocation: Ex-post revenue maximization with no wastage," Working Papers e116, Tokyo Center for Economic Research.
    9. Malik, Komal & Mishra, Debasis, 2021. "Pareto efficient combinatorial auctions: Dichotomous preferences without quasilinearity," Journal of Economic Theory, Elsevier, vol. 191(C).
    10. Yu Zhou & Shigehiro Serizawa, 2016. "Strategy-Proofness and Efficiency for Non-quasi-linear Common-Tiered-Object Preferences: Characterization of Minimum Price Rule," ISER Discussion Paper 0971, Institute of Social and Economic Research, Osaka University.
    11. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object auction design: Ex-post revenue maximization with no wastage," ISER Discussion Paper 1001, Institute of Social and Economic Research, Osaka University.
    12. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Strategy-proof multi-object mechanism design: Ex-post revenue maximization with non-quasilinear preferences," Journal of Economic Theory, Elsevier, vol. 188(C).
    13. Haris Aziz & Yoichi Kasajima, 2017. "Impossibilities for probabilistic assignment," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 49(2), pages 255-275, August.
    14. Ryosuke Sakai & Shigehiro Serizawa, 2020. "Strategy-proof mechanism design with non-quasilinear preferences: Ex-post revenue maximization for an arbitrary number of objects," ISER Discussion Paper 1107, Institute of Social and Economic Research, Osaka University.
    15. Zhou, Yu & Serizawa, Shigehiro, 2018. "Strategy-proofness and efficiency for non-quasi-linear and common-tiered-object preferences: Characterization of minimum price rule," Games and Economic Behavior, Elsevier, vol. 109(C), pages 327-363.

    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. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Strategy-proof multi-object mechanism design: Ex-post revenue maximization with non-quasilinear preferences," Journal of Economic Theory, Elsevier, vol. 188(C).
    2. , & ,, 2015. "Strategy-proofness and efficiency with non-quasi-linear preferences: a characterization of minimum price Walrasian rule," Theoretical Economics, Econometric Society, vol. 10(2), May.
    3. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Mechanism design without quasilinearity," Theoretical Economics, Econometric Society, vol. 15(2), May.
    4. Jim Ingebretsen Carlson, 2020. "A speedy auction using approximated bidders’ preferences," Annals of Operations Research, Springer, vol. 288(1), pages 65-93, May.
    5. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object allocation: Ex-post revenue maximization with no wastage," Working Papers e116, Tokyo Center for Economic Research.
    6. Jagadeesan, Ravi & Kominers, Scott Duke & Rheingans-Yoo, Ross, 2018. "Strategy-proofness of worker-optimal matching with continuously transferable utility," Games and Economic Behavior, Elsevier, vol. 108(C), pages 287-294.
    7. Yu Zhou & Shigehiro Serizawa, 2016. "Strategy-Proofness and Efficiency for Non-quasi-linear Common-Tiered-Object Preferences: Characterization of Minimum Price Rule," ISER Discussion Paper 0971, Institute of Social and Economic Research, Osaka University.
    8. Andersson, Tommy & Erlanson, Albin, 2013. "Multi-item Vickrey–English–Dutch auctions," Games and Economic Behavior, Elsevier, vol. 81(C), pages 116-129.
    9. Zhou, Yu & Serizawa, Shigehiro, 2018. "Strategy-proofness and efficiency for non-quasi-linear and common-tiered-object preferences: Characterization of minimum price rule," Games and Economic Behavior, Elsevier, vol. 109(C), pages 327-363.
    10. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    11. Satoru Fujishige & Zaifu Yang, 2020. "A Universal Dynamic Auction for Unimodular Demand Types: An Efficient Auction Design for Various Kinds of Indivisible Commodities," Discussion Papers 20/08, Department of Economics, University of York.
    12. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object auction design: Ex-post revenue maximization with no wastage," ISER Discussion Paper 1001, Institute of Social and Economic Research, Osaka University.
    13. Ingebretsen Carlson, Jim, 2016. "An Auction with Approximated Bidder Preferences - When an Auction has to be Quick," Working Papers 2016:12, Lund University, Department of Economics.
    14. Ozan Candogan & Asuman Ozdaglar & Pablo A. Parrilo, 2015. "Iterative Auction Design for Tree Valuations," Operations Research, INFORMS, vol. 63(4), pages 751-771, August.
    15. Sushil Bikhchandani & Sven de Vries & James Schummer & Rakesh V. Vohra, 2011. "An Ascending Vickrey Auction for Selling Bases of a Matroid," Operations Research, INFORMS, vol. 59(2), pages 400-413, April.
    16. Baranov, Oleg, 2018. "An efficient ascending auction for private valuations," Journal of Economic Theory, Elsevier, vol. 177(C), pages 495-517.
    17. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object auction design: Ex-post revenue maximization with no wastage," Discussion Papers 17-03, Indian Statistical Institute, Delhi.
    18. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    19. Andersson, Tommy & Svensson, Lars-Gunnar, 2018. "Sequential rules for house allocation with price restrictions," Games and Economic Behavior, Elsevier, vol. 107(C), pages 41-59.
    20. Shinji Ohseto, 2021. "Strategy-proof and Pareto efficient allocation of indivisible goods: general impossibility domains," International Journal of Game Theory, Springer;Game Theory Society, vol. 50(2), pages 419-432, June.

    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:dpr:wpaper:0943. 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: Librarian (email available below). General contact details of provider: https://edirc.repec.org/data/isosujp.html .

    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.