{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T15:37:57Z","timestamp":1764603477820,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,11,30]],"date-time":"2017-11-30T00:00:00Z","timestamp":1512000000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1116961, CCF-1552909, CCF-1617851, IIS-1447470"],"award-info":[{"award-number":["CCF-1116961, CCF-1552909, CCF-1617851, IIS-1447470"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2017,11,30]]},"abstract":"<jats:p>A classical trading experiment consists of a set of unit demand buyers and unit supply sellers with identical items. Each agent\u2019s value or opportunity cost for the item is his private information, and preferences are quasilinear. Trade between agents employs a double oral auction (DOA) in which both buyers and sellers call out bids or offers that 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 article 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 empirical phenomenon described previously. 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 mildly 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 that 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.<\/jats:p>","DOI":"10.1145\/3084358","type":"journal-article","created":{"date-parts":[[2017,12,22]],"date-time":"2017-12-22T17:17:37Z","timestamp":1513963057000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast Convergence in the Double Oral Auction"],"prefix":"10.1145","volume":"5","author":[{"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"University of Pennsylvania"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}]},{"given":"Yang","family":"Li","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}]},{"given":"Rakesh","family":"Vohra","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}]}],"member":"320","published-online":{"date-parts":[[2017,12,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2014.02.007"},{"key":"e_1_2_1_2_1","unstructured":"Dimitri P. Bertsekas. 1979. A Distributed Algorithm for the Assignment Problem. Working Paper. Laboratory for Information and Decision Systems. Massachusetts Institute of Technology Cambridge MA.  Dimitri P. Bertsekas. 1979. A Distributed Algorithm for the Assignment Problem. Working Paper. Laboratory for Information and Decision Systems. Massachusetts Institute of Technology Cambridge MA."},{"key":"e_1_2_1_3_1","unstructured":"Dimitri P. Bertsekas. 1991. Linear Network Optimization: Algorithms and Codes. MIT Press Cambridge MA.   Dimitri P. Bertsekas. 1991. Linear Network Optimization: Algorithms and Codes. MIT Press Cambridge MA."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00249638"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1086\/256654"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913320"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1086\/261411"},{"key":"e_1_2_1_8_1","unstructured":"Daniel P. Friedman and John Rust. 1993. The Double Auction Market: Institutions Theories and Evidence. Vol. 14. Westview Press Boulder CO.  Daniel P. Friedman and John Rust. 1993. The Double Auction Market: Institutions Theories and Evidence. Vol. 14. Westview Press Boulder CO."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133154"},{"key":"e_1_2_1_11_1","unstructured":"Donald E. Knuth. 1976. Mariages Stables et Leurs Relations Avec d8autres Probl\u00e8mes combinatoires. Presses de l\u2019Universit\u00e9 de Montr\u00e9al. http:\/\/books.google.com\/books?id&equals;eAmFAAAAIAAJ.  Donald E. Knuth. 1976. Mariages Stables et Leurs Relations Avec d8autres Probl\u00e8mes combinatoires. Presses de l\u2019Universit\u00e9 de Montr\u00e9al. http:\/\/books.google.com\/books?id&equals;eAmFAAAAIAAJ."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Harold W. Kuhn. 2010. The Hungarian method for the assignment problem. In 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer 29--47.  Harold W. Kuhn. 2010. The Hungarian method for the assignment problem. In 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer 29--47.","DOI":"10.1007\/978-3-540-68279-0_2"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 2010. Randomized Algorithms. Chapman 8 Hall\/CRC.  Rajeev Motwani and Prabhakar Raghavan. 2010. Randomized Algorithms. Chapman 8 Hall\/CRC.","DOI":"10.1201\/9781584888239-c12"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-014-0459-1"},{"volume-title":"Proceedings of the 2013 52nd Annual Conference on Decision and Control (CDC\u201913)","author":"Nax Heinrich H.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764470"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2307\/2938326"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01753437"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1086\/258609"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Vernon L. Smith. 1991. Papers in Experimental Economics. Cambridge University Press.  Vernon L. Smith. 1991. Papers in Experimental Economics. Cambridge University Press.","DOI":"10.1017\/CBO9780511528354"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084358","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3084358","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3084358","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:03:47Z","timestamp":1750215827000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084358"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,30]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11,30]]}},"alternative-id":["10.1145\/3084358"],"URL":"https:\/\/doi.org\/10.1145\/3084358","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2017,11,30]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}