{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:25:05Z","timestamp":1750307105637,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,1,25]],"date-time":"2013-01-25T00:00:00Z","timestamp":1359072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000690","name":"Research Councils UK","doi-asserted-by":"publisher","award":["EP\/1011587\/1"],"award-info":[{"award-number":["EP\/1011587\/1"]}],"id":[{"id":"10.13039\/501100000690","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":[[2013,1,25]]},"abstract":"<jats:p>We study dominant-strategy mechanisms in allocation domains where agents have one-dimensional types and quasilinear utilities. Taking an allocation function as an input, we present an algorithmic technique for finding optimal payments in a class of mechanism design problems, including utilitarian and egalitarian allocation of homogeneous items with nondecreasing marginal costs. Our results link optimality of payment functions to a geometric condition involving triangulations of polytopes. When this condition is satisfied, we constructively show the existence of an optimal payment function that is piecewise linear in agent types.<\/jats:p>","DOI":"10.1145\/2399187.2399191","type":"journal-article","created":{"date-parts":[[2013,5,16]],"date-time":"2013-05-16T18:02:44Z","timestamp":1368727364000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Optimal payments in dominant-strategy mechanisms for single-parameter domains"],"prefix":"10.1145","volume":"1","author":[{"given":"Victor","family":"Naroditskiy","sequence":"first","affiliation":[{"name":"University of Southampton, Southampton, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Polukarov","sequence":"additional","affiliation":[{"name":"University of Southampton, Southampton, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicholas R.","family":"Jennings","sequence":"additional","affiliation":[{"name":"University of Southampton and King Abdulaziz University, Southampton, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,1,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_48"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875583"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017949922773"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1160633.1160790"},{"volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI). 103--110","author":"Conitzer V.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-2354.t01-1-00102"},{"key":"e_1_2_1_7_1","unstructured":"de Clippel G. Naroditskiy V. Polukarov M. Greenwald A. and Jennings N. R. 2012. Destroy to save. Games and Economic Behavior.  de Clippel G. Naroditskiy V. Polukarov M. Greenwald A. and Jennings N. R. 2012. Destroy to save. Games and Economic Behavior."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"De Loera J. Rambau J. and Santos F. 2010. Triangulations. Springer.  De Loera J. Rambau J. and Santos F. 2010. Triangulations. Springer.","DOI":"10.1007\/978-3-642-12971-1"},{"volume-title":"Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI). 1347--1354","author":"Dufton L.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386825"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.06.007"},{"volume-title":"Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI). 1676--1679","author":"Guo M.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25510-6_14"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Hardin G. 1968. The tragedy of the commons. Science 162 3859 1243--1248.  Hardin G. 1968. The tragedy of the commons. Science 162 3859 1243--1248.","DOI":"10.1126\/science.162.3859.1243"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-006-0165-8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2008.03.003"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Nisan N. Roughgarden T. Tardos E. and Vazirani V. 2007. Algorithmic Game Theory. Cambridge University Press New York NY.   Nisan N. Roughgarden T. Tardos E. and Vazirani V. 2007. Algorithmic Game Theory. Cambridge University Press New York NY.","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2003.11.005"},{"key":"e_1_2_1_21_1","unstructured":"Roberts K. 1979. The characterization of implementable social choice rules. In Aggregation and Revelation of Preferences.  Roberts K. 1979. The characterization of implementable social choice rules. In Aggregation and Revelation of Preferences."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2399187.2399191","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2399187.2399191","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:35:01Z","timestamp":1750239301000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2399187.2399191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,25]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1,25]]}},"alternative-id":["10.1145\/2399187.2399191"],"URL":"https:\/\/doi.org\/10.1145\/2399187.2399191","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2013,1,25]]},"assertion":[{"value":"2011-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}