Research map / Learning theory and algorithms / Submodular and game algorithms
Teams in Online Scheduling Polls: Game-Theoretic Aspects
Robert Bredereck, Jiehua Chen, Rolf Niedermeier, Svetlana Obraztsova, Nimrod Talmon
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict the search to one time slot for coalition members' nonzero declarations | Finding an improvement step in the team power game · Team power game | search scope | Improved |
| Bound coalition size by a constant | Searching for an improving coalition · Team power game | time complexity: polynomial time | Improved |
| Allow an unrestricted coalition to seek an improvement step | Improvement-step existence decision · Team power game | computational complexity: NP-complete | Hurt |
| Bound maximum true availability by three | 1-strong Nash equilibrium · Team power game | existence: a_max ≤ 3: always exists | Improved |
| Use coalition size two with maximum availability one | 2-strong Nash equilibrium · Team power game | existence: a_max = 1: always exists | Improved |
| Allow coalition size two when maximum availability is two | 2-strong Nash equilibrium · Team power game | existence: a_max = 2: does not always exist | Hurt |
| Allow unbounded coalition size in equilibrium existence | Nash-equilibrium existence decision · Team power game | computational complexity: coNP-hard | Hurt |
Closest papers by meaning
- Stability in Online Coalition Formation (AAAI 2024 · similarity 0.85)
- Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size (AAAI 2025 · similarity 0.84)
- The Complexity of Computing Robust Mediated Equilibria in Ordinal Games (AAAI 2024 · similarity 0.83)
- Team-Fictitious Play for Reaching Team-Nash Equilibrium in Multi-team Games (NeurIPS 2024 · similarity 0.83)
- Zero-Sum Games between Mean-Field Teams: Reachability-Based Analysis under Mean-Field Sharing (AAAI 2024 · similarity 0.83)
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
