On revenue equivalence in truthful mechanisms.
0
Citation
11
Reference
20
Related Paper
Abstract:
Introduction. In distributed systems, where problem solutions have to be jointly derived by several selfish agents and where problem data is spread over the agents as private information, mechanism design is used to motivate agents to reveal their private information truthfully and to obtain a good overall solution for the system. As a simple example, consider single item auctions, where several bidders are asked to reveal their valuation for a certain good. Dependent on the bids, the mechanism allocates the good to one of the bidders and the price of the good is designed such that agents have an incentive to bid their true valuation. We consider direct revelation mechanisms, which consist of an allocation rule that selects an allocation depending on the agents’ reports about their private information, and a payment scheme that assigns a payment to every agent. Allocation rules that give rise to a mechanism in which truth-telling is a dominant strategy for every agent are called truthfully implementable. Our concern is with the payment scheme that extends a truthfully implementable allocation rule to a truthful mechanism. The property of an allocation rule to have a unique payment scheme completing the allocation rule to a truthful mechanism is called revenue equivalence. We give a characterization for an allocation rule to satisfy revenue equivalence. In order to obtain this characterization, we prove a property on complete directed graphs and apply it to the so called allocation graph, which is defined by the allocation rule and the valuation function of an agent. The characterization holds for any (possibly infinite) outcome space. Furthermore, we give elementary and simple proofs for the uniqueness of the payment scheme in a truthful mechanism for the cases of finite and countably infinite outcome spaces under very weak assumptions. Many of the known results follow as immediate consequences of ours, e.g. results in Green and Laffont [2], Holmstrom [4], Krishna and Maenner [5], Milgrom and Segal [6], Suijs [10] and Chung and Olszewski [1]. For details and discussions, especially of the paper by Chung and Olszewski, we refer to the full version ofKeywords:
Incentive compatibility
Mechanism Design
Combinatorial auction
Private information retrieval
Cite
We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, which is closely related to Nash bargaining and the competitive equilibrium, is known to be not implementable in a truthful fashion, which has been its main drawback. To alleviate this issue, we propose a new mechanism, which we call the Partial Allocation mechanism, that discards a carefully chosen fraction of the allocated resources in order to incentivize the agents to be truthful in reporting their valuations. This mechanism introduces a way to implement interesting truthful outcomes in settings where monetary payments are not an option.
Mechanism Design
Fair division
Bargaining problem
Strategic dominance
Cite
Citations (72)
Combinatorial auction
Counterexample
Submodular set function
Cite
Citations (10)
We study online auction settings in which agents arrive and depart dynamically in a random (secretary) order, and each agent's private type consists of the agent's arrival and departure times, value and budget. We consider multi-unit auctions with additive agents for the allocation of both divisible and indivisible items. For both settings, we devise truthful mechanisms that give a constant approximation with respect to the auctioneer's revenue, under a large market assumption. For divisible items, we devise in addition a truthful mechanism that gives a constant approximation with respect to the liquid welfare --- a natural efficiency measure for budgeted settings introduced by Dobzinski and Paes Leme [ICALP'14]. Our techniques provide high-level principles for transforming offline truthful mechanisms into online ones, with or without budget constraints. To the best of our knowledge, this is the first work that addresses the non-trivial challenge of combining online settings with budgeted agents.
Constant (computer programming)
Mechanism Design
Value (mathematics)
Private information retrieval
Budget constraint
Combinatorial auction
Cite
Citations (0)
In this paper, we study payment rules for core-selecting combinatorial auctions (CAs). Day and Raghavan [11] have argued that the core provides a fairness guarantee in that the winners’ payments will be at least as high as the sum of the bids of any other coalition of bidders. However, we argue that the core primarily provides a fairness guarantee to losing bidders and says little about how payoffs are distributed among the winners. To address this, we propose an additional notion of fairness that goes beyond the core. We consider the fact that auction participants are often heterogeneous in size and value, and we study the distribution of winners’ payoffs; specifically, we define a Gini coefficient for CA payment rules by which we can then compare different rules. We find that the most common payment rule that has been used in practice, the Quadratic rule [10], is unfair towards small players participating in the auction. In contrast to prior work, which has only studied the Quadratic rule in stylized settings, we use computational methods to study approximate Bayes-Nash equilibria of payment rules in more complex settings. We develop a novel framework for the study of core-selecting payment rules and then use it to design alternative, fairer rules that improve upon the Quadratic rule while retaining its high efficiency. Our new rules involve novel bidder weightings, and new distance metrics to VCG prices. To find a payment rule that strikes an optimal trade-off between all design objectives (efficiency, core, fairness, revenue, and incentives), we have evaluated 85 different payment rules via our computational Bayes-Nash equilibrium analysis.
Stylized fact
Cite
Citations (0)
Mechanism design seeks algorithms whose inputs are provided by selfish agents who would lie if advantageous. Incentive compatible mechanisms compel the agents to tell the truth by making it in their self-interest to do so. Often, as in combinatorial auctions, such mechanisms involve the solution of NP-hard problems. Unfortunately, approximation algorithms typically destroy incentive compatibility. Randomized rounding is a commonly used technique for designing approximation algorithms. We devise a version of randomized rounding that is incentive compatible, giving a truthful mechanism for combinatorial auctions with parameter agents (e.g., single minded bidders) that approximately maximizes the social value of the auction. We discuss two orthogonal notions of truthfulness for a randomized mechanism, truthfulness with high probability and in expectation, and give a mechanism that achieves both simultaneously.We consider combinatorial auctions where multiple copies of many different items are on sale, and each bidder i desires a subset Si. Given a set of bids, the problem of finding the allocation of items that maximizes total valuation is the well-known SETPACKING problem. This problem is NP-hard, but for the case of items with many identical copies the optimum can be approximated very well. To turn this approximation algorithm into a truthful auction mechanism we overcome two problems: we show how to make the allocation algorithm monotone, and give a method to compute the appropriate payments efficiently.
Combinatorial auction
Incentive compatibility
Rounding
Randomized rounding
Mechanism Design
Submodular set function
Randomized Algorithm
Cite
Citations (133)
Mechanism design studies the implementation of allocation functions (sometimes called social choice functions) when relevant information resides with self-interested agents who may misreport their information if it is rational to do so. A central question in the field is to characterize which allocation functions are truthful, meaning that they can be combined with a payment function that induces players to report their preferences truthfully. Characterization theorems for truthful mechanisms, when they exist, are a boon to the mechanism designer since they allow us to reduce problems of optimal mechanism design to algorithm design problems in which the algorithm that computes the allocation function is required to satisfy additional constraints.
Mechanism Design
Submodular set function
Cite
Citations (10)
We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, which is closely related to Nash bargaining and the competitive equilibrium, is known to be not implementable in a truthful fashion, which has been its main drawback. To alleviate this issue, we propose a new mechanism, which we call the Partial Allocation mechanism, that discards a carefully chosen fraction of the allocated resources in order to incentivize the agents to be truthful in reporting their valuations. This mechanism introduces a way to implement interesting truthful outcomes in settings where monetary payments are not an option.
Mechanism Design
Fair division
Bargaining problem
Strategic dominance
Cite
Citations (28)
We study the problem of selling identical items to n unit-demand bidders in a setting in which the total supply of items is unknown to the mechanism. Items arrive dynamically, and the seller must make the allocation and payment decisions online with the goal of maximizing social welfare. We consider two models of unknown supply: the adversarial supply model, in which the mechanism must produce a welfare guarantee for any arbitrary supply, and the stochastic supply model, in which supply is drawn from a distribution known to the mechanism, and the mechanism need only provide a welfare guarantee in expectation.
Cite
Citations (28)
Incentive compatibility
Mechanism Design
Private information retrieval
Cite
Citations (1)
This manuscript presents an alternative implementation of the truthful-in-expectation mechanism of Dughmi, Roughgarden and Yan for combinatorial auctions with weighted-matroid-rank-sum valuations. The new implementation uses only value queries and is approximately truthful-in-expectation, in the sense that by reporting truthfully each agent maximizes his utility within a multiplicative 1-o(1) factor. It still provides an optimal (1-1/e-o(1))-approximation in social welfare. We achieve this by first presenting an approximately maximal-in-distributional-range allocation rule and then showing a black-box transformation to an approximately truthful-in-expectation mechanism.
Combinatorial auction
Mechanism Design
Value (mathematics)
Rank (graph theory)
Cite
Citations (13)