The gap and the gain : improving the approximate mechanism design frontier in constrained environments

The main focus of this thesis is the design of strategyproof mechanisms. Part One considers two mechanism design problems without monetary transfers in the learning-augmented framework. Both problems are augmented with a prediction of the optimal solution, and all mechanisms provide error-dependent approximation guarantees that interpolate between the consistency and robustness guarantees. Chapter 3 considers the generalized assignment problem (GAP) in the private graph model. For the bipartite matching problem our mechanism achieves the optimal consistency-robustness trade-off. For more general GAP variants we derive randomized mechanisms with improved approximation guarantees in expectation. In Chapter 4, we first introduce outliers within mechanism design and apply it to the single facility location problem on the real line. We focus on either minimizing the utilitarian or egalitarian objective, but only for a subset of agents. For the egalitarian objective, our mechanism achieves a tight 2-approximation which cannot be improved by augmenting the problem with predictions. We also derive tight results for the utilitarian objective, in which case augmenting with predictions does lead to improved guarantees. Part Two considers budget-feasible mechanism design in which monetary transfers are limited. Namely, we consider knapsack procurement auctions with concave and non-decreasing valuations and in which partial allocations are allowed. We derive constant factor approximation guarantees and for linear valuations, we show a separation between the divisible and indivisible setting. In Part Three, we study the efficiency of equilibrium outcomes (price of anarchy (POA)) of simultaneous single-item first-price auctions under the hybrid agent model with return-on-investment constraints. We introduce a new smoothness framework through which we derive bounds on the POA for coarse correlated equilibria, fractionally subadditive valuations, and any composition of agent types. In case of feasible reserve prices, we also derive bounds for additive valuations.

• View at Worldcat

Free Full Text ( Final Version , 2mb )