We study the truthful facility assignment problem, where a set of agents with private most-preferred points on a metric space are assigned to facilities that lie on the metric space, under capacity constraints on the facilities. The goal is to produce such an assignment that minimizes the social cost, i.e., the total distance between the most-preferred points of the agents and their corresponding facilities in the assignment, under the constraint of truthfulness, which ensures that agents do not misreport their most-preferred points. We propose a resource augmentation framework, where a truthful mechanism is evaluated by its worst-case performance on an instance with enhanced facility capacities against the optimal mechanism on the same instance with the original capacities. We study a very well-known mechanism, Serial Dictatorship, and provide an exact analysis of its performance. Although Serial Dictatorship is a purely combinatorial mechanism, our analysis uses linear programming; a linear program expresses its greedy nature as well as the structure of the input, and finds the input instance that enforces the mechanism have its worst-case performance. Bounding the objective of the linear program using duality arguments allows us to compute tight bounds on the approximation ratio. Among other results, we prove that Serial Dictatorship has approximation ratio @math when the capacities are multiplied by any integer @math . Our results suggest that even a limited augmentation of the resources can have wondrous effects on the performance of the mechanism and in particular, the approximation ratio goes to 1 as the augmentation factor becomes large. We complement our results with bounds on the approximation ratio of Random Serial Dictatorship, the randomized version of Serial Dictatorship, when there is no resource augmentation.
Assignment problems are central in the literature of economics and computer science; the literature on one-sided matchings dates back to the seminal paper by Hylland and Zeckhauser @cite_1 and includes many very influential papers @cite_15 @cite_12 in economics as well as a rich recent literature in computer science @cite_29 @cite_5 @cite_32 . Serial Dictatorships (or their randomized counterparts) have been in the focus of much of this literature, mainly due to their simplicity and the fragile nature of truthfulness, which makes it quite hard to construct more involved truthful mechanisms. In a celebrated result, Svensson @cite_12 characterized a large class of truthful mechanisms by serial dictatorships. Random Serial Dictatorship has also been extensively studied @cite_31 @cite_34 and recently it was proven @cite_30 that is asymptotically the best truthful mechanism for one-sided matchings under the general cardinal preference domain.
@cite_30 @cite_31 @cite_29 @cite_1 @cite_32 @cite_5 @cite_15 @cite_34 @cite_12
1830090996 2063004177 49938292 2950990081 2036929816 1996818906
We study the problem of approximate social welfare maximization (without money) in one-sided matching problems when agents have unrestricted cardinal preferences over a finite set of items. Random priority is a very well-known truthful-in-expectation mechanism for the problem. We prove that the approximation ratio of random priority is Θ(n − 1 2) while no truthful-in-expectation mechanism can achieve an approximation ratio better than O(n − 1 2), where n is the number of agents and items. Furthermore, we prove that the approximation ratio of all ordinal (not necessarily truthful-in-expectation) mechanisms is upper bounded by O(n − 1 2), indicating that random priority is asymptotically the best truthful-in-expectation mechanism and the best ordinal mechanism for the problem. We study the House Allocation problem (also known as the Assignment problem), i.e., the problem of allocating a set of objects among a set of agents, where each agent has ordinal preferences (possibly involving ties) over a subset of the objects. We focus on truthful mechanisms without monetary transfers for finding large Pareto optimal matchings. It is straightforward to show that no deterministic truthful mechanism can approximate a maximum cardinality Pareto optimal matching with ratio better than 2. We thus consider randomized mechanisms. We give a natural and explicit extension of the classical Random Serial Dictatorship Mechanism (RSDM) specifically for the House Allocation problem where preference lists can include ties. We thus obtain a universally truthful randomized mechanism for finding a Pareto optimal matching and show that it achieves an approximation ratio of eovere-1. The same bound holds even when agents have priorities (weights) and our goal is to find a maximum weight (as opposed to maximum cardinality) Pareto optimal matching. On the other hand we give a lower bound of 18 over 13 on the approximation ratio of any universally truthful Pareto optimal mechanism in settings with strict preferences. In the case that the mechanism must additionally be non-bossy, an improved lower bound of eovere-1 holds. This lower bound is tight given that RSDM for strict preference lists is non-bossy. We moreover interpret our problem in terms of the classical secretary problem and prove that our mechanism provides the best randomized strategy of the administrator who interviews the applicants. We investigate the problem of allocating items (private goods) among competing agents in a setting that is both prior-free and payment-free. Specificall, we focus on allocating multiple heterogeneous items between two agents with additive valuation functions. Our objective is to design strategy-proof mechanisms that are competitive against the most efficien (first-best allocation. We introduce the family of linear increasing-price (LIP) mechanisms. The LIP mechanisms are strategy-proof, prior-free, and payment-free, and they are exactly the increasing-price mechanisms satisfying a strong responsiveness property. We show how to solve for competitive mechanisms within the LIP family. For the case of two items, we fin a LIP mechanism whose competitive ratio is near optimal (the achieved competitive ratio is 0.828, while any strategy-proof mechanism is at most 0.841-competitive). As the number of items goes to infinit, we prove a negative result that any increasing-price mechanism (linear or nonlinear) has a maximal competitive ratio of 0.5. Our results imply that in some cases, it is possible to design good allocation mechanisms without payments and without priors. We study mechanism design problems in the ordinal setting wherein the preferences of agents are described by orderings over outcomes, as opposed to specific numerical values associated with them. This setting is relevant when agents can compare outcomes, but aren't able to evaluate precise utilities for them. Such a situation arises in diverse contexts including voting and matching markets. Our paper addresses two issues that arise in ordinal mechanism design. To design social welfare maximizing mechanisms, one needs to be able to quantitatively measure the welfare of an outcome which is not clear in the ordinal setting. Second, since the impossibility results of Gibbard and Satterthwaite Gibbard73,Satterthwaite75 force one to move to randomized mechanisms, one needs a more nuanced notion of truthfulness. We propose rank approximation as a metric for measuring the quality of an outcome, which allows us to evaluate mechanisms based on worst-case performance, and lex-truthfulness as a notion of truthfulness for randomized ordinal mechanisms. Lex-truthfulness is stronger than notions studied in the literature, and yet flexible enough to admit a rich class of mechanisms circumventing classical impossibility results . We demonstrate the usefulness of the above notions by devising lex-truthful mechanisms achieving good rank-approximation factors, both in the general ordinal setting, as well as structured settings such as (one-sided) matching markets , and its generalizations, matroid and scheduling markets. Matching markets have historically been an important topic in economics research. On the positive (descriptive) side, researchers have modeled everything ranging from marriage markets to labor markets using the framework of matching. Matching was also one of the first areas in which market design made a name for itself, perhaps most famously in the redesign of the market that matches graduating M.D.s to their first residency programs in the United States. The arrival of computer scientists to the field of market design in general can be traced to many of the reasons suggested recently by Conitzer [2010] (in a broader context than just market design) in an article in Communications of the ACM, including the effects of new markets that have been made possible by advances in networking and Internet technology, a more computational mindset in general, and also the ability to view problems from a different perspective. In the case of matching markets in particular, in addition to the (often) constructive nature of computational approaches, there is also the historical fact that computer scientists have studied matching from many different perspectives, perhaps because matching markets have a very natural representation in the language of graphs. Strategy-proof allocation of a finite number of indivisible goods among a finite number of individuals is considered. The main result is that in a pure distributional case, a mechanism is strategy-proof, nonbossy and neutral if and only if it is serially dictatorial. If the indivisible goods are initially owned by the individuals, a mechanism is strategy-proof, individually rational and Pareto consistent if and only if it is the core mechanism.