---
_id: '8793'
abstract:
- lang: eng
  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.
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)."
article_processing_charge: No
article_type: original
author:
- first_name: Martin
  full_name: Zeiner, Martin
  last_name: Zeiner
- first_name: Ulrich
  full_name: Schmid, Ulrich
  last_name: Schmid
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
citation:
  ama: Zeiner M, Schmid U, Chatterjee K. Optimal strategies for selecting coordinators.
    <i>Discrete Applied Mathematics</i>. 2021;289(1):392-415. doi:<a href="https://doi.org/10.1016/j.dam.2020.10.022">10.1016/j.dam.2020.10.022</a>
  apa: Zeiner, M., Schmid, U., &#38; Chatterjee, K. (2021). Optimal strategies for
    selecting coordinators. <i>Discrete Applied Mathematics</i>. Elsevier. <a href="https://doi.org/10.1016/j.dam.2020.10.022">https://doi.org/10.1016/j.dam.2020.10.022</a>
  chicago: Zeiner, Martin, Ulrich Schmid, and Krishnendu Chatterjee. “Optimal Strategies
    for Selecting Coordinators.” <i>Discrete Applied Mathematics</i>. Elsevier, 2021.
    <a href="https://doi.org/10.1016/j.dam.2020.10.022">https://doi.org/10.1016/j.dam.2020.10.022</a>.
  ieee: M. Zeiner, U. Schmid, and K. Chatterjee, “Optimal strategies for selecting
    coordinators,” <i>Discrete Applied Mathematics</i>, vol. 289, no. 1. Elsevier,
    pp. 392–415, 2021.
  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.” <i>Discrete
    Applied Mathematics</i>, vol. 289, no. 1, Elsevier, 2021, pp. 392–415, doi:<a
    href="https://doi.org/10.1016/j.dam.2020.10.022">10.1016/j.dam.2020.10.022</a>.
  short: M. Zeiner, U. Schmid, K. Chatterjee, Discrete Applied Mathematics 289 (2021)
    392–415.
corr_author: '1'
date_created: 2020-11-22T23:01:26Z
date_published: 2021-01-31T00:00:00Z
date_updated: 2026-04-16T09:15:13Z
day: '31'
ddc:
- '510'
department:
- _id: KrCh
doi: 10.1016/j.dam.2020.10.022
external_id:
  isi:
  - '000596823800035'
file:
- access_level: open_access
  checksum: f1039ff5a2d6ca116720efdb84ee9d5e
  content_type: application/pdf
  creator: dernst
  date_created: 2021-02-04T11:28:42Z
  date_updated: 2021-02-04T11:28:42Z
  file_id: '9089'
  file_name: 2021_DiscreteApplMath_Zeiner.pdf
  file_size: 652739
  relation: main_file
  success: 1
file_date_updated: 2021-02-04T11:28:42Z
has_accepted_license: '1'
intvolume: '       289'
isi: 1
issue: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '01'
oa: 1
oa_version: Published Version
page: 392-415
project:
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11402-N23
  name: Rigorous Systems Engineering
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
publication: Discrete Applied Mathematics
publication_identifier:
  eissn:
  - 1872-6771
  issn:
  - 0166-218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimal strategies for selecting coordinators
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 289
year: '2021'
...