Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship

DOI10.1007/s10107-022-01902-8MaRDI QIDQ6120929

Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Ioannis Caragiannis, Kristoffer Arnsfelt Hansen, Zihan Tan

Publication date: 21 February 2024

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

approximation ratioresource augmentationserial dictatorshipmechanism design without money

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25) Algorithmic game theory and complexity (91A68)

Cites Work

• Unnamed Item
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• Approximating optimal social choice under metric preferences
• The efficiency of fair division
• A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games
• Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
• On-line algorithms for weighted bipartite matching and stable marriages
• Near-optimal asymmetric binary matrix partitions
• A collection of lower bounds for online matching on the line
• Size versus truthfulness in the house allocation problem
• Oblivious algorithms for the maximum directed cut problem
• Strategy-proof allocation of indivisible goods
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• Truthful Approximations to Range Voting
• Social Welfare in One-Sided Matchings: Random Priority and Beyond
• Truthful Mechanisms for Matching and Clustering in an Ordinal World
• Randomized Social Choice Functions Under Metric Preferences
• Responsive Lotteries
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• The Price of Matching with Metric Preferences
• Randomized online algorithms for minimum metric bipartite matching
• Manipulation of Schemes that Mix Voting with Chance
• Speed is as powerful as clairvoyance
• The Online Transportation Problem
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
• Online Weighted Matching
• Robust Price of Anarchy Bounds via LP and Fenchel Duality
• Online bipartite matching with random arrivals
• The Online Transportation Problem: On the Exponential Boost of One Extra Server
• Approximation and Online Algorithms
• Wavelength Management in WDM Rings to Maximize the Number of Connections
• The distortion of distributed metric social choice
• A new solution to the random assignment problem.