[{"file":[{"file_name":"2021_DiscreteApplMath_Zeiner.pdf","date_created":"2021-02-04T11:28:42Z","file_size":652739,"date_updated":"2021-02-04T11:28:42Z","creator":"dernst","success":1,"checksum":"f1039ff5a2d6ca116720efdb84ee9d5e","file_id":"9089","content_type":"application/pdf","relation":"main_file","access_level":"open_access"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0166218X"]},"publication_status":"published","volume":289,"issue":"1","license":"https://creativecommons.org/licenses/by/4.0/","oa_version":"Published Version","abstract":[{"text":"We study optimal election sequences for repeatedly selecting a (very) small group of leaders among a set of participants (players) with publicly known unique ids. In every time slot, every player has to select exactly one player that it considers to be the current leader, oblivious to the selection of the other players, but with the overarching goal of maximizing a given parameterized global (“social”) payoff function in the limit. We consider a quite generic model, where the local payoff achieved by a given player depends, weighted by some arbitrary but fixed real parameter, on the number of different leaders chosen in a round, the number of players that choose the given player as the leader, and whether the chosen leader has changed w.r.t. the previous round or not. The social payoff can be the maximum, average or minimum local payoff of the players. Possible applications include quite diverse examples such as rotating coordinator-based distributed algorithms and long-haul formation flying of social birds. Depending on the weights and the particular social payoff, optimal sequences can be very different, from simple round-robin where all players chose the same leader alternatingly every time slot to very exotic patterns, where a small group of leaders (at most 2) is elected in every time slot. Moreover, we study the question if and when a single player would not benefit w.r.t. its local payoff when deviating from the given optimal sequence, i.e., when our optimal sequences are Nash equilibria in the restricted strategy space of oblivious strategies. As this is the case for many parameterizations of our model, our results reveal that no punishment is needed to make it rational for the players to optimize the social payoff.","lang":"eng"}],"month":"01","intvolume":" 289","scopus_import":"1","ddc":["510"],"date_updated":"2023-08-04T11:12:41Z","department":[{"_id":"KrCh"}],"file_date_updated":"2021-02-04T11:28:42Z","_id":"8793","status":"public","article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"day":"31","publication":"Discrete Applied Mathematics","isi":1,"has_accepted_license":"1","year":"2021","date_published":"2021-01-31T00:00:00Z","doi":"10.1016/j.dam.2020.10.022","date_created":"2020-11-22T23:01:26Z","page":"392-415","acknowledgement":"We are grateful to Matthias Függer and Thomas Nowak for having raised our interest in the problem studied in this paper.\r\nThis work has been supported the Austrian Science Fund (FWF) projects S11405, S11407 (RiSE), and P28182 (ADynNet).","publisher":"Elsevier","quality_controlled":"1","oa":1,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"chicago":"Zeiner, Martin, Ulrich Schmid, and Krishnendu Chatterjee. “Optimal Strategies for Selecting Coordinators.” Discrete Applied Mathematics. Elsevier, 2021. https://doi.org/10.1016/j.dam.2020.10.022.","ista":"Zeiner M, Schmid U, Chatterjee K. 2021. Optimal strategies for selecting coordinators. Discrete Applied Mathematics. 289(1), 392–415.","mla":"Zeiner, Martin, et al. “Optimal Strategies for Selecting Coordinators.” Discrete Applied Mathematics, vol. 289, no. 1, Elsevier, 2021, pp. 392–415, doi:10.1016/j.dam.2020.10.022.","ama":"Zeiner M, Schmid U, Chatterjee K. Optimal strategies for selecting coordinators. Discrete Applied Mathematics. 2021;289(1):392-415. doi:10.1016/j.dam.2020.10.022","apa":"Zeiner, M., Schmid, U., & Chatterjee, K. (2021). Optimal strategies for selecting coordinators. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2020.10.022","ieee":"M. Zeiner, U. Schmid, and K. Chatterjee, “Optimal strategies for selecting coordinators,” Discrete Applied Mathematics, vol. 289, no. 1. Elsevier, pp. 392–415, 2021.","short":"M. Zeiner, U. Schmid, K. Chatterjee, Discrete Applied Mathematics 289 (2021) 392–415."},"title":"Optimal strategies for selecting coordinators","author":[{"last_name":"Zeiner","full_name":"Zeiner, Martin","first_name":"Martin"},{"full_name":"Schmid, Ulrich","last_name":"Schmid","first_name":"Ulrich"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"}],"external_id":{"isi":["000596823800035"]},"article_processing_charge":"No","project":[{"grant_number":"S11402-N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"}]},{"external_id":{"isi":["000466061100020"],"arxiv":["1708.08037"]},"article_processing_charge":"No","author":[{"orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"János","last_name":"Pach","full_name":"Pach, János"}],"title":"Thrackles: An improved upper bound","citation":{"ama":"Fulek R, Pach J. Thrackles: An improved upper bound. Discrete Applied Mathematics. 2019;259(4):266-231. doi:10.1016/j.dam.2018.12.025","apa":"Fulek, R., & Pach, J. (2019). Thrackles: An improved upper bound. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2018.12.025","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” Discrete Applied Mathematics, vol. 259, no. 4. Elsevier, pp. 266–231, 2019.","short":"R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.","mla":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” Discrete Applied Mathematics, vol. 259, no. 4, Elsevier, 2019, pp. 266–231, doi:10.1016/j.dam.2018.12.025.","ista":"Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied Mathematics. 259(4), 266–231.","chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” Discrete Applied Mathematics. Elsevier, 2019. https://doi.org/10.1016/j.dam.2018.12.025."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","project":[{"call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281"}],"page":"266-231","date_created":"2019-01-20T22:59:17Z","doi":"10.1016/j.dam.2018.12.025","date_published":"2019-04-30T00:00:00Z","year":"2019","isi":1,"publication":"Discrete Applied Mathematics","day":"30","oa":1,"publisher":"Elsevier","quality_controlled":"1","department":[{"_id":"UlWa"}],"date_updated":"2023-08-24T14:39:33Z","type":"journal_article","article_type":"original","status":"public","_id":"5857","issue":"4","related_material":{"record":[{"relation":"earlier_version","id":"433","status":"public"}]},"volume":259,"publication_status":"published","publication_identifier":{"issn":["0166218X"]},"language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/1708.08037","open_access":"1"}],"scopus_import":"1","intvolume":" 259","month":"04","abstract":[{"lang":"eng","text":"A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is [Formula presented](n−1), and that this bound is best possible for infinitely many values of n."}],"oa_version":"Preprint"}]