Distributional Robustness in Mechanism Design

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.

Dimensionality Reduction in Dynamic Optimization under Uncertainty

Napat Rujeerapaiboon

Dynamic optimization problems affected by uncertainty are ubiquitous in many application domains. Decision makers typically model the uncertainty through random variables governed by a probability distribution. If the distribution is precisely known, then the emerging optimization problems constitute stochastic programs or chance constrained programs. On the other hand, if the distribution is at least partially unknown, then the emanating optimization problems represent robust or distributionally robust optimization problems. In this thesis, we leverage techniques from stochastic and distributionally robust optimization to address complex problems in finance, energy systems management and, more abstractly, applied probability. In particular, we seek to solve uncertain optimization problems where the prior distributional information includes only the first and the second moments (and, sometimes, the support). The main objective of the thesis is to solve large instances of practical optimization problems. For this purpose, we develop complexity reduction and decomposition schemes, which exploit structural symmetries or multiscale properties of the problems at hand in order to break them down into smaller and more tractable components. In the first part of the thesis we study the growth-optimal portfolio, which maximizes the expected log-utility over a single investment period. In a classical stochastic setting, this portfolio is known to outperform any other portfolio with probability 1 in the long run. In the short run, however, it is notoriously volatile. Moreover, its performance suffers in the presence of distributional ambiguity. We design fixed-mix strategies that offer similar performance guarantees as the classical growth-optimal portfolio but for a finite investment horizon. Moreover, the proposed performance guarantee remains valid for any asset return distribution with the same mean and covariance matrix. These results rely on a Taylor approximation of the terminal logarithmic wealth that becomes more accurate as the rebalancing frequency is increased. In the second part of the thesis, we demonstrate that such a Taylor approximation is in fact not necessary. Specifically, we derive sharp probability bounds on the tails of a product of non-negative random variables. These generalized Chebyshev bounds can be computed numerically using semidefinite programming--in some cases even analytically. Similar techniques can also be used to derive multivariate Chebyshev bounds for sums, maxima, and minima of random variables. In the final part of the thesis, we consider a multi-market reservoir management problem. The eroding peak/off-peak spreads on European electricity spot markets imply reduced profitability for the hydropower producers and force them to participate in the balancing markets. This motivates us to propose a two-layer stochastic programming model for the optimal operation of a cascade of hydropower plants selling energy on both spot and balancing markets. The planning problem optimizes the reservoir management over a yearly horizon with weekly granularity, and the trading subproblems optimize the market transactions over a weekly horizon with hourly granularity. We solve both the planning and trading problems in linear decision rules, and we exploit the inherent parallelizability of the trading subproblems to achieve computational tractability.

EPFL2016

Robust Multidimensional Pricing: Separation without Regret

Cagil Kocyigit, Daniel Kuhn, Napat Rujeerapaiboon

We study a robust monopoly pricing problem with a minimax regret objective, where a seller endeavors to sell multiple goods to a single buyer, only knowing that the buyer's values for the goods range over a rectangular uncertainty set. 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 the 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.

2018

On Linear Optimization over Wasserstein Balls

Daniel Kuhn, Wolfram Wiesemann

Wasserstein balls, which contain all probability measures within a pre-specified Wasserstein distance to a reference measure, have recently enjoyed wide popularity in the distributionally robust optimization and machine learning communities to formulate and solve data-driven optimization problems with rigorous statistical guarantees. In this technical note we prove that the Wasserstein ball is weakly compact under mild conditions, and we offer necessary and sufficient conditions for the existence of optimal solutions. We also characterize the sparsity of solutions if the Wasserstein ball is centred at a discrete reference measure. In comparison with the existing literature, which has proved similar results under different conditions, our proofs are self-contained and shorter, yet mathematically rigorous, and our necessary and sufficient conditions for the existence of optimal solutions are easily verifiable in practice.

2020

Dimensionality Reduction in Dynamic Optimization under Uncertainty

Napat Rujeerapaiboon

EPFL2016