[{"publication":"Theoretical Computer Science","has_accepted_license":"1","month":"02","oa_version":"Submitted Version","project":[{"grant_number":"S11402-N23","name":"Rigorous Systems Engineering","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"Z211","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"264B3912-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Formal Methods meets Algorithmic Game Theory","grant_number":"M02369"}],"language":[{"iso":"eng"}],"date_published":"2020-02-06T00:00:00Z","type":"journal_article","oa":1,"publication_identifier":{"issn":["03043975"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","related_material":{"record":[{"relation":"earlier_version","id":"1341","status":"public"}]},"file":[{"creator":"dernst","file_id":"8639","success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_name":"2020_TheoreticalCS_Avni.pdf","date_updated":"2020-10-09T06:31:22Z","checksum":"e86635417f45eb2cd75778f91382f737","file_size":1413001,"date_created":"2020-10-09T06:31:22Z"}],"author":[{"id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5588-8287","full_name":"Avni, Guy","first_name":"Guy","last_name":"Avni"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger"},{"first_name":"Orna","last_name":"Kupferman","full_name":"Kupferman, Orna"}],"_id":"6761","scopus_import":"1","title":"Dynamic resource allocation games","intvolume":"       807","publication_status":"published","article_processing_charge":"No","date_created":"2019-08-04T21:59:20Z","department":[{"_id":"ToHe"}],"file_date_updated":"2020-10-09T06:31:22Z","page":"42-55","quality_controlled":"1","article_type":"original","publisher":"Elsevier","isi":1,"external_id":{"isi":["000512219400004"]},"date_updated":"2023-08-17T13:52:49Z","year":"2020","citation":{"short":"G. Avni, T.A. Henzinger, O. Kupferman, Theoretical Computer Science 807 (2020) 42–55.","mla":"Avni, Guy, et al. “Dynamic Resource Allocation Games.” <i>Theoretical Computer Science</i>, vol. 807, Elsevier, 2020, pp. 42–55, doi:<a href=\"https://doi.org/10.1016/j.tcs.2019.06.031\">10.1016/j.tcs.2019.06.031</a>.","ista":"Avni G, Henzinger TA, Kupferman O. 2020. Dynamic resource allocation games. Theoretical Computer Science. 807, 42–55.","ama":"Avni G, Henzinger TA, Kupferman O. Dynamic resource allocation games. <i>Theoretical Computer Science</i>. 2020;807:42-55. doi:<a href=\"https://doi.org/10.1016/j.tcs.2019.06.031\">10.1016/j.tcs.2019.06.031</a>","apa":"Avni, G., Henzinger, T. A., &#38; Kupferman, O. (2020). Dynamic resource allocation games. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2019.06.031\">https://doi.org/10.1016/j.tcs.2019.06.031</a>","ieee":"G. Avni, T. A. Henzinger, and O. Kupferman, “Dynamic resource allocation games,” <i>Theoretical Computer Science</i>, vol. 807. Elsevier, pp. 42–55, 2020.","chicago":"Avni, Guy, Thomas A Henzinger, and Orna Kupferman. “Dynamic Resource Allocation Games.” <i>Theoretical Computer Science</i>. Elsevier, 2020. <a href=\"https://doi.org/10.1016/j.tcs.2019.06.031\">https://doi.org/10.1016/j.tcs.2019.06.031</a>."},"abstract":[{"text":"In resource allocation games, selfish players share resources that are needed in order to fulfill their objectives. The cost of using a resource depends on the load on it. In the traditional setting, the players make their choices concurrently and in one-shot. That is, a strategy for a player is a subset of the resources. We introduce and study dynamic resource allocation games. In this setting, the game proceeds in phases. In each phase each player chooses one resource. A scheduler dictates the order in which the players proceed in a phase, possibly scheduling several players to proceed concurrently. The game ends when each player has collected a set of resources that fulfills his objective. The cost for each player then depends on this set as well as on the load on the resources in it – we consider both congestion and cost-sharing games. We argue that the dynamic setting is the suitable setting for many applications in practice. We study the stability of dynamic resource allocation games, where the appropriate notion of stability is that of subgame perfect equilibrium, study the inefficiency incurred due to selfish behavior, and also study problems that are particular to the dynamic setting, like constraints on the order in which resources can be chosen or the problem of finding a scheduler that achieves stability.","lang":"eng"}],"doi":"10.1016/j.tcs.2019.06.031","day":"06","ddc":["000"],"volume":807},{"date_published":"2014-02-13T00:00:00Z","type":"journal_article","date_updated":"2021-01-12T06:56:16Z","year":"2014","citation":{"ama":"Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. Alternating traps in Muller and parity games. <i>Theoretical Computer Science</i>. 2014;521:73-91. doi:<a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">10.1016/j.tcs.2013.11.032</a>","apa":"Grinshpun, A., Phalitnonkiat, P., Rubin, S., &#38; Tarfulea, A. (2014). Alternating traps in Muller and parity games. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">https://doi.org/10.1016/j.tcs.2013.11.032</a>","ieee":"A. Grinshpun, P. Phalitnonkiat, S. Rubin, and A. Tarfulea, “Alternating traps in Muller and parity games,” <i>Theoretical Computer Science</i>, vol. 521. Elsevier, pp. 73–91, 2014.","chicago":"Grinshpun, Andrey, Pakawat Phalitnonkiat, Sasha Rubin, and Andrei Tarfulea. “Alternating Traps in Muller and Parity Games.” <i>Theoretical Computer Science</i>. Elsevier, 2014. <a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">https://doi.org/10.1016/j.tcs.2013.11.032</a>.","mla":"Grinshpun, Andrey, et al. “Alternating Traps in Muller and Parity Games.” <i>Theoretical Computer Science</i>, vol. 521, Elsevier, 2014, pp. 73–91, doi:<a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">10.1016/j.tcs.2013.11.032</a>.","short":"A. Grinshpun, P. Phalitnonkiat, S. Rubin, A. Tarfulea, Theoretical Computer Science 521 (2014) 73–91.","ista":"Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. 2014. Alternating traps in Muller and parity games. Theoretical Computer Science. 521, 73–91."},"abstract":[{"text":"Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is to compute the winning regions for the players. Different classes and representations of Muller games lead to problems of varying computational complexity. One such class are parity games; these are of particular significance in computational complexity, as they remain one of the few combinatorial problems known to be in NP ∩ co-NP but not known to be in P. We show that winning regions for a Muller game can be determined from the alternating structure of its traps. To every Muller game we then associate a natural number that we call its trap depth; this parameter measures how complicated the trap structure is. We present algorithms for parity games that run in polynomial time for graphs of bounded trap depth, and in general run in time exponential in the trap depth. ","lang":"eng"}],"oa":1,"publist_id":"4703","doi":"10.1016/j.tcs.2013.11.032","publication_identifier":{"issn":["03043975"]},"day":"13","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","status":"public","volume":521,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1303.3777"}],"author":[{"full_name":"Grinshpun, Andrey","last_name":"Grinshpun","first_name":"Andrey"},{"first_name":"Pakawat","last_name":"Phalitnonkiat","full_name":"Phalitnonkiat, Pakawat"},{"full_name":"Rubin, Sasha","last_name":"Rubin","first_name":"Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Tarfulea, Andrei","first_name":"Andrei","last_name":"Tarfulea"}],"_id":"2246","publication":"Theoretical Computer Science","scopus_import":1,"month":"02","title":"Alternating traps in Muller and parity games","intvolume":"       521","oa_version":"Submitted Version","publication_status":"published","date_created":"2018-12-11T11:56:33Z","department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"page":"73 - 91","quality_controlled":"1","publisher":"Elsevier"}]