Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity
Authors: Ioannis Caragiannis, Kurt Mehlhorn, Nidhi Rathi
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We answer this question affirmatively and present an algorithm that uses polynomial number (specifically, O(n5) queries). This solves the main open problem stated by Caragiannis and Rathi (2024). Our analysis uses a potential function argument that measures progress towards learning the underlying edge-weight information. |
| Researcher Affiliation | Academia | 1Aarhus University, Aarhus, Denmark 2Max Planck Institute for Informatics, Saarbr ucken 3Saarland Informatics Campus, Germany EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: An efficient algorithm to find welfare-optimal action sequence for OSM |
| Open Source Code | No | The paper does not provide any concrete statement about releasing code for the methodology described in this paper. It refers to another paper (Caragiannis and Rathi (2024)) for details on a truthful implementation paradigm, not source code for the current work. |
| Open Datasets | No | The paper does not use or refer to any specific publicly available datasets for experimental evaluation. It discusses a theoretical model involving a 'complete bipartite graph G = Kn,n' and 'agent-item preferences' that are learned through 'action sequence queries'. |
| Dataset Splits | No | The paper does not use any specific datasets, therefore, it does not provide any information regarding dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical algorithm design and query complexity, and as such, does not provide any details about specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and describes an algorithm without presenting an empirical implementation. Therefore, it does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper presents theoretical work on algorithm design and query complexity, rather than empirical experiments. As such, it does not describe any experimental setup details, hyperparameters, or training configurations. |