Research map / Multi-agent systems and games / Games and equilibria
Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives an algorithm that finds a welfare-optimal serial dictatorship action sequence for bipartite matching using polynomially many (n^5) action-sequence queries, with a potential-function analysis and a truthful VCG-style implementation.
Problem
Computing a social-welfare-optimal agent sequence for serial dictatorship in one-sided matching when agent-item values are unknown and can only be learned by querying action sequences.
Approach
Maintains a proxy graph whose edge weights overestimate true weights, runs the maximum-weight PO matching's serial dictatorship sequence on the proxy, and uses a lexicographic potential (known edges, weight error, rank error) to bound queries by n^5, answering the open problem of Caragiannis and Rathi.
Key results
- Algorithm finds a welfare-optimal action sequence for n-agent bipartite matching using n^5 action-sequence queries.
- If edges incident to each agent have pairwise distinct weights, the query count drops to n^4.
- The algorithm gives an alternate proof that the price of serial dictatorship for maximum-weight perfect matching is 1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed query algorithm | n-agent OSM instances · n-agent OSM instances | query complexity: n^5 | Helped |
| Assume pairwise distinct weights on edges incident to each agent | the proposed algorithm · n-agent OSM instances with pairwise distinct incident-edge weights | query complexity: n^5 -> n^4 | Helped |
Limitations
- Lower bound on query complexity is not known.
- Analysis is specific to bipartite matchings; extension beyond matchings is open.
Experimental setup
Metrics: query complexity
Builds on: Caragiannis and Rathi query framework for price of serial dictatorship maximum-weight Pareto-optimal matching sequencing algorithm
Closest papers by meaning
- Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond (NeurIPS 2022 · similarity 0.89)
- Strategyproof Matching of Roommates and Rooms (AAAI 2025 · similarity 0.87)
- Every Bit Helps: Achieving the Optimal Distortion with a Few Queries (AAAI 2025 · similarity 0.86)
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.86)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.86)
- MATWA: A Web Toolkit for Matching Under Preferences (AAAI 2025 · similarity 0.85)
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.