The discrete Kuhn-Tucker theorem and its application to auctions

Yokote, Koji (2018): The discrete Kuhn-Tucker theorem and its application to auctions.

Abstract

Using a notion of convexity in discrete convex analysis, we introduce a discrete analogue of the Kuhn-Tucker theorem. We apply it to an auction model and show that existing iterative auctions can be viewed as the process of finding a saddle point of the Lagrange function.

• Item Type: MPRA Paper
• Language: English
• Keywords: Auctions; Discrete convex analysis; Kuhn-Tucker theorem
• 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.

Budish, E., Che, Y. K., Kojima, F., & Milgrom, P. (2013). Designing random allocation mechanisms: Theory and applications. The American Economic Review, 103(2), 585-623.

Cramton, P., Shoham, Y., & Steinber, R. (2006). Combinatorial auctions. MIT press, Cambridge

Fujishige, S., & Tamura, A. (2007). A two-sided discrete-concave market with possibly bounded side payments: An approach by discrete convex analysis. Mathematics of Operations Research, 32(1), 136-155.

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. (1999). Walrasian equilibrium with gross substitutes. Journal of Economic theory, 87(1), 95-124.

Hiriart-Urruty, J.-B., Lemarechal, C. (2001). Fundamentals of convex analysis. Springer.

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. (2015). Recent developments in matching theory and its practical applications.Advances in Economics and Econometrics; 11th world congress of Econometric Society.

Kojima, F., Tamura, A., & Yokoo, M. (2017). Designing matching mechanisms under constraints: An approach from discrete convex analysis. MPRA paper No. 78637.

Murota, K. (2003). Discrete convex analysis. SIAM.

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

Rockafellar, R. T. (1970). Convex analysis. Princeton University Press.

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

Tiel, J. v., 1984. Convex analysis: An introductory text. John Wiley.