We consider the problem of designing revenue-optimal mechanisms for selling two heterogeneous items to a single buyer. Designing a revenue-optimal mechanism for selling a single item is simple: Set a threshold price based on the distribution, and sell the item only when the buyer’s valuation exceeds the threshold. However, designing a revenue-optimal mechanism to sell two heterogeneous items is a harder problem. Even the simplest setting with two items and one buyer remains unsolved as yet. The partial characterizations available in the literature have succeeded in solving the problem largely for distributions that are bordered by the coordinate axes. We consider distributions that do not contain (0; 0) in their support sets. Specifically, we consider the buyer’s valuations to be distributed uniformly over arbitrary rectangles in the positive quadrant. We anticipate that the special cases we solve could be a guideline to un-derstand the methods to solve the general problem. We explore two different methods – the duality method and the virtual valuation method – and apply them to solve the problem for distributions that are not bordered by the coordinate axes. The thesis consists of two parts. In the first part, we consider the problem when the buyer has no demand constraints. We assume the buyer’s valuations to be uniformly distributed over an arbitrary rectangle [c1; c1 + b1] [c2; c2 + b2] in the positive quadrant. We first study the duality approach that solves the problem for the (c1; c2) = (0; 0) case. We then nontrivially extend this approach to provide an explicit solution for arbitrary nonnegative values of (c1; c2; b1; b2). We prove that the optimal mechanism is to sell the two items according to one of eight simple menus. The menus indicate that the items must be sold individually for certain values of (c1; c2), the items must be bundled for certain other values, and the auction is an interplay of individual sale and a bundled sale for the remaining values of (c1; c2). We conjecture that our method can be extended to a wider class of distributions. We provide some preliminary results to support the conjecture. In the second part, we consider the problem when the buyer has a unit-demand constraint. We assume the buyer’s valuations (z1; z2) to be uniformly distributed over an arbitrary rectangle [c; c + b1] [c; c + b2] in the positive quadrant, having its south-west corner on the line z1 = z2. We first show that the structure of the dual measure shows significant variations for different values of (c; b1; b2) which makes it hard to discover the correct dual measure, and hence to compute the solution. We then nontrivially extend the virtual valuation method to provide a complete, explicit solution for the problem considered. In particular, we prove that the optimal mechanism is structured into five simple menus. We then conjecture, with promising preliminary results, that the optimal mechanism when the valuations are uniformly distributed in an arbitrary rectangle [c1; c1 + b1] [c2; c2 + b2] is also structured according to similar menus.

Unit-demand auctions have been well studied with applications in several areas. In this dissertation, we discuss new variants of the unit-demand auction that are motivated by practical applications. We design mechanisms for these variants that have strong properties related to truthfulness, efficiency, scalability, and privacy. The main contributions of this dissertation can be divided into two parts. In the first part, we introduce a new variant of the classic sealed-bid unit-demand auction in which each item is associated with a put option; the put option of an item gives the seller the right to sell the item at a specified strike price to a specified bidder, regardless of market conditions. We motivate our unit-demand auction setting by discussing applications to the reassignment of leases, and to the design of multi-round auctions. For the classic sealed-bid unit-demand framework, the VCG mechanism provides a truthful auction with strong associated guarantees, including efficiency and envy-freedom. For an item in our auction, the strike price of the associated put imposes a lower bound on the auction price. Due to these lower bound constraints on auction prices, we find that the VCG mechanism is not suitable for our setting. Instead, our work draws on two fundamental techniques, one from the realm of mechanism design for numerical preferences -- the dynamic unit-demand approximate auction of Demange, Gale, and Sotomayor -- and one from the realm of mechanism design for ordinal preferences -- the Top Trading Cycles algorithm -- to obtain a natural auction that satisfies the lower bound constraints on auction prices. While we cannot, in general, achieve either efficiency or envy-freedom in our setting, our auction achieves suitably relaxed versions of these properties. For example, this auction is envy-free for all bidders who do not acquire an item via the exercise of a put. We provide a polynomial time implementation of this auction. By breaking ties in an appropriate manner, we are able to prove that this auction is truthful. In the second part, we specify rules for a dynamic unit-demand auction that supports arbitrary bid revision. In each round, the dynamic auction takes a tentative allocation and pricing as part of the input, and allows each bidder -- including a tentatively allocated bidder -- to submit an arbitrary unit-demand bid. Each round of our dynamic auction is implemented via a single application of the sealed-bid unit-demand auction proposed in the first part. We show that our dynamic auction satisfies strong properties related to truthfulness and efficiency. Using a certain privacy preservation property of each round of the auction, we show that the overall dynamic auction is highly resistant to shilling. We present a fast algorithm for implementing the proposed auction. Using this algorithm, the amortized cost of processing each bidding operation is upper bounded by the complexity of solving a single-source shortest paths problem on a graph with nonnegative edge weights and a node for each item in the auction. We also propose a dynamic price adjustment scheme that discourages sniping by providing bidders with incentives to bid early in the auction. / text

Cette thèse regroupe trois essais en théorie des enchères. Le chapitre 1 introduit de ladélégation dans le mécanisme d’enchère GSP. Dans un jeu impliquant des transferts monétaires et unepolitique de rémunération mise en place par une agence, un équilibre collusif efficace est atteint.Nousproposons une caractérisation du profil d’enchères collusif implémentable dans un jeu de positions `a troisjoueurs et deux positions. Le chapitre 2 considère des ventes séquentielles d’un objet `a deux acheteurs: l’unconnaît son évaluation privée tandis que l’autre non. Les acheteurs ont une demande multi-unitaire et lesévaluations privées entre unit´es sont parfaitement corrélées. Un équilibre asymétrique existe dans lequelle joueur non-informé adopte une stratégie agressive tandis que le joueur informé joue de manière prudente.Le comportement du joueur non-informé est justifié par l’opportunité d’acquérir de l’informationgratuitement. Cette dynamique induit une décroissance des prix entre les ventes. Le chapitre 3, introduitun jeu de décision séquentielle dans la première enchère. Un équilibre séparateur existe dans lequel lejoueur informé est agressif lorsqu’il est le premier `a jouer impliquant une stratégie de non-participationde la part de son concurrent non-informé. A l’inverse, ce dernier adopte une attitude plus prudentelorsqu’il est le premier `a joueur. Un équilibre mélangeant dans lequel le joueur informé cache son informationprivée ne peut exister que si le joueur non-informé adopte une stratégie de non-participation. / This thesis is a collection of three essays in theoretical auction analysis. Chapter 1 considersbid delegation in the GSP auction mechanism. In a game involving side-contracts and a compensationpolicy set by an agency, the first-best collusive outcome is achieved. We offer a characterization of the implementablebid profiles for the two-position game with three players. Chapter 2 considers the sequentialsale of an object to two buyers: one knows his private information and the other buyer does not. Buyershave a multi-unit demand and private valuations for each unit are perfectly correlated. An asymmetricequilibrium exists when the uninformed player adopts an aggressive bidding strategy. Conversely, hisinformed opponent behaves more conservatively by using bid shading. The bidding behaviour of theuninformed bidder is driven by the opportunity to learn his private valuation for free. This dynamic is atthe root of the decline in the equilibrium price across both sales. In chapter 3, information is observableduring the first-stage auction in a sequential-move game in which the first-mover bidder is observed byhis opponent. A separating equilibrium exists in which the informed bidder bids aggressively when he isthe first-mover which entails a non-participation strategy from his uninformed competitor. Conversely,the latter adopts a conservative behaviour when he is the first-mover. A pooling equilibrium in which theinformed bidder blurs his valuation can only exist if his uninformed opponent adopts a non-participatingstrategy.

No description available.