{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T18:26:09Z","timestamp":1780511169615,"version":"3.54.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,1,21]],"date-time":"2020-01-21T00:00:00Z","timestamp":1579564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2020,2,29]]},"abstract":"<jats:p>Realistic multi-agent team applications often feature dynamic environments with soft deadlines that penalize late execution of tasks. This puts a premium on quickly allocating tasks to agents. However, when such problems include temporal and spatial constraints that require tasks to be executed sequentially by agents, they are NP-hard, and thus are commonly solved using general and specifically designed incomplete heuristic algorithms.<\/jats:p>\n          <jats:p>We propose FMC_TA, a novel such incomplete task allocation algorithm that allows tasks to be easily sequenced to yield high-quality solutions. FMC_TA first finds allocations that are fair (envy-free), balancing the load and sharing important tasks among agents, and efficient (Pareto optimal) in a simplified version of the problem. It computes such allocations in polynomial or pseudo-polynomial time (centrally or distributedly, respectively) using a Fisher market with agents as buyers and tasks as goods. It then heuristically schedules the allocations, taking into account inter-agent constraints on shared tasks.<\/jats:p>\n          <jats:p>We empirically compare our algorithm to state-of-the-art incomplete methods, both centralized and distributed, on law enforcement problems inspired by real police logs. We present a novel formalization of the law enforcement problem, which we use to perform our empirical study. The results show a clear advantage for FMC_TA in total utility and in measures in which law enforcement authorities measure their own performance. Besides problems with realistic properties, the algorithms were compared on synthetic problems in which we increased the size of different elements of the problem to investigate the algorithm\u2019s behavior when the problem scales. The domination of the proposed algorithm was found to be consistent.<\/jats:p>","DOI":"10.1145\/3356467","type":"journal-article","created":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T22:12:06Z","timestamp":1585951926000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Market Clearing\u2013based Dynamic Multi-agent Task Allocation"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8964-2434","authenticated-orcid":false,"given":"Sofia Amador","family":"Nelke","sequence":"first","affiliation":[{"name":"HIT Holon Institute of Technology, Holon Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steven","family":"Okamoto","sequence":"additional","affiliation":[{"name":"Google, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roie","family":"Zivan","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,1,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multi-agent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1495--1496","author":"Amador Sofia","year":"2014"},{"key":"e_1_2_1_2_1","unstructured":"M. Arshad and M. C. Silaghi. 2004. Distributed simulated annealing. In Distributed Constraint Problem Solving and Reasoning in Multi-Agent Systems: Frontiers in Artificial Intelligence and Applications. IOS Press.  M. Arshad and M. C. Silaghi. 2004. Distributed simulated annealing. In Distributed Constraint Problem Solving and Reasoning in Multi-Agent Systems: Frontiers in Artificial Intelligence and Applications. IOS Press."},{"key":"e_1_2_1_3_1","volume-title":"Scarf","author":"Brainard William C.","year":"2000"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-012-9212-y"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2022423"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10846-014-0154-2"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS\u201902)","author":"Devanur N. R."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2006.876939"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-016-9579-8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-013-9225-1"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201908)","author":"Farinelli A."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375735.376439"},{"key":"e_1_2_1_13_1","volume-title":"The Theory of Linear Economic Models","author":"Gale D."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"J. Godoy and M. Gini. 2013. Task allocation for spatially and temporally distributed tasks. In Intelligent Autonomous Systems 12. Springer 603--612.  J. Godoy and M. Gini. 2013. Task allocation for spatially and temporally distributed tasks. In Intelligent Autonomous Systems 12. Springer 603--612.","DOI":"10.1007\/978-3-642-33932-5_56"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2407900"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS\u201907)","author":"Jones E. G."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the National Conference on Artificial Intelligence","volume":"21","author":"Koenig S."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1233813.1233816"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 25th Conference on Artificial Intelligence (AAAI\u201911)","author":"Macarthur K. S."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 17th International Conference on Parallel and Distributed Computing Systems. 15--17","author":"Maheswaran R. T."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2010.03.011"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence.","author":"Nunes Ernesto","year":"2015"},{"key":"e_1_2_1_23_1","volume-title":"C (April","author":"Nunes Ernesto","year":"2017"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multi-agent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 381--388","author":"Parker James","year":"2014"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/rob.21601"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers Inc., 1224--1229","author":"Paulussen T. O."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.3233\/MGS-180289"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the American Control Conference (ACC\u201912)","author":"Ponda Sameera S."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"D. Poole and A. K. Mackworth. 2010. Artificial Intelligence\u2014Foundations of Computational Agents. Cambridge University Press.  D. Poole and A. K. Mackworth. 2010. Artificial Intelligence\u2014Foundations of Computational Agents. Cambridge University Press.","DOI":"10.1017\/CBO9780511794797"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1883405.1883419"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201910)","author":"Ramchurn S. D."},{"key":"e_1_2_1_32_1","volume-title":"Modern Heuristic Techniques for Combinatorial Problems","author":"Reeves C. R."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/303285.303295"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/277390.277399"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1643275.1643304"},{"key":"e_1_2_1_36_1","volume-title":"The Algorithm Design Manual","author":"Skiena Steven","edition":"2"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the International Conference on Multi-Agent Systems. 325--332","author":"Walsh W. E."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-016-0771-5"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1177\/109434200101500305"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.2015.2504350"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2018.02.017"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.021"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.10.004"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"R. Zivan S. Okamoto and H. Peled. 2014. Explorative anytime local search for distributed constraint optimization. Artific. Intell. 211 (2014).  R. Zivan S. Okamoto and H. Peled. 2014. Explorative anytime local search for distributed constraint optimization. Artific. Intell. 211 (2014).","DOI":"10.1016\/j.artint.2014.03.002"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906061160"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3356467","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3356467","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:22:54Z","timestamp":1750202574000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3356467"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,21]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2,29]]}},"alternative-id":["10.1145\/3356467"],"URL":"https:\/\/doi.org\/10.1145\/3356467","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,21]]},"assertion":[{"value":"2019-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}