Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
From MaRDI portal
Publication:2672280
DOI10.1016/j.ic.2022.104920zbMath1492.91078OpenAlexW4280632634MaRDI QIDQ2672280
Yansong Gao, Jie Zhang, Xiaotie Deng
Publication date: 8 June 2022
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2022.104920
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Truth, justice, and cake cutting
- Approximating optimal social choice under metric preferences
- Why do popular mechanisms lack efficiency in random environments?
- A solution to the random assignment problem on the full preference domain
- A lower bound for scheduling mechanisms
- Smoothed analysis of termination of linear programming algorithms
- Scheduling without payments
- House allocation with existing tenants
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- On a conjecture by Gale about one-sided matching problems
- Smoothed analysis of binary search trees
- Strategy-proof allocation of indivisible goods
- On smoothed analysis of quicksort and Hoare's find
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- The computational complexity of random serial dictatorship
- Truthful approximation mechanisms for restricted combinatorial auctions
- Topology matters: smoothed competitiveness of metrical task systems
- Algorithmic mechanism design (extended abstract)
- Bayesian algorithmic mechanism design
- Social Welfare in One-Sided Matchings: Random Priority and Beyond
- Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
- Lotteries in student assignment: An equivalence result
- Social Welfare in One-Sided Matching Markets without Money
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
- Settling the complexity of computing two-player Nash equilibria
- Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
- The Average number of pivot steps required by the Simplex-Method is polynomial
- Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
- Smoothed analysis of algorithms
- Mathematical Foundations of Computer Science 2003
- Algorithmic Game Theory
- A new solution to the random assignment problem.
This page was built for publication: Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
