5 citations · 6 across the 4 of their papers we have counts for
6 papers
On Scheduling Mechanisms Beyond the Worst Case
Yansong Gao, Jie Zhang
The problem of scheduling unrelated machines has been studied since the inception of algorithmic mechanism design \cite{NR99}. It is a resource allocation problem that entails assi…
Bounded Incentives in Manipulating the Probabilistic Serial Rule
Zihe Wang, Zhide Wei, Jie Zhang
The Probabilistic Serial mechanism is well-known for its desirable fairness and efficiency properties. It is one of the most prominent protocols for the random assignment problem.…
Social Cost Guarantees in Smart Route Guidance
Paolo Serafino, Carmine Ventre, Long Tran-Thanh +3
We model and study the problem of assigning traffic in an urban road network infrastructure. In our model, each driver submits their intended destination and is assigned a route to…
Average-case Analysis of the Assignment Problem with Independent Preferences
Yansong Gao, Jie Zhang
The fundamental assignment problem is in search of welfare maximization mechanisms to allocate items to agents when the private preferences over indivisible items are provided by s…
Average-case Approximation Ratio of Scheduling without Payments
Jie Zhang
Apart from the principles and methodologies inherited from Economics and Game Theory, the studies in Algorithmic Mechanism Design typically employ the worst-case analysis and appro…
Smoothed and Average-case Approximation Ratios of Mechanisms: Beyond the Worst-case Analysis
Xiaotie Deng, Yansong Gao, Jie Zhang
The approximation ratio has become one of the dominant measures in mechanism design problems. In light of analysis of algorithms, we define the \emph{smoothed approximation ratio}…