{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:16Z","timestamp":1750306336286,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,6,29]],"date-time":"2016-06-29T00:00:00Z","timestamp":1467158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100009043","name":"University of Patras","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009043","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Social Fund and Greek national funds through the research funding program Thales on \u201cAlgorithmic Game Theory,\u201d by \u201dCaratheodory\u201c research","award":["E.114"],"award-info":[{"award-number":["E.114"]}]},{"name":"ERC Advanced","award":["321171 (ALGAME)"],"award-info":[{"award-number":["321171 (ALGAME)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2016,7,26]]},"abstract":"<jats:p>\n            The seminal work of Myerson (Mathematics of OR \u201981) characterizes incentive-compatible single-item auctions among bidders with independent valuations. In this setting, relatively simple deterministic auction mechanisms achieve revenue optimality. When bidders have correlated valuations, designing the revenue-optimal deterministic auction is a computationally demanding problem; indeed, Papadimitriou and Pierrakos (STOC \u201911) proved that it is APX-hard, obtaining an explicit inapproximability factor of 1999\/2000 = 99.95%. In the current article, we strengthen this inapproximability factor to 63\/64 \u2248 98.5%. Our proof is based on a gap-preserving reduction from the M\n            <jats:sc>ax<\/jats:sc>\n            -NM 3SAT problem; a variant of the maximum satisfiability problem where each clause has exactly three literals and no clause contains both negated and unnegated literals. We furthermore show that the gap between the revenue of deterministic and randomized auctions can be as low as 13\/14 \u2248 92.9%, improving an explicit gap of 947\/948 \u2248 99.9% by Dobzinski, Fu, and Kleinberg (STOC \u201911).\n          <\/jats:p>","DOI":"10.1145\/2934309","type":"journal-article","created":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T14:08:13Z","timestamp":1467727693000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Limitations of Deterministic Auction Design for Correlated Bidders"],"prefix":"10.1145","volume":"8","author":[{"given":"Ioannis","family":"Caragiannis","sequence":"first","affiliation":[{"name":"University of Patras and CTI \u201cDiophantus\u201d, Greece, Rion, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Kaklamanis","sequence":"additional","affiliation":[{"name":"University of Patras and CTI \u201cDiophantus\u201d, Greece, Rion, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Kyropoulou","sequence":"additional","affiliation":[{"name":"University of Oxford, UK, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,6,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_24"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25510-6_6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1329125.1329260"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2307\/1911240"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913096"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_44"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993655"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2004.06.005"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.10"},{"volume-title":"Auction Theory","author":"Krishna Vijay","key":"e_1_2_1_10_1","unstructured":"Vijay Krishna . 2009. Auction Theory . Academic Press , San Diego, CA . Vijay Krishna. 2009. Auction Theory. Academic Press, San Diego, CA."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/2235520"},{"key":"e_1_2_1_12_1","volume-title":"Eighth World Congress (Econometric Society Monographs), M. Dewatripont, L. P. Hansen, and S. J. Turnovsky (Eds.).","volume":"3","author":"Maskin Eric","year":"2003","unstructured":"Eric Maskin . 2003 . Auctions and efficiency. In Advances in Economics and Econometrics: Theory and Applications , Eighth World Congress (Econometric Society Monographs), M. Dewatripont, L. P. Hansen, and S. J. Turnovsky (Eds.). Vol. 3 . 1--24. Eric Maskin. 2003. Auctions and efficiency. In Advances in Economics and Econometrics: Theory and Applications, Eighth World Congress (Econometric Society Monographs), M. Dewatripont, L. P. Hansen, and S. J. Turnovsky (Eds.). Vol. 3. 1--24."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/1911865"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_15_1","volume-title":"Vazirani","author":"Nisan Noam","year":"2007","unstructured":"Noam Nisan , Tim Roughgarden , \u00c9va Tardos , and Vijay V . Vazirani . 2007 . Algorithmic Game Theory. Cambridge University Press , New York, NY. Noam Nisan, Tim Roughgarden, \u00c9va Tardos, and Vijay V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993654"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/501158.501160"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652138"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482606"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2934309","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2934309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:54Z","timestamp":1750222494000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2934309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,29]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7,26]]}},"alternative-id":["10.1145\/2934309"],"URL":"https:\/\/doi.org\/10.1145\/2934309","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2016,6,29]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}