Application of the discrete separation theorem to auctions

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

Abstract

The separation theorem in discrete convex analysis states that two disjoint discrete convex sets can be separated by a hyperplane with a 0-1 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
• 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

References

Ausubel, L. M. (2006). An efficient dynamic auction for heterogeneous commodities. The American economic review, 96(3), 602-629.

Demange, G., Gale, D., & Sotomayor, M. (1986). Multi-item auctions. Journal of Political Economy, 94(4), 863-872.

Fujishige, S., & Yang, Z. (2003). A note on Kelso and Crawford's gross substitutes condition. Mathematics of Operations Research, 28(3), 463-469.

Gul, F., & Stacchetti, E. (2000). The English auction with differentiated commodities. Journal of Economic theory, 92(1), 66-95.

Hall, P. (1935). On representatives of subsets. Journal of the London Mathematical Society, 1(1), 26-30.

Kelso Jr, A. S., & Crawford, V. P. (1982). Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society, 1483-1504.

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), 6-20.

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), 151-273.

Murota, K., Shioura, A., & Yang, Z. (2016). Time bounds for iterative auctions: a unified approach by discrete convex analysis. discrete optimization, 19, 36-62.

Roth, A. E., & Sotomayor, M. (1990). Two-sided matching: a study in game-theoretic modeling and analysis. Cambridge University Press, Cambridge.