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

Characterizing the Vickrey Combinatorial Auction by Induction

Author

Listed:
  • Chew Soo Hong
  • Shigehiro Serizawa

Abstract

This note studies the allocation of heterogeneous commodities to agents whose private values for combinations of these commodities are monotonic by inclusion. This setting can accommodate the presence of complementarity and substitutability among the heterogeneous commodities. By using induction logic, we provide an elementary proof of Holmstrom's (1919) characterization of the Vickrey combinatorial auction as the unique efficient, strategy-proof, and individually rational allocation rule. Our proof method can also be applied to domains to which his proof cannot be.

Suggested Citation

  • Chew Soo Hong & Shigehiro Serizawa, 2005. "Characterizing the Vickrey Combinatorial Auction by Induction," ISER Discussion Paper 0631, Institute of Social and Economic Research, Osaka University.
    • Handle: RePEc:dpr:wpaper:0631
    as

    Download full text from publisher

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

    Other versions of this item:

    References listed on IDEAS

    as
    1. Jeffrey S. Banks & John O. Ledyard & David P. Porter, 1989. "Allocating Uncertain and Unresponsive Resources: An Experimental Approach," RAND Journal of Economics, The RAND Corporation, vol. 20(1), pages 1-25, Spring.
    2. Milgrom,Paul, 2004. "Putting Auction Theory to Work," Cambridge Books, Cambridge University Press, number 9780521536721, September.
    3. Brewer, Paul J. & Plott, Charles R., 1996. "A binary conflict ascending price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks," International Journal of Industrial Organization, Elsevier, vol. 14(6), pages 857-886, October.
    4. Paul Milgrom, 2000. "Putting Auction Theory to Work: The Simultaneous Ascending Auction," Journal of Political Economy, University of Chicago Press, vol. 108(2), pages 245-272, April.
    5. McCabe, Kevin A & Rassenti, Stephen J & Smith, Vernon L, 1990. "Auction Institutional Design: Theory and Behavior of Simultaneous Multiple-Unit Generalizations of the Dutch and English Auctions," American Economic Review, American Economic Association, vol. 80(5), pages 1276-1283, December.
    6. Soo Chew & Shigehiro Serizawa, 2007. "Characterizing the Vickrey combinatorial auction by induction," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 33(2), pages 393-406, November.
    7. Green, Jerry & Laffont, Jean-Jacques, 1977. "On the revelation of preferences for public goods," Journal of Public Economics, Elsevier, vol. 8(1), pages 79-93, August.
    8. Green, Jerry & Laffont, Jean-Jacques, 1977. "Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public Goods," Econometrica, Econometric Society, vol. 45(2), pages 427-438, March.
    9. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    10. Holmstrom, Bengt, 1979. "Groves' Scheme on Restricted Domains," Econometrica, Econometric Society, vol. 47(5), pages 1137-1144, September.
    11. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    12. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    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. Sprumont, Yves, 2013. "Constrained-optimal strategy-proof assignment: Beyond the Groves mechanisms," Journal of Economic Theory, Elsevier, vol. 148(3), pages 1102-1121.
    2. SHINOZAKI, Hiroki, 2024. "Shutting-out-proofness in object allocation problems with money," Discussion paper series HIAS-E-138, Hitotsubashi Institute for Advanced Study, Hitotsubashi University.
    3. Hultkrantz, Lars & Lunander, Anders, 2013. "Design of a Combinatorial Bidding Market for Green Corridor Freight," Working Papers 2013:6, Örebro University, School of Business.
    4. Itai Sher, 2012. "Optimal shill bidding in the VCG mechanism," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 50(2), pages 341-387, June.
    5. Francisco Robles, 2016. "An implementation of the Vickrey outcome with gross-substitutes," UB School of Economics Working Papers 2016/353, University of Barcelona School of Economics.
    6. , & ,, 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.
    7. Tsuyoshi Adachi & Takumi Kongo, 2013. "First-price auctions on general preference domains: axiomatic characterizations," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 1(1), pages 93-103, May.
    8. Christopher P. Chambers & Michael Richter, 2023. "Ordinal allocation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 60(1), pages 5-14, January.
    9. SHINOZAKI, Hiroki, 2023. "Non-obvious manipulability and efficiency in package assignment problems with money for agents with income effects and hard budget constraints," Discussion paper series HIAS-E-136, Hitotsubashi Institute for Advanced Study, Hitotsubashi University.
    10. Soo Chew & Shigehiro Serizawa, 2007. "Characterizing the Vickrey combinatorial auction by induction," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 33(2), pages 393-406, November.
    11. 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.
    12. Alva, Samson & Manjunath, Vikram, 2019. "Strategy-proof Pareto-improvement," Journal of Economic Theory, Elsevier, vol. 181(C), pages 121-142.
    13. Kerber, Manfred & Lange, Christoph & Rowat, Colin, 2016. "An introduction to mechanized reasoning," Journal of Mathematical Economics, Elsevier, vol. 66(C), pages 26-39.
    14. Toyotaka Sakai, 2013. "Axiomatizations of second price auctions with a reserve price," International Journal of Economic Theory, The International Society for Economic Theory, vol. 9(3), pages 255-265, September.
    15. Shigehiro Serizawa, 2006. "Strategy-Proof and Anonymous Allocation Rules of Indivisible Goods: A New Characterization of Vickrey Allocation Rule," ISER Discussion Paper 0648, Institute of Social and Economic Research, Osaka University.
    16. 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.
    17. Yu Zhou & Youngsub Chun & Shigehiro Serizawa, 2022. "A characterization of the Vickrey rule in slot allocation problems," International Journal of Economic Theory, The International Society for Economic Theory, vol. 18(1), pages 38-49, March.
    18. Sano, Ryuji, 2013. "Vickrey-reserve auctions and an equilibrium equivalence," Mathematical Social Sciences, Elsevier, vol. 65(2), pages 112-117.
    19. Takumi Kongo, 2020. "Similarities in axiomatizations: equal surplus division value and first-price auctions," Review of Economic Design, Springer;Society for Economic Design, vol. 24(3), pages 199-213, December.
    20. Nanyang Bu, 2016. "Joint misrepresentation with bribes," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 61(1), pages 115-125, January.
    21. 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.
    22. Miki Kato & Shinji Ohseto & Shohei Tamura, 2015. "Strategy-proofness versus symmetry in economies with an indivisible good and money," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(1), pages 195-207, February.
    23. Tomoya Tajika & Tomoya Kazumura, 2019. "Non-manipulability of uniform price auctions with a large number of objects," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(2), pages 543-569, June.
    24. Marina Núñez & Francisco Robles, 2023. "Overbidding and underbidding in package allocation problems," UB School of Economics Working Papers 2023/440, University of Barcelona School of Economics.

    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. Paul Milgrom, 2006. "Package Auctions and Package Exchanges: the 2004 Fisher-Schultz Lecture," Levine's Bibliography 321307000000000131, UCLA Department of Economics.
    2. Lawrence M. Ausubel & Paul Milgrom, 2004. "Ascending Proxy Auctions," Discussion Papers 03-035, Stanford Institute for Economic Policy Research.
    3. 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.
    4. Sano, Ryuji, 2013. "Vickrey-reserve auctions and an equilibrium equivalence," Mathematical Social Sciences, Elsevier, vol. 65(2), pages 112-117.
    5. Eric Maskin, 2004. "The Unity of Auction Theory: Paul Milgrom's Masterclass," Economics Working Papers 0044, Institute for Advanced Study, School of Social Science.
    6. 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.
    7. Marek Pycia & Peter Troyan, 2023. "A Theory of Simplicity in Games and Mechanism Design," Econometrica, Econometric Society, vol. 91(4), pages 1495-1526, July.
    8. Schnizler, Bjorn & Neumann, Dirk & Veit, Daniel & Weinhardt, Christof, 2008. "Trading grid services - a multi-attribute combinatorial approach," European Journal of Operational Research, Elsevier, vol. 187(3), pages 943-961, June.
    9. Ledyard, John O., "undated". "Public Goods: A Survey of Experimental Research," Working Papers 861, California Institute of Technology, Division of the Humanities and Social Sciences.
    10. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    11. Kazumori, Eiichiro & Belch, Yaakov, 2019. "t-Tree: The Tokyo toolbox for large-scale combinatorial auction experiments," Journal of Behavioral and Experimental Finance, Elsevier, vol. 24(C).
    12. Lawrence M. Ausubel & Paul Milgrom, 2004. "The Lovely but Lonely Vickrey Auction," Discussion Papers 03-036, Stanford Institute for Economic Policy Research.
    13. Alva, Samson & Manjunath, Vikram, 2019. "Strategy-proof Pareto-improvement," Journal of Economic Theory, Elsevier, vol. 181(C), pages 121-142.
    14. Yi, Jianxin & Li, Yong, 2016. "A general impossibility theorem and its application to individual rights," Mathematical Social Sciences, Elsevier, vol. 81(C), pages 79-86.
    15. Christopher P. Chambers & Michael Richter, 2023. "Ordinal allocation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 60(1), pages 5-14, January.
    16. 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.
    17. 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.
    18. James Schummer, 1999. "Almost-dominant Strategy Implementation," Discussion Papers 1278, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    19. Sprumont, Yves, 2013. "Constrained-optimal strategy-proof assignment: Beyond the Groves mechanisms," Journal of Economic Theory, Elsevier, vol. 148(3), pages 1102-1121.
    20. Takashi Kunimoto & Cuiling Zhang, 2021. "On incentive compatible, individually rational public good provision mechanisms," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(2), pages 431-468, August.

    More about this item

    JEL classification:

    • D44 - Microeconomics - - Market Structure, Pricing, and Design - - - Auctions
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations
    • D61 - Microeconomics - - Welfare Economics - - - Allocative Efficiency; Cost-Benefit Analysis
    • D82 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Asymmetric and Private Information; Mechanism Design

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