IDEAS home Printed from https://ideas.repec.org/p/alo/isipdp/17-03.html
   My bibliography  Save this paper

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

Author

Listed:
  • Tomoya Kazumura

    (University of Tokyo)

  • Debasis Mishra

    (Indian Statistical Institute, Delhi)

  • Shigehiro Serizawa

    (Osaka University)

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 mechanism, 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) mechanism is desirable. We show that at each preference profile, the MWEP mechanism generates more revenue for the seller than any desirable mechanism satisfying no subsidy. Our result works for quasilinear type space, where the MWEP mechanism is the VCG mechanism, and for various nonquasilinear type spaces, some of which incorporate positive income effect of agents. We can relax no subsidy to no bankruptcy in our result for certain type spaces with positive income effect.

Suggested Citation

  • 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.
    • Handle: RePEc:alo:isipdp:17-03
    as

    Download full text from publisher

    File URL: https://www.isid.ac.in/~epu/wp-content/uploads/2017/05/dp17-03.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. Armstrong, Mark, 1996. "Multiproduct Nonlinear Pricing," Econometrica, Econometric Society, vol. 64(1), pages 51-75, January.
    4. Paul Milgrom & Ilya Segal, 2002. "Envelope Theorems for Arbitrary Choice Sets," Econometrica, Econometric Society, vol. 70(2), pages 583-601, March.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Tommy Andersson & Lars‐Gunnar Svensson, 2014. "Non‐Manipulable House Allocation With Rent Control," Econometrica, Econometric Society, vol. 82(2), pages 507-539, March.
    10. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Mechanism design without quasilinearity," Theoretical Economics, Econometric Society, vol. 15(2), May.
    11. , & ,, 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.
    12. 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.
    13. Demange, Gabrielle & Gale, David, 1985. "The Strategy Structure of Two-sided Matching Markets," Econometrica, Econometric Society, vol. 53(4), pages 873-888, July.
    14. 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.
    15. Border, Kim C, 1991. "Implementation of Reduced Form Auctions: A Geometric Approach," Econometrica, Econometric Society, vol. 59(4), pages 1175-1187, July.
    16. 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.
    17. 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.
    18. 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.
    19. Baisa, Brian, 2017. "Auction design without quasilinear preferences," Theoretical Economics, Econometric Society, vol. 12(1), January.
    20. 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.
    21. 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.
    22. 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.
    23. , & , J., 2015. "Maximal revenue with multiple goods: nonmonotonicity and other observations," Theoretical Economics, Econometric Society, vol. 10(3), September.
    24. 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.
    25. Hal R. Varian, 2009. "Online Ad Auctions," American Economic Review, American Economic Association, vol. 99(2), pages 430-434, May.
    26. Krishna, Vijay & Maenner, Eliot, 2001. "Convex Potentials with an Application to Mechanism Design," Econometrica, Econometric Society, vol. 69(4), pages 1113-1119, July.
    27. 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.
    28. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    29. Pai, Mallesh M. & Vohra, Rakesh, 2014. "Optimal auctions with financially constrained buyers," Journal of Economic Theory, Elsevier, vol. 150(C), pages 383-425.
    30. 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.
    31. 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.
    32. 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.
    33. Thanassoulis, John, 2004. "Haggling over substitutes," Journal of Economic Theory, Elsevier, vol. 117(2), pages 217-245, August.
    34. , & ,, 2007. "A non-differentiable approach to revenue equivalence," Theoretical Economics, Econometric Society, vol. 2(4), December.
    35. 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.
    36. 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.
    37. Dobzinski, Shahar & Lavi, Ron & Nisan, Noam, 2012. "Multi-unit auctions with budget limits," Games and Economic Behavior, Elsevier, vol. 74(2), pages 486-503.
    38. 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. Chatterji, Shurojit & Zeng, Huaxia, 2019. "Random mechanism design on multidimensional domains," Journal of Economic Theory, Elsevier, vol. 182(C), pages 25-105.
    2. Yu Zhou & Shigehiro Serizawa, 2019. "Minimum price equilibrium in the assignment market," ISER Discussion Paper 1047, Institute of Social and Economic Research, Osaka University.

    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 allocation: Ex-post revenue maximization with no wastage," Working Papers e116, Tokyo Center for Economic Research.
    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. 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.
    6. 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.
    7. 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.
    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. , & ,, 2013. "Implementation in multidimensional dichotomous domains," Theoretical Economics, Econometric Society, vol. 8(2), May.
    11. 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.
    12. 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.
    13. 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).
    14. Carbajal, Juan Carlos & Ely, Jeffrey C., 2013. "Mechanism design without revenue equivalence," Journal of Economic Theory, Elsevier, vol. 148(1), pages 104-133.
    15. Debasis Mishra & Anup Pramanik & Souvik Roy, 2013. "Implementation in multidimensional domains with ordinal restrictions," Discussion Papers 13-07, Indian Statistical Institute, Delhi.
    16. 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.
    17. Baisa, Brian, 2020. "Efficient multi-unit auctions for normal goods," Theoretical Economics, Econometric Society, vol. 15(1), January.
    18. Yu Zhou & Shigehiro Serizawa, 2019. "Minimum price equilibrium in the assignment market," ISER Discussion Paper 1047, Institute of Social and Economic Research, Osaka University.
    19. 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.
    20. Paul H. Edelman & John A. Weymark, 2021. "Dominant strategy implementability and zero length cycles," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 72(4), pages 1091-1120, November.

    More about this item

    Keywords

    multi-object auction design; strategy-proof mechanism design; ex-post revenue maximization; minimum Walrasian equilibrium price mechanism; non-quasilinear preferences; no wastage; equal treatment of equals;
    All these keywords.

    JEL classification:

    • D82 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Asymmetric and Private Information; Mechanism Design
    • D44 - Microeconomics - - Market Structure, Pricing, and Design - - - Auctions
    • D40 - Microeconomics - - Market Structure, Pricing, and Design - - - General

    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:alo:isipdp:17-03. 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: Debasis Mishra (email available below). General contact details of provider: https://edirc.repec.org/data/isindin.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.