Cagil Kocyigit
Mechanism design theory examines the design of allocation mechanisms or incentive systems involving multiple rational but self-interested agents and plays a central role in many societally important problems in economics. In mechanism design problems, agents typically hold private information that is unknown to the others. Traditionally, the mechanism design literature models this information asymmetry through random variables that are governed by a probability distribution, which is known precisely by all agents. However, the knowledge of such a distribution may be difficult to justify, especially when the available data is scarce. In this thesis, we address this concern by assuming that the underlying probability distribution is unknown but belongs to an ambiguity set, which is commonly known. An ambiguity set is a set of distributions and typically contains all distributions consistent with the information available. We leverage techniques from distributionally robust optimization to investigate how decisions of a mechanism designer are affected by distributional ambiguity. In the first part of the thesis, we study a distributionally robust single-item auction design problem, where the seller aims to design a revenue maximizing auction that is not only immunized against the ambiguity of the bidder values but also against the uncertainty about the bidders' attitude towards ambiguity. For ambiguity sets that contain all distributions supported on a hypercube or that contain only distributions under which the bidders' values are independent, we show that the classical second price auctions are essentially optimal. For more realistic ambiguity sets under which the bidders' values are characterized through moment bounds, we identify a new mechanism, the optimal highest-bidder-lottery, whose revenues cannot be matched by any second price auction with a constant number of additional bidders. We also show that the optimal highest-bidder-lottery provides a 2-approximation of the (unknown) optimal mechanism, whereas the best second price auction fails to provide any constant-factor approximation guarantee. In the second part, we study a robust monopoly pricing problem with a minimax regret objective, where a seller endeavors to sell multiple goods to a single buyer and has no knowledge of the underlying distribution apart from its support. We interpret this pricing problem as a zero-sum game between the seller, who chooses a selling mechanism, and a fictitious adversary or nature, who chooses the buyer's values from within an uncertainty set. Using duality techniques rooted in robust optimization, we prove that this game admits a Nash equilibrium in mixed strategies that can be computed in closed form. The Nash strategy of the seller is a randomized posted price mechanism under which the goods are sold separately, while the Nash strategy of nature is a distribution on the uncertainty set under which the buyer's values are comonotonic. We further show that the restriction of the pricing problem to deterministic mechanisms is solved by a deteministic posted price mechanism under which the goods are sold separately. In the last part, we consider the multi-bidder variant of the mechanism design problem studied in the second part. We show that the separation result persists and that the optimal auction is separable across items, that is, at optimality the seller uses an an individual auction separately for each item.
EPFL2020
