Yiannis Giannakopoulos

On the Power of Determinism in Multi-Item Auctions

We study the classical multi-item monopoly setting with a single additive buyer and $m$ heterogeneous items whose values are independent but not necessarily identically distributed. Optimal truthful auctions may be randomized and complicated. We analyze the approximation ratios of three simple deterministic auctions: s...