Research map / Multi-agent systems and games / Games and equilibria
Parameterized Algorithms for Finding a Collective Set of Items
Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, Dušan Knop, Rolf Niedermeier
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 |
|---|---|---|---|
| parameterize by number of items instead of agents | OWA-WINNER · parameterized complexity | tractability | Improved |
| parameterize by size k of the collective set | OWA-WINNER · parameterized complexity | tractability | Hurt |
| use nonincreasing OWA vectors constant except first or last pi values, parameterized by agents and pi | OWA-WINNER with arbitrary utilities · parameterized complexity | tractability | Improved |
| use OWA vectors that are not nonincreasing | OWA-WINNER with arbitrary utilities · parameterized complexity | tractability | Hurt |
| switch from beta(1) to beta(2) OWA vector | beta(i)-WINNER · parameterized by agents | tractability | Hurt |
| restrict to approval utilities with rho nonincreasing pieces | alpha-weighted-WINNER · parameterized by agents and rho | tractability | Improved |
| use FPT algorithm for approval utilities to approximate Borda utilities | OWA-WINNER · approximation | tractability | Improved |
Closest papers by meaning
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.86)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.85)
- CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization (AAAI 2026 · similarity 0.84)
- Barely Random Algorithms and Collective Metrical Task Systems (NeurIPS 2024 · similarity 0.84)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.83)
- Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity (AAAI 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.
