{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:55:38Z","timestamp":1750308938624,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,2,5]],"date-time":"2018-02-05T00:00:00Z","timestamp":1517788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007618","name":"University of Chicago Booth School of Business","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007618","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2018,2,28]]},"abstract":"<jats:p>\n            We study pricing equilibria for graphical valuations, whichare a class of valuations that admit a compact representation. These valuations are associated with a value graph, whose nodes correspond to items, and edges encode (pairwise) complementarities\/substitutabilities between items. It is known that for graphical valuations a Walrasian equilibrium (a pricing equilibrium that relies on anonymous item prices) does not exist in general. On the other hand, a pricing equilibrium exists when the seller uses an\n            <jats:italic>agent-specific graphical pricing<\/jats:italic>\n            rule that involves prices for each item and markups\/discounts for pairs of items. We study the existence of pricing equilibria with simpler pricing rules which either (i) require anonymity (so that prices are identical for all agents) while allowing for pairwise markups\/discounts or (ii) involve offering prices only for items. We show that a pricing equilibrium with the latter pricing rule exists if and only if a Walrasian equilibrium exists, whereas the former pricing rule may guarantee the existence of a pricing equilibrium even for graphical valuations that do not admit a Walrasian equilibrium. Interestingly, by exploiting a novel connection between the existence of a pricing equilibrium and the partitioning polytope associated with the underlying graph, we also establish that for simple (series-parallel) value graphs, a pricing equilibrium with anonymous graphical pricing rule exists if and only if a Walrasian equilibrium exists. These equivalence results imply that simpler pricing rules (i) and (ii) do not guarantee the existence of a pricing equilibrium for all graphical valuations.\n          <\/jats:p>","DOI":"10.1145\/3175495","type":"journal-article","created":{"date-parts":[[2018,2,6]],"date-time":"2018-02-06T18:13:28Z","timestamp":1517940808000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Pricing Equilibria and Graphical Valuations"],"prefix":"10.1145","volume":"6","author":[{"given":"Ozan","family":"Candogan","sequence":"first","affiliation":[{"name":"University of Chicago, Booth School of Business"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Asuman","family":"Ozdaglar","sequence":"additional","affiliation":[{"name":"MIT, EECS"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo","family":"Parrilo","sequence":"additional","affiliation":[{"name":"MIT, EECS"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,2,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229016"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.rpm.5170119"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1257\/0002828043052330"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.96.3.602"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2202\/1534-5955.1019"},{"volume-title":"Internet: E-auction and Markets","year":"2002","author":"Bikhchandani S.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1996.2269"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.2001.2957"},{"volume-title":"Combinatorial auctions","author":"Blumrosen Liad","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1958003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Eric Budish G\u00e9rard P. Cachon Judd B. Kessler and Abraham Othman. 2016. Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Res. (2016) to appear.  Eric Budish G\u00e9rard P. Cachon Judd B. Kessler and Abraham Othman. 2016. Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Res. (2016) to appear.","DOI":"10.2139\/ssrn.2635243"},{"volume-title":"Kessler","year":"2016","author":"Budish Eric","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3215559.3215561"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480191199415"},{"key":"e_1_2_1_16_1","first-page":"248","article-title":"Combinatorial auctions with k-wise dependent valuations","volume":"5","author":"Conitzer Vincent","year":"2005","journal-title":"AAAI"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1162\/105864097567174"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Peter Cramton Yoav Shoham and Richard Steinberg. 2006. Combinatorial Auctions. MIT Press.   Peter Cramton Yoav Shoham and Richard Steinberg. 2006. Combinatorial Auctions. MIT Press.","DOI":"10.7551\/mitpress\/9780262033428.001.0001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.07.010"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.15.3.284.16077"},{"volume-title":"Graph Theory","author":"Diestel Reinhard","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(65)90125-3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2580"},{"volume-title":"Jensen and Bjarne Toft","year":"2011","author":"Tommy","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"A. S. Kelso and V. P. Crawford. 1982. Job matching coalition formation and gross substitutes. Econom.: J. Econom. Soc. (1982) 1483--1504.  A. S. Kelso and V. P. Crawford. 1982. Job matching coalition formation and gross substitutes. Econom.: J. Econom. Soc. (1982) 1483--1504.","DOI":"10.2307\/1913392"},{"volume-title":"Parkes","year":"2009","author":"Lahaie S\u00e9bastien","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1086\/262118"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.09.004"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2004.10.007"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems","volume":"1","author":"Othman Abraham","year":"2010"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/336992.337032"},{"volume-title":"Iterative combinatorial auctions","author":"Parkes D. C.","key":"e_1_2_1_34_1","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/9780262033428.003.0003"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764515"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2006.00708.x"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA6514"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1086\/674550"},{"volume-title":"Mechanism Design: A Linear Programming Approach","year":"2011","author":"Vohra Rakesh V.","key":"e_1_2_1_40_1"},{"volume-title":"Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing. IEEE, 499--506","author":"Zhou H.","key":"e_1_2_1_41_1"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3175495","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3175495","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:37:00Z","timestamp":1750282620000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3175495"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,5]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2,28]]}},"alternative-id":["10.1145\/3175495"],"URL":"https:\/\/doi.org\/10.1145\/3175495","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2018,2,5]]},"assertion":[{"value":"2016-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}