×

zbMATH — the first resource for mathematics

Fast convergence in the double oral auction. (English) Zbl 1406.91156
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 60-73 (2015).
Summary: A classical trading experiment consists of a set of unit demand buyers and unit supply sellers with identical items. Each agent’s value or opportunity cost for the item is their private information and preferences are quasi-linear. Trade between agents employs a double oral auction (DOA) in which both buyers and sellers call out bids or offers which an auctioneer recognizes. Transactions resulting from accepted bids and offers are recorded. This continues until there are no more acceptable bids or offers. Remarkably, the experiment consistently terminates in a Walrasian price. The main result of this paper is a mechanism in the spirit of the DOA that converges to a Walrasian equilibrium in a polynomial number of steps, thus providing a theoretical basis for the above-described empirical phenomenon. It is well-known that computation of a Walrasian equilibrium for this market corresponds to solving a maximum weight bipartite matching problem. The uncoordinated but rational responses of agents thus solve in a distributed fashion a maximum weight bipartite matching problem that is encoded by their private valuations. We show, furthermore, that every Walrasian equilibrium is reachable by some sequence of responses. This is in contrast to the well known auction algorithms for this problem which only allow one side to make offers and thus essentially choose an equilibrium that maximizes the surplus for the side making offers. Our results extend to the setting where not every agent pair is allowed to trade with each other.
For the entire collection see [Zbl 1326.68026].

MSC:
91B26 Auctions, bargaining, bidding and selling, and other market models
91B50 General equilibrium theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Assadi, S., Khanna, S., Li, Y., Vohra, R.: Fast convergence in the double oral auction. CoRR abs/1510.00086 (2015) · Zbl 1406.91156
[2] Bertsekas, D.: A distributed algorithm for the assignment problem. Laboratory for Information and Decision Systems, Working Paper, M.I.T., Cambridge (1979)
[3] Bertsekas, D.P.: Linear Network Optimization: Algorithms and Codes. MIT Press, Cambridge (1991) · Zbl 0754.90059
[4] Bertsekas, D.P., Castaon, D.A.: A forward/reverse auction algorithm for asymmetric assignment problems. Comput. Optim. Appl. 1(3), 277–297 (1992). doi: 10.1007/BF00249638 · Zbl 0776.90054 · doi:10.1007/BF00249638
[5] Chamberlin, E.H.: An experimental imperfect market. J. Polit. Econ. 56(2), 95–108 (1948) · doi:10.1086/256654
[6] Crawford, V.P., Knoer, E.M.: Job matching with heterogeneous firms and workers. Econometrica J. Econometric Soc. 49, 437–450 (1981) · Zbl 1202.91141 · doi:10.2307/1913320
[7] Demange, G., Gale, D., Sotomayor, M.: Multi-item auctions. J. Polit. Econ. 94, 863–872 (1986) · doi:10.1086/261411
[8] Friedman, D.P., Rust, J.: The Double Auction Market: Institutions, Theories, and Evidence. Westview Press, Boulder (1993)
[9] Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9–15 (1962) · Zbl 0109.24403 · doi:10.2307/2312726
[10] Kanoria, Y., Bayati, M., Borgs, C., Chayes, J., Montanari, A.: Fast convergence of natural bargaining dynamics in exchange networks. In: SODA (2011). http://dl.acm.org/citation.cfm?id=2133036.2133154 · Zbl 1314.91112
[11] Knuth, D.: Mariages stables et leurs relations avec d&autres problèmes combinatoires: Collection de la Chaire Aisenstadt, Presses de l’Université de Montréal (1976). http://books.google.com/books?id=eAmFAAAAIAAJ
[12] Kuhn, H.W.: The Hungarian method for the assignment problem. In: Jünger, M., Liebling, T.M., Naddef, D., Nemhauser, G.L. (eds.) 50 Years of Integer Programming 1958–2008 - From the Early Years to the State-of-the-Art, pp. 29–47. Springer, Heidelberg (2010) · Zbl 1187.90015 · doi:10.1007/978-3-540-68279-0_2
[13] Nax, H.H., Pradelski, B.S.R., Young, H.P.: Decentralized dynamics to optimal and stable states in the assignment game. In: CDC (2013) · doi:10.1109/CDC.2013.6760238
[14] Pradelski, B.S.: Decentralized dynamics and fast convergence in the assignment game: extended abstract. In: EC. ACM, New York (2015) · doi:10.1145/2764468.2764470
[15] Roth, A.E., Vate, J.H.V.: Random paths to stability in two-sided matching. Econometrica J. Econometric Soc. 58, 1475–1480 (1990) · Zbl 0731.90007 · doi:10.2307/2938326
[16] Shapley, L., Shubik, M.: The assignment game I: the core. Int. J. Game Theory 1(1), 111–130 (1971). doi: 10.1007/BF01753437 · Zbl 0236.90078 · doi:10.1007/BF01753437
[17] Smith, V.L.: An experimental study of competitive market behavior. J. Polit. Econ. 70(2), 111–137 (1962) · doi:10.1086/258609
[18] Smith, V.L.: Papers in Experimental Economics. Cambridge University Press, New York (1991) · doi:10.1017/CBO9780511528354
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.