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

Strategy-proof multi-object allocation: Ex-post revenue maximization with no wastage

Author

Listed:
  • Tomoya Kazumura
  • Debasis Mishra
  • Shigehiro Serizawa

Abstract

A seller is selling multiple objects to a set of agents. Each agent can buy at most one object and his utility over consumption bundles (i.e., (object,transfer) pairs) need not be quasilinear. The seller considers the following desiderata for her (allocation) rule, which she terms desirable: (1) strategy-proofness, (2) ex-post individual rationality, (3) equal treatment of equals, (4) no wastage (every object is allocated to some agent). The minimum Walrasian equilibrium price (MWEP) rule is desirable. We show that at each preference profile, the MWEP rule generates more revenue for the seller than any desirable rule satisfying no subsidy. Our result works for quasilinear domain, where the MWEP rule is the VCG rule, and for various non-quasilinear domains, some of which incorporate positive income effect of agents. We can relax no subsidy to no bankruptcy in our result for certain domains with positive income effect.

Suggested Citation

  • 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.
    • Handle: RePEc:tcr:wpaper:e116
    as

    Download full text from publisher

    File URL: https://www.tcer.or.jp/wp/pdf/e116.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Lavi, Ron & May, Marina, 2012. "A note on the incompatibility of strategy-proofness and Pareto-optimality in quasi-linear settings with public budgets," Economics Letters, Elsevier, vol. 115(1), pages 100-103.
    2. Bulow, Jeremy & Klemperer, Paul, 1996. "Auctions versus Negotiations," American Economic Review, American Economic Association, vol. 86(1), pages 180-194, March.
    3. 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.
    4. Benjamin Edelman & Michael Ostrovsky & Michael Schwarz, 2007. "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords," American Economic Review, American Economic Association, vol. 97(1), pages 242-259, March.
    5. 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.
    6. Demange, Gabrielle & Gale, David, 1985. "The Strategy Structure of Two-sided Matching Markets," Econometrica, Econometric Society, vol. 53(4), pages 873-888, July.
    7. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Mechanism design without quasilinearity," Theoretical Economics, Econometric Society, vol. 15(2), May.
    8. Border, Kim C, 1991. "Implementation of Reduced Form Auctions: A Geometric Approach," Econometrica, Econometric Society, vol. 59(4), pages 1175-1187, July.
    9. Tomoya Kazumura & Shigehiro Serizawa, 2016. "Efficiency and strategy-proofness in object assignment problems with multi-demand preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 633-663, October.
    10. Sushil Bikhchandani & Shurojit Chatterji & Ron Lavi & Ahuva Mu'alem & Noam Nisan & Arunava Sen, 2006. "Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation," Econometrica, Econometric Society, vol. 74(4), pages 1109-1132, July.
    11. Manelli, Alejandro M. & Vincent, Daniel R., 2006. "Bundling as an optimal selling mechanism for a multiple-good monopolist," Journal of Economic Theory, Elsevier, vol. 127(1), pages 1-35, March.
    12. Ken Binmore & Paul Klemperer, 2002. "The Biggest Auction Ever: the Sale of the British 3G Telecom Licences," Economic Journal, Royal Economic Society, vol. 112(478), pages 74-96, March.
    13. 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.
    14. , & , J., 2015. "Maximal revenue with multiple goods: nonmonotonicity and other observations," Theoretical Economics, Econometric Society, vol. 10(3), September.
    15. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    16. Birgit Heydenreich & Rudolf Müller & Marc Uetz & Rakesh V. Vohra, 2009. "Characterization of Revenue Equivalence," Econometrica, Econometric Society, vol. 77(1), pages 307-316, January.
    17. Yeon‐Koo Che & Jinwoo Kim & Konrad Mierendorff, 2013. "Generalized Reduced‐Form Auctions: A Network‐Flow Approach," Econometrica, Econometric Society, vol. 81(6), pages 2487-2520, November.
    18. 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.
    19. Mookherjee, Dilip & Reichelstein, Stefan, 1992. "Dominant strategy implementation of Bayesian incentive compatible allocation rules," Journal of Economic Theory, Elsevier, vol. 56(2), pages 378-399, April.
    20. Thanassoulis, John, 2004. "Haggling over substitutes," Journal of Economic Theory, Elsevier, vol. 117(2), pages 217-245, August.
    21. Ashlagi Itai & Braverman Mark & Hassidim Avinatan & Lavi Ron & Tennenholtz Moshe, 2010. "Position Auctions with Budgets: Existence and Uniqueness," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 10(1), pages 1-32, May.
    22. Jehiel, Philippe & Moldovanu, Benny & Stacchetti, Ennio, 1999. "Multidimensional Mechanism Design for Auctions with Externalities," Journal of Economic Theory, Elsevier, vol. 85(2), pages 258-293, April.
    23. 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.
    24. , & ,, 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.
    25. Sergiu Hart & Noam Nisan, 2013. "The Menu-Size Complexity of Auctions," Discussion Paper Series dp637, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    26. Armstrong, Mark, 1996. "Multiproduct Nonlinear Pricing," Econometrica, Econometric Society, vol. 64(1), pages 51-75, January.
    27. Paul Milgrom & Ilya Segal, 2002. "Envelope Theorems for Arbitrary Choice Sets," Econometrica, Econometric Society, vol. 70(2), pages 583-601, March.
    28. 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.
    29. Tommy Andersson & Lars‐Gunnar Svensson, 2014. "Non‐Manipulable House Allocation With Rent Control," Econometrica, Econometric Society, vol. 82(2), pages 507-539, March.
    30. Orley Ashenfelter & Kathryn Graddy, 2003. "Auctions and the Price of Art," Journal of Economic Literature, American Economic Association, vol. 41(3), pages 763-787, September.
    31. Baisa, Brian, 2017. "Auction design without quasilinear preferences," Theoretical Economics, Econometric Society, vol. 12(1), January.
    32. 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.
    33. Alex Gershkov & Jacob K. Goeree & Alexey Kushnir & Benny Moldovanu & Xianwen Shi, 2013. "On the Equivalence of Bayesian and Dominant Strategy Implementation," Econometrica, Econometric Society, vol. 81(1), pages 197-220, January.
    34. Hal R. Varian, 2009. "Online Ad Auctions," American Economic Review, American Economic Association, vol. 99(2), pages 430-434, May.
    35. Krishna, Vijay & Maenner, Eliot, 2001. "Convex Potentials with an Application to Mechanism Design," Econometrica, Econometric Society, vol. 69(4), pages 1113-1119, July.
    36. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    37. Pai, Mallesh M. & Vohra, Rakesh, 2014. "Optimal auctions with financially constrained buyers," Journal of Economic Theory, Elsevier, vol. 150(C), pages 383-425.
    38. Leonard, Herman B, 1983. "Elicitation of Honest Preferences for the Assignment of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 91(3), pages 461-479, June.
    39. , & ,, 2007. "A non-differentiable approach to revenue equivalence," Theoretical Economics, Econometric Society, vol. 2(4), December.
    40. Dobzinski, Shahar & Lavi, Ron & Nisan, Noam, 2012. "Multi-unit auctions with budget limits," Games and Economic Behavior, Elsevier, vol. 74(2), pages 486-503.
    41. Rochet, Jean-Charles, 1987. "A necessary and sufficient condition for rationalizability in a quasi-linear context," Journal of Mathematical Economics, Elsevier, vol. 16(2), pages 191-200, April.
    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. Yu Zhou & Shigehiro Serizawa, 2019. "Minimum price equilibrium in the assignment market," ISER Discussion Paper 1047, Institute of Social and Economic Research, Osaka University.
    2. Chatterji, Shurojit & Zeng, Huaxia, 2019. "Random mechanism design on multidimensional domains," Journal of Economic Theory, Elsevier, vol. 182(C), pages 25-105.

    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. 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.
    2. 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.
    3. 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).
    4. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Mechanism design without quasilinearity," Theoretical Economics, Econometric Society, vol. 15(2), May.
    5. Tomoya Kazumura & Shigehiro Serizawa, 2016. "Efficiency and strategy-proofness in object assignment problems with multi-demand preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 633-663, October.
    6. 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.
    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. Mishra, Debasis & Pramanik, Anup & Roy, Souvik, 2014. "Multidimensional mechanism design in single peaked type spaces," Journal of Economic Theory, Elsevier, vol. 153(C), pages 103-116.
    9. Komal Malik & Debasis Mishra, 2018. "Pareto efficient combinatorial auctions: dichotomous preferences without quasilinearity," Discussion Papers 18-06, Indian Statistical Institute, Delhi.
    10. 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.
    11. , & ,, 2013. "Implementation in multidimensional dichotomous domains," Theoretical Economics, Econometric Society, vol. 8(2), May.
    12. Carbajal, Juan Carlos & Mu'alem, Ahuva, 2020. "Selling mechanisms for a financially constrained buyer," Games and Economic Behavior, Elsevier, vol. 124(C), pages 386-405.
    13. 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.
    14. Baisa, Brian, 2020. "Efficient multi-unit auctions for normal goods," Theoretical Economics, Econometric Society, vol. 15(1), January.
    15. Yu Zhou & Shigehiro Serizawa, 2019. "Minimum price equilibrium in the assignment market," ISER Discussion Paper 1047, Institute of Social and Economic Research, Osaka University.
    16. Berger, A. & Müller, R.J. & Naeemi, S.H., 2010. "Path-monotonicity and incentive compatibility," Research Memorandum 035, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    17. Carbajal, Juan Carlos & Ely, Jeffrey C., 2013. "Mechanism design without revenue equivalence," Journal of Economic Theory, Elsevier, vol. 148(1), pages 104-133.
    18. Debasis Mishra & Anup Pramanik & Souvik Roy, 2013. "Implementation in multidimensional domains with ordinal restrictions," Discussion Papers 13-07, Indian Statistical Institute, Delhi.
    19. Rochet, Jean-Charles, 2024. "Multidimensional Screening After 37 years," TSE Working Papers 24-1536, Toulouse School of Economics (TSE).
    20. M. Yenmez, 2015. "Incentive compatible market design with applications," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(3), pages 543-569, 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:tcr:wpaper:e116. 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: the person in charge (email available below). General contact details of provider: https://edirc.repec.org/data/tctokjp.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.