Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
From MaRDI portal
Publication:5111230
DOI10.4230/LIPICS.MFCS.2017.16zbMATH Open1441.91019arXiv1705.07200MaRDI QIDQ5111230FDOQ5111230
Authors: Yansong Gao, Jie Zhang, Xiaotie Deng 
Publication date: 26 May 2020
Full work available at URL: https://arxiv.org/abs/1705.07200
Recommendations
- Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
- Average-case approximation ratio of scheduling without payments
- Social welfare in one-sided matchings: random priority and beyond
- Size versus truncation robustness in the assignment problem
- Black-box randomized reductions in algorithmic mechanism design
Cites Work
- Introduction to algorithms.
- Algorithmic Game Theory
- Title not available (Why is that?)
- The Impossibility of Bayesian Group Decision Making with Separate Aggregation of Beliefs and Values
- Partial strategyproofness: relaxing strategyproofness for the random assignment problem
- Strategy-proof allocation of indivisible goods
- Title not available (Why is that?)
- Title not available (Why is that?)
- Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
- A new solution to the random assignment problem.
- Algorithmic mechanism design
- Scheduling without payments
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
- Algorithmic mechanism design (extended abstract)
- An introduction to strategy-proof social choice functions
- Mix and match: a strategyproof mechanism for multi-hospital kidney exchange
- Truthful approximation mechanisms for restricted combinatorial auctions
- Bayesian algorithmic mechanism design
- Truth revelation in approximately efficient combinatorial auctions
- Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
- Mathematical Foundations of Computer Science 2003
- A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms
- On a conjecture by Gale about one-sided matching problems
- Topology matters: smoothed competitiveness of metrical task systems
- Lotteries in student assignment: an equivalence result
- Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm
- Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method
- Smoothed analysis of termination of linear programming algorithms
- Stochastic mean payoff games: smoothed analysis and approximation schemes
- The Average number of pivot steps required by the Simplex-Method is polynomial
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- Smoothed analysis of binary search trees
- A lower bound for scheduling mechanisms
- Title not available (Why is that?)
- Optimal auctions vs. anonymous pricing
- Social welfare in one-sided matchings: random priority and beyond
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- On smoothed analysis of quicksort and Hoare's find
Cited In (3)
Uses Software
This page was built for publication: Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111230)
