Teams in Online Scheduling Polls: Game-Theoretic Aspects
Authors: Robert Bredereck, Jiehua Chen, Rolf Niedermeier, Svetlana Obraztsova, Nimrod Talmon
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce a corresponding game, where each team can declare a lower total availability in the scheduling poll in order to improve its relative attendance the pay-off. We are especially interested in situations where teams can form coalitions. We provide an efficient algorithm that, given a coalition, finds an optimal way for each team in a coalition to improve its pay-off. In contrast, we show that deciding whether such a coalition exists is NP-hard. We also study the existence of Nash equilibria: Finding Nash equilibria for various small sizes of teams and coalitions can be done in polynomial time while it is co NP-hard if the coalition size is unbounded. Main Contributions. We show that, depending on the size of the coalition (i.e., the number of teams that could deviate from their declared availabilities), the computational complexity of finding an improvement step for a given coalition and deciding whether an improvement step exists for an arbitrary coalition ranges from being polynomial-time solvable to being NP-hard; further, deciding whether an improvement step exists for any coalition of size at most t is W[2]-hard when parameterizing by the coalition size t. We show that a 1-strong Nash equilibrium always exists for some special profiles and we provide a simple polynomial-time algorithm for finding it in these cases. Finally, we show that deciding whether a t-strong Nash equilibrium exists is co NP-hard. Our results are summarized in Table 1. |
| Researcher Affiliation | Academia | 1University of Oxford, United Kingdom, robert.bredereck@cs.ox.ac.uk 2TU Berlin, Germany, {jiehua.chen, rolf.niedermeier}@tu-berlin.de 3I-CORE, Hebrew University of Jerusalem, Israel, svetlana.obraztsova@gmail.com 4I-CORE, Weizmann Institute of Science, Israel, nimrodtalmon77@gmail.com |
| Pseudocode | No | The paper describes algorithms and complexity results but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use or reference any datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup or hyperparameters. |