Yokote, Koji (2017): Application of the discrete separation theorem to auctions.

PDF
MPRA_paper_82884.pdf Download (357kB)  Preview 
Abstract
The separation theorem in discrete convex analysis states that two disjoint discrete convex sets can be separated by a hyperplane with a 01 normal vector. We apply this theorem to an auction model and provide a unified approach to existing results. When p is not an equilibrium price vector, i.e., aggregate demand and aggregate supply are disjoint, the separation theorem indicates the existence of excess demand/supply. This observation yields a refined analysis of a characterization of competitive price vectors by Gul and Stacchetti (2000). Adjusting the prices of items in excess demand/supply corresponds to Ausubel's (2006) auction.
Item Type:  MPRA Paper 

Original Title:  Application of the discrete separation theorem to auctions 
English Title:  Application of the discrete separation theorem to auctions 
Language:  English 
Keywords:  Discrete convex analysis, Separation theorem, Hall's theorem, Auction 
Subjects:  C  Mathematical and Quantitative Methods > C7  Game Theory and Bargaining Theory > C78  Bargaining Theory ; Matching Theory D  Microeconomics > D4  Market Structure, Pricing, and Design > D44  Auctions 
Item ID:  82884 
Depositing User:  Koji Yokote 
Date Deposited:  23 Nov 2017 06:27 
Last Modified:  29 Sep 2019 12:20 
References:  Ausubel, L. M. (2006). An efficient dynamic auction for heterogeneous commodities. The American economic review, 96(3), 602629. Demange, G., Gale, D., & Sotomayor, M. (1986). Multiitem auctions. Journal of Political Economy, 94(4), 863872. Fujishige, S., & Yang, Z. (2003). A note on Kelso and Crawford's gross substitutes condition. Mathematics of Operations Research, 28(3), 463469. Gul, F., & Stacchetti, E. (2000). The English auction with differentiated commodities. Journal of Economic theory, 92(1), 6695. Hall, P. (1935). On representatives of subsets. Journal of the London Mathematical Society, 1(1), 2630. Kelso Jr, A. S., & Crawford, V. P. (1982). Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society, 14831504. Kojima, F., Tamura, A., & Yokoo, M. (2017). Designing matching mechanisms under constraints: An approach from discrete convex analysis. MPRA paper No. 78637. Mishra, D., & Talman, D. (2010). Characterization of the Walrasian equilibria of the assignment model. Journal of Mathematical Economics, 46(1), 620. Murota, K. (2003). Discrete convex analysis. SIAM. Murota, K. (2016). Discrete convex analysis: A tool for economics and game theory. Journal of Mechanism and Institution Design, 1(1), 151273. Murota, K., Shioura, A., & Yang, Z. (2016). Time bounds for iterative auctions: a unified approach by discrete convex analysis. discrete optimization, 19, 3662. Roth, A. E., & Sotomayor, M. (1990). Twosided matching: a study in gametheoretic modeling and analysis. Cambridge University Press, Cambridge. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/82884 