{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T04:57:35Z","timestamp":1774673855901,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","license":[{"start":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T00:00:00Z","timestamp":1542326400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israeli Academy of Sciencesnder","award":["230\/10 ISF and 1435\/14 ISF"],"award-info":[{"award-number":["230\/10 ISF and 1435\/14 ISF"]}]},{"name":"Israeli Academy of Sciences"},{"DOI":"10.13039\/100000001","name":"National Science Foundation NSF","doi-asserted-by":"crossref","award":["CCF-1215965 NSF and CCF-1524062 NSF"],"award-info":[{"award-number":["CCF-1215965 NSF and CCF-1524062 NSF"]}],"id":[{"id":"10.13039\/100000001","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,11,30]]},"abstract":"<jats:p>Border\u2019s theorem gives an intuitive linear characterization of the feasible interim allocation rules of a Bayesian single-item environment, and it has several applications in economic and algorithmic mechanism design. All known generalizations of Border\u2019s theorem either restrict attention to relatively simple settings or resort to approximation. This article identifies a complexity-theoretic barrier that indicates, assuming standard complexity class separations, that Border\u2019s theorem cannot be extended significantly beyond the state of the art. We also identify a surprisingly tight connection between Myerson\u2019s optimal auction theory, when applied to public project settings, and some fundamental results in the analysis of Boolean functions.<\/jats:p>","DOI":"10.1145\/3274645","type":"journal-article","created":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T13:08:54Z","timestamp":1542373734000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Public Projects, Boolean Functions, and the Borders of Border\u2019s Theorem"],"prefix":"10.1145","volume":"6","author":[{"given":"Parikshit","family":"Gopalan","sequence":"first","affiliation":[{"name":"VMware Research, Palo Alto, CA"}]},{"given":"Noam","family":"Nisan","sequence":"additional","affiliation":[{"name":"Hebrew University and Microsoft Research"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}]}],"member":"320","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229017"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2307\/2938181"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-006-0080-z"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_66"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214021"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.88"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA11405"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634171"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.1961.24"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634170"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590772"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_32"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993655"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 736--745","author":"Elkind Edith","year":"2007"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA10592"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel L. Lov\u00e1sz and A. Schrijver. 1988. Geometric Algorithms and Combinatorial Optimization 2nd edition. Springer.  M. Gr\u00f6tschel L. Lov\u00e1sz and A. Schrijver. 1988. Geometric Algorithms and Combinatorial Optimization 2nd edition. Springer.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"S. Hart and P. J. Reny. 2014. Implementation of reduced form mechanisms: A simple approach and a new characterization. Economic Theory Bulletin (2014).  S. Hart and P. J. Reny. 2014. Implementation of reduced form mechanisms: A simple approach and a new characterization. Economic Theory Bulletin (2014).","DOI":"10.1007\/s40505-014-0055-3"},{"key":"e_1_2_1_18_1","first-page":"191","article-title":"A polynomial algorithm in linear programming","volume":"20","author":"Khachiyan L. G.","year":"1979","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913516"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913517"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.econlet.2010.09.019"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","volume-title":"Introduction to mechanism design (for computer scientists)","author":"Nisan Noam","DOI":"10.1017\/CBO9780511800481.011"},{"key":"e_1_2_1_24_1","volume-title":"Analysis of Boolean Functions","author":"O\u2019Donnell Ryan"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756466"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993654"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/45.1.95"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.16"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764515"},{"key":"e_1_2_1_30_1","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_32_1","volume-title":"Lectures on Polytopes","author":"Ziegler G. M."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274645","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274645","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:55Z","timestamp":1750208275000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274645"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,16]]},"references-count":32,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2018,11,30]]}},"alternative-id":["10.1145\/3274645"],"URL":"https:\/\/doi.org\/10.1145\/3274645","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,16]]},"assertion":[{"value":"2016-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}