Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity
Authors: Ioannis Caragiannis, Kurt Mehlhorn, Nidhi Rathi
AAAI 2025 | Venue PDF | 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. |