{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T07:55:49Z","timestamp":1767772549874,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,8,3]],"date-time":"2016-08-03T00:00:00Z","timestamp":1470182400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Google Inter-university Center for Electronic Markets and Auctions"},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Israeli Ministry of Science"},{"DOI":"10.13039\/501100005386","name":"Israeli Centers of Research Excellence program","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003977","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":[[2016,8,26]]},"abstract":"<jats:p>\n            We introduce the notion of\n            <jats:italic>local computation mechanism design<\/jats:italic>\n            \u2014designing game-theoretic mechanisms that run in polylogarithmic time and space. Local computation mechanisms reply to each query in polylogarithmic time and space, and the replies to different queries are consistent with the same global feasible solution. When the mechanism employs payments, the computation of the payments is also done in polylogarithmic time and space. Furthermore, the mechanism needs to maintain incentive compatibility with respect to the allocation and payments.\n          <\/jats:p>\n          <jats:p>We present local computation mechanisms for two classical game-theoretical problems: stable matching and job scheduling. For stable matching, some of our techniques may have implications to the global (non-LCA (Local Computation Algorithm)) setting. Specifically, we show that when the men\u2019s preference lists are bounded, we can achieve an arbitrarily good approximation to the stable matching within a fixed number of iterations of the Gale-Shapley algorithm.<\/jats:p>","DOI":"10.1145\/2956584","type":"journal-article","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T13:26:34Z","timestamp":1470317194000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Local Computation Mechanism Design"],"prefix":"10.1145","volume":"4","author":[{"given":"Avinatan","family":"Hassidim","sequence":"first","affiliation":[{"name":"Bar Ilan University, Ramat Gan, Israel"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Ramat Aviv, Israel"}]},{"given":"Shai","family":"Vardi","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Ramat Aviv, Israel"}]}],"member":"320","published-online":{"date-parts":[[2016,8,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095205"},{"key":"e_1_2_1_2_1","volume-title":"The Probabilistic Method","author":"Alon Noga","unstructured":"Noga Alon and Joel Spencer . 2008. The Probabilistic Method ( 3 rd ed.). John Wiley . Noga Alon and Joel Spencer. 2008. The Probabilistic Method (3rd ed.). John Wiley.","edition":"3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129086"},{"volume-title":"Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 482--491","author":"Aaron","key":"e_1_2_1_4_1","unstructured":"Aaron Archer and \u00c9va Tardos. 2001. Truthful mechanisms for one-parameter agents . In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 482--491 . Aaron Archer and \u00c9va Tardos. 2001. Truthful mechanisms for one-parameter agents. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 482--491."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1008"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807349"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.10.008"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"John W. Byers Jeffrey Considine and Michael Mitzenmacher. 2003. Simple load balancing for distributed hash tables. In IPTPS. 80--87.  John W. Byers Jeffrey Considine and Michael Mitzenmacher. 2003. Simple load balancing for distributed hash tables. In IPTPS. 80--87.","DOI":"10.1007\/978-3-540-45172-3_7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873682"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-007-0081-6"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00125-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.1.103.14256"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9353-9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90074-5"},{"key":"e_1_2_1_17_1","volume-title":"Irving","author":"Gusfield Dan","year":"1989","unstructured":"Dan Gusfield and Robert W . Irving . 1989 . The Stable Marriage Problem\u2014Structure and Algorithms. MIT Press . Dan Gusfield and Robert W. Irving. 1989. The Stable Marriage Problem\u2014Structure and Algorithms. MIT Press."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217033"},{"key":"e_1_2_1_19_1","unstructured":"Nicole Immorlica and Mohammad Mahdian. 2005. Marriage honesty and stability. In SODA. 53--62.   Nicole Immorlica and Mohammad Mahdian. 2005. Marriage honesty and stability. In SODA. 53--62."},{"key":"e_1_2_1_20_1","volume-title":"Mariages stables. Les Presses de l\u2019Universit\u00e9 de Montr\u00e9al","author":"Knuth Donald E.","year":"1976","unstructured":"Donald E. Knuth . 1976. Mariages stables. Les Presses de l\u2019Universit\u00e9 de Montr\u00e9al ( 1976 ). Donald E. Knuth. 1976. Mariages stables. Les Presses de l\u2019Universit\u00e9 de Montr\u00e9al (1976)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.99.3.608"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Enyue Lu and S. Q. Zheng. 2003. A parallel iterative improvement stable matching algorithm. In HiPC. 55--65.  Enyue Lu and S. Q. Zheng. 2003. A parallel iterative improvement stable matching algorithm. In HiPC. 55--65.","DOI":"10.1007\/978-3-540-24596-4_7"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_55"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Yishay Mansour and Shai Vardi. 2013. A local computation approximation scheme to maximum matching. In APPROX-RANDOM. 260--273.  Yishay Mansour and Shai Vardi. 2013. A local computation approximation scheme to maximum matching. In APPROX-RANDOM. 260--273.","DOI":"10.1007\/978-3-642-40328-6_19"},{"volume-title":"Game Theory","author":"Maschler Michael","key":"e_1_2_1_26_1","unstructured":"Michael Maschler , Eilon Solan , and Shmuel Zamir . 2013. Game Theory . Cambridge Press . Michael Maschler, Eilon Solan, and Shmuel Zamir. 2013. Game Theory. Cambridge Press."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219004"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.81"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301287"},{"key":"e_1_2_1_31_1","unstructured":"N. Nisan T. Roughgarden E. Tardos and V. Vazirani (Eds.). 2005. Algorithmic Game Theory. Cambridge University Press.   N. Nisan T. Roughgarden E. Tardos and V. Vazirani (Eds.). 2005. Algorithmic Game Theory. Cambridge University Press."},{"key":"e_1_2_1_32_1","volume-title":"On the communication complexity of finding an (approximate) stable marriage. CoRR abs\/1406.1273","author":"Ostrovsky Rafail","year":"2014","unstructured":"Rafail Ostrovsky and Will Rosenbaum . 2014. On the communication complexity of finding an (approximate) stable marriage. CoRR abs\/1406.1273 ( 2014 ). http:\/\/arxiv.org\/abs\/1406.1273. Rafail Ostrovsky and Will Rosenbaum. 2014. On the communication complexity of finding an (approximate) stable marriage. CoRR abs\/1406.1273 (2014). http:\/\/arxiv.org\/abs\/1406.1273."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01935367"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.05.007"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1001\/jama.289.7.909"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.89.4.748"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00002"},{"key":"e_1_2_1_38_1","volume-title":"Roth and Marilda Sotomayor","author":"Alvin","year":"1990","unstructured":"Alvin E. Roth and Marilda Sotomayor . 1990 . Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press . Alvin E. Roth and Marilda Sotomayor. 1990. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1086\/262074"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS). 223--238","author":"Rubinfeld Ronitt","year":"2011","unstructured":"Ronitt Rubinfeld , Gil Tamir , Shai Vardi , and Ning Xie . 2011 . Fast local computation algorithms . In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS). 223--238 . Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. 2011. Fast local computation algorithms. In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS). 223--238."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250829"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02136029"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792546"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248407"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2956584","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2956584","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:39:43Z","timestamp":1750217983000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2956584"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,3]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8,26]]}},"alternative-id":["10.1145\/2956584"],"URL":"https:\/\/doi.org\/10.1145\/2956584","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2016,8,3]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}