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

DOI10.1007/S10107-022-01902-8MaRDI QIDQ6120929zbMATH OpenFDO

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

Publication date 21 February 2024

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10107-022-01902-8

zbMATH Keywords

approximation ratiomechanism design without moneyresource augmentationserial dictatorship

Mathematics Subject Classification ID

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

Cites work

• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• A collection of lower bounds for online matching on the line
• A new solution to the random assignment problem.
• A randomized O(^2k)-competitive algorithm for metric bipartite matching
• A robust and optimal online algorithm for minimum metric bipartite matching
• 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
• Approximating optimal social choice under metric preferences
• Approximation and Online Algorithms
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• scientific article; zbMATH DE number 7236471 (Why is no real title available?)
• Manipulation of Schemes that Mix Voting with Chance
• Near-optimal asymmetric binary matrix partitions
• Oblivious algorithms for the maximum directed cut problem
• On-line algorithms for weighted bipartite matching and stable marriages
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online Weighted Matching
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Randomized online algorithms for minimum metric bipartite matching
• Randomized social choice functions under metric preferences
• Responsive lotteries
• Robust price of anarchy bounds via LP and Fenchel duality
• Size versus truthfulness in the house allocation problem
• Social welfare in one-sided matchings: random priority and beyond
• Speed is as powerful as clairvoyance
• Strategy-proof allocation of indivisible goods
• The distortion of distributed metric social choice
• The efficiency of fair division
• The Online Transportation Problem
• The Online Transportation Problem: On the Exponential Boost of One Extra Server
• The price of matching with metric preferences
• Truthful approximations to range voting
• Truthful Mechanisms for Matching and Clustering in an Ordinal World
• Wavelength management in WDM rings to maximize the number of connections

Cited in

(5)

• Optimizing over serial dictatorships
• Facility assignment with fair cost sharing: equilibrium and mechanism design
• Breaking the metric voting distortion barrier
• Estimating the expected social welfare and cost of random serial dictatorship
• Utilitarian distortion with predictions

This page was built for publication: Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6120929)