**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Publication# Distributional Robustness in Mechanism Design

Abstract

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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (43)

Probability distribution

In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon in terms of its sample space and the probabilities of events (subsets of the sample space). For instance, if X is used to denote the outcome of a coin toss ("the experiment"), then the probability distribution of X would take the value 0.5 (1 in 2 or 1/2) for X = heads, and 0.

Mechanism design

Mechanism design is a field in economics and game theory that takes an objectives-first approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts at the end of the game, then goes backwards, it is also called reverse game theory. It has broad applications, from economics and politics in such fields as market design, auction theory and social choice theory to networked-systems (internet interdomain routing, sponsored search auctions).

Auction

An auction is usually a process of buying and selling goods or services by offering them up for bids, taking bids, and then selling the item to the highest bidder or buying the item from the lowest bidder. Some exceptions to this definition exist and are described in the section about different types. The branch of economic theory dealing with auction types and participants' behavior in auctions is called auction theory. The open ascending price auction is arguably the most common form of auction and has been used throughout history.

Related publications (85)

Related MOOCs (13)

Advanced statistical physics

We explore statistical physics in both classical and open quantum systems. Additionally, we will cover probabilistic data analysis that is extremely useful in many applications.

Advanced statistical physics

We explore statistical physics in both classical and open quantum systems. Additionally, we will cover probabilistic data analysis that is extremely useful in many applications.

Selected Topics on Discrete Choice

Discrete choice models are used extensively in many disciplines where it is important to predict human behavior at a disaggregate level. This course is a follow up of the online course “Introduction t

Given two jointly distributed random variables (X,Y), a functional representation of X is a random variable Z independent of Y, and a deterministic function g(⋅,⋅) such that X=g(Y,Z). The problem of finding a minimum entropy functional representation is kn ...

2023We use generalized Ray-Knight theorems, introduced by B. Toth in 1996, together with techniques developed for excited random walks as main tools for establishing positive and negative results concerning convergence of some classes of diffusively scaled sel ...

The RIde-hail VEhicle Routing (RIVER) problem describes how drivers in a ride-hail market form a dynamic routing strategy according to the expected reward in each zone of the market. We model this decision-making problem as a Markov decision process (MDP), ...

2023