The Experts below are selected from a list of 368220 Experts worldwide ranked by ideXlab platform
Matthew S Weinberg - One of the best experts on this subject based on the ideXlab platform.
-
a duality based unified approach to bayesian Mechanism Design
SIAM Journal on Computing, 2019Co-Authors: Yang Cai, Nikhil R Devanur, Matthew S WeinbergAbstract:We provide a unified view of many recent developments in Bayesian Mechanism Design, including the black-box reductions of Cai, Daskalakis, and Weinberg [in Proceedings of the 54th Annual IEEE Sympo...
-
a duality based unified approach to bayesian Mechanism Design
arXiv: Computer Science and Game Theory, 2018Co-Authors: Yang Cai, Nikhil R Devanur, Matthew S WeinbergAbstract:We provide a unified view of many recent developments in Bayesian Mechanism Design, including the black-box reductions of Cai et al. [CDW13b], simple auctions for additive buyers [HN12], and posted-price Mechanisms for unit-demand bidders [CHK07]. Additionally, we show that viewing these three previously disjoint lines of work through the same lens leads to new developments as well. First, we provide a duality framework for Bayesian Mechanism Design, which naturally accommodates multiple agents and arbitrary objectives/feasibility constraints. Using this, we prove that either a posted-price Mechanism or the Vickrey-Clarke-Groves auction with per-bidder entry fees achieves a constant-factor of the optimal revenue achievable by a Bayesian Incentive Compatible Mechanism whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et al. [CHMS10] and Yao [Yao15], and improving both approximation ratios (from 30 to 24 and 69 to 8, respectively). Finally, we show that this view also leads to improved structural characterizations in the Cai et al. framework.
-
a duality based unified approach to bayesian Mechanism Design
Symposium on the Theory of Computing, 2016Co-Authors: Yang Cai, Nikhil R Devanur, Matthew S WeinbergAbstract:We provide a unified view of many recent developments in Bayesian Mechanism Design, including the black-box reductions of Cai et. al., simple auctions for additive buyers, and posted-price Mechanisms for unit-demand buyers. Additionally, we show that viewing these three previously disjoint lines of work through the same lens leads to new developments as well. First, we provide a duality framework for Bayesian Mechanism Design, which naturally accommodates multiple agents and arbitrary objectives/feasibility constraints. Using this, we prove that either a posted-price Mechanism or the VCG auction with per-bidder entry fees achieves a constant-factor of the optimal Bayesian IC revenue whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et. al. and Yao, and improving both approximation ratios (from 33.75 to 24 and 69 to 8). Finally, we show that this view also leads to improved structural characterizations in the Cai et. al. framework.
-
understanding incentives Mechanism Design becomes algorithm Design
Foundations of Computer Science, 2013Co-Authors: Constantinos Daskalakis, Matthew S WeinbergAbstract:We provide a computationally efficient black-box reduction from Mechanism Design to algorithm Design in very general settings. Specifically, we give an approximation-preserving reduction from truthfully maximizing any objective under arbitrary feasibility constraints with arbitrary bidder types to (not necessarily truthfully) maximizing the same objective plus virtual welfare (under the same feasibility constraints). Our reduction is based on a fundamentally new approach: we describe a Mechanism's behavior indirectly only in terms of the expected value it awards bidders for certain behavior, and never directly access the allocation rule at all. Applying our new approach to revenue, we exhibit settings where our reduction holds both ways. That is, we also provide an approximation-sensitive reduction from (non-truthfully) maximizing virtual welfare to (truthfully) maximizing revenue, and therefore the two problems are computationally equivalent. With this equivalence in hand, we show that both problems are NP-hard to approximate within any polynomial factor, even for a single monotone sub modular bidder. We further demonstrate the applicability of our reduction by providing a truthful Mechanism maximizing fractional max-min fairness.
Felix Bierbrauer - One of the best experts on this subject based on the ideXlab platform.
-
public good provision Mechanism Design and voting
Research Papers in Economics, 2015Co-Authors: Felix Bierbrauer, Martin HellwigAbstract:We study the relation between Mechanism Design and voting in public-good provision. If incentive Mechanisms must satisfy conditions of coalition-proofness and robustness, as well as individual incentive compatibility, the participants' contributions to public-good provision can only depend on the level of the public good that is provided and that level can only depend on the population shares of people favouring one level over another. For a public good that comes as a single indivisible unit the outcome depends on whether or not the share of votes in favour of provision exceeds a speci ed threshold. With more provision levels for the public good more complicated Mechanisms can be used but they still involve the counting of votes rather than any measurement of the participants' willingness to pay. The paper thus provides a foundation for the use of voting Mechanisms.
-
a note on optimal income taxation public goods provision and robust Mechanism Design
Journal of Public Economics, 2009Co-Authors: Felix BierbrauerAbstract:Abstract This paper extends the model of optimal income taxation due to Mirrlees (Mirrlees, J., 1971. An exploration in the theory of optimum income taxation. Review of Economic Studies 38, 175–208) and includes private information on public goods preferences. A Mechanism Design approach is used to establish the following result: If policies are required to be robustly implementable in the sense of Bergemann and Morris (Bergemann, D., Morris, S., 2005. Robust Mechanism Design. Econometrica 73, 1771–1813), then the optimality conditions in the extended model with uncertainty about tax and expenditure policies are the same as in the standard model of optimal income taxation. The paper provides a foundation for a widely-used assumption in public finance, namely that individuals optimize their behavior subject to a predetermined and commonly known tax system.
Annamaria Kovacs - One of the best experts on this subject based on the ideXlab platform.
-
Mechanism Design for fractional scheduling on unrelated machines
ACM Transactions on Algorithms, 2010Co-Authors: George Christodoulou, Elias Koutsoupias, Annamaria KovacsAbstract:Scheduling on unrelated machines is one of the most general and classical variants of the task scheduling problem. Fractional scheduling is the LP-relaxation of the problem, which is polynomially solvable in the nonstrategic setting, and is a useful tool to Design deterministic and randomized approximation algorithms. The Mechanism Design version of the scheduling problem was introduced by Nisan and Ronen. In this article, we consider the Mechanism Design version of the fractional variant of this problem. We give lower bounds for any fractional truthful Mechanism. Our lower bounds also hold for any (randomized) Mechanism for the integral case. In the positive direction, we propose a truthful Mechanism that achieves approximation 3/2 for 2 machines, matching the lower bound. This is the first new tight bound on the approximation ratio of this problem, after the tight bound of 2, for 2 machines, obtained by Nisan and Ronen. For n machines, our Mechanism achieves an approximation ratio of n+1/2. Motivated by the fact that all the known deterministic and randomized Mechanisms for the problem assign each task independently from the others, we focus on an interesting subclass of allocation algorithms, the task-independent algorithms. We give a lower bound of n+1/2, that holds for every (not only monotone) allocation algorithm that takes independent decisions. Under this consideration, our truthful independent Mechanism is the best that we can hope from this family of algorithms.
-
Mechanism Design for fractional scheduling on unrelated machines
International Colloquium on Automata Languages and Programming, 2007Co-Authors: George Christodoulou, Elias Koutsoupias, Annamaria KovacsAbstract:In this paper, we consider the Mechanism Design version of the fractional variant of the scheduling problem on unrelated machines. We give a lower bound of 2-1/n for any fractional truthful Mechanism, while we propose a truthful Mechanism that achieves approximation of 1 + (n - 1)/2, for n machines. We also focus on an interesting family of allocation algorithms, the task-independent algorithms. We give a lower bound of 1 + (n - 1)/2, that holds for every (not only monotone) allocation algorithm of this class. Under this consideration, our truthful independent Mechanism is the best that we can hope from this family of algorithms.
Jason D Hartline - One of the best experts on this subject based on the ideXlab platform.
-
bernoulli factories and black box reductions in Mechanism Design
Journal of the ACM, 2021Co-Authors: Shaddin Dughmi, Robert Kleinberg, Jason D Hartline, Rad NiazadehAbstract:We provide a polynomial time reduction from Bayesian incentive compatible Mechanism Design to Bayesian algorithm Design for welfare maximization problems. Unlike prior results, our reduction achiev...
-
bernoulli factories and black box reductions in Mechanism Design
Sigecom Exchanges, 2017Co-Authors: Shaddin Dughmi, Robert Kleinberg, Jason D Hartline, Rad NiazadehAbstract:In this letter, we report on our work providing a polynomial time reduction from Bayesian incentive compatible Mechanism Design to Bayesian algorithm Design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with multidimensional and continuous type spaces.
-
Mechanism Design for data science
arXiv: Computer Science and Game Theory, 2014Co-Authors: Shuchi Chawla, Jason D Hartline, Denis NekipelovAbstract:Good economic Mechanisms depend on the preferences of participants in the Mechanism. For example, the revenue-optimal auction for selling an item is parameterized by a reserve price, and the appropriate reserve price depends on how much the bidders are willing to pay. A Mechanism Designer can potentially learn about the participants' preferences by observing historical data from the Mechanism; the Designer could then update the Mechanism in response to learned preferences to improve its performance. The challenge of such an approach is that the data corresponds to the actions of the participants and not their preferences. Preferences can potentially be inferred from actions but the degree of inference possible depends on the Mechanism. In the optimal auction example, it is impossible to learn anything about preferences of bidders who are not willing to pay the reserve price. These bidders will not cast bids in the auction and, from historical bid data, the auctioneer could never learn that lowering the reserve price would give a higher revenue (even if it would). To address this impossibility, the auctioneer could sacrifice revenue optimality in the initial auction to obtain better inference properties so that the auction's parameters can be adapted to changing preferences in the future. This paper develops the theory for optimal Mechanism Design subject to good inferability.
-
multi parameter Mechanism Design and sequential posted pricing
Symposium on the Theory of Computing, 2010Co-Authors: Shuchi Chawla, Jason D Hartline, David Malec, Balasubramanian SivanAbstract:We study the classic mathematical economics problem of Bayesian optimal Mechanism Design where a principal aims to optimize expected revenue when allocating resources to self-interested agents with preferences drawn from a known distribution. In single parameter settings (i.e., where each agent's preference is given by a single private value for being served and zero for not being served) this problem is solved [20]. Unfortunately, these single parameter optimal Mechanisms are impractical and rarely employed [1], and furthermore the underlying economic theory fails to generalize to the important, relevant, and unsolved multi-dimensional setting (i.e., where each agent's preference is given by multiple values for each of the multiple services available) [25]. In contrast to the theory of optimal Mechanisms we develop a theory of sequential posted price Mechanisms, where agents in sequence are offered take-it-or-leave-it prices. We prove that these Mechanisms are approximately optimal in single-dimensional settings. These posted-price Mechanisms avoid many of the properties of optimal Mechanisms that make the latter impractical. Furthermore, these Mechanisms generalize naturally to multi-dimensional settings where they give the first known approximations to the elusive optimal multi-dimensional Mechanism Design problem. In particular, we solve multi-dimensional multi-unit auction problems and generalizations to matroid feasibility constraints. The constant approximations we obtain range from 1.5 to 8. For all but one case, our posted price sequences can be computed in polynomial time. This work can be viewed as an extension and improvement of the single-agent algorithmic pricing work of [9] to the setting of multiple agents where the Designer has combinatorial feasibility constraints on which agents can simultaneously obtain each service.
-
multi parameter Mechanism Design and sequential posted pricing
Behavioral and Quantitative Game Theory on Conference on Future Directions, 2010Co-Authors: Shuchi Chawla, Jason D Hartline, David Malec, Balasubramanian SivanAbstract:We consider the classical mathematical economics problem of Bayesian optimal Mechanism Design where a principal aims to optimize expected revenue when allocating resources to self-interested agents with preferences drawn from a known distribution. In single-parameter settings (i.e., where each agent's preference is given by a single private value for being served and zero for not being served) this problem is solved. Unfortunately, these single parameter optimal Mechanisms are impractical and rarely employed, and furthermore the underlying economic theory fails to generalize to the important, relevant, and unsolved multi-dimensional setting (i.e., where each agent's preference is given by multiple values for each of the multiple services available). In contrast to the theory of optimal Mechanisms we develop a theory of sequential posted price Mechanisms, where agents in sequence are offered take-it-or-leave-it prices. We prove that these Mechanisms are approximately optimal in single-dimensional settings. These posted-price Mechanisms avoid many of the properties of optimal Mechanisms that make the latter impractical. Furthermore, these Mechanisms generalize naturally to multidimensional settings where they give the first known approximations to the elusive optimal multi-dimensional Mechanism Design problem.
Dirk Bergemann - One of the best experts on this subject based on the ideXlab platform.
-
dynamic Mechanism Design an introduction
Journal of Economic Literature, 2019Co-Authors: Dirk Bergemann, Juuso ValimakiAbstract:We provide an introduction to the recent developments of dynamic Mechanism Design, with a primary focus on the quasilinear case. First, we describe socially optimal (or efficient) dynamic Mechanisms. These Mechanisms extend the well-known Vickrey–Clark–Groves and D'Aspremont–Gerard–Varet Mechanisms to a dynamic environment. Second, we discuss revenue optimal Mechanisms. We cover models of sequential screening and revenue-maximizing auctions with dynamically changing bidder types. We also discuss models of information management where the Mechanism Designer can control (at least partially) the stochastic process governing the agents' types. Third, we consider models with changing populations of agents over time. After discussing related models with risk-averse agents and limited liability, we conclude with a number of open questions and challenges that remain for the theory of dynamic Mechanism Design.
-
dynamic Mechanism Design an introduction
Social Science Research Network, 2017Co-Authors: Dirk Bergemann, Juuso ValimakiAbstract:We provide an introduction into the recent developments of dynamic Mechanism Design with a primary focus on the quasilinear case. First, we describe socially optimal (or efficient) dynamic Mechanisms. These Mechanisms extend the well known Vickrey-Clark-Groves and D’Aspremont-Gerard-Varet Mechanisms to a dynamic environment. Second, we discuss results on revenue optimal Mechanism. We cover models of sequential screening and revenue maximizing auctions with dynamically changing bidder types. We also discuss models of information management where the Mechanism Designer can control (at least partially) the stochastic process governing the agent’s types. Third, we consider models with changing populations of agents over time. This allows us to address new issues relating to the properties of payment rules. After discussing related models with risk-averse agents, limited liability, and different performance criteria for the Mechanisms, we conclude by discussing a number of open questions and challenges that remain for the theory of dynamic Mechanism Design.
-
robust Mechanism Design
Econometrica, 2005Co-Authors: Dirk Bergemann, Stephen MorrisAbstract:The Mechanism Design literature assumes too much common knowledge of the environment among the players and planner. We relax this assumption by studying implementation on richer type spaces, with more higher order uncertainty. We study the "ex post equivalence" question: when is interim implementation on all possible type spaces equivalent to requiring ex post implementation on the
-
robust Mechanism Design
Econometrica, 2005Co-Authors: Dirk Bergemann, Stephen MorrisAbstract:The Mechanism Design literature assumes too much common knowledge of the environment among the players and planner. We relax this assumption by studying implementation on richer type spaces, with more higher order uncertainty. We study the "ex post equivalence" question: When is interim implementation on all possible type spaces equivalent to requiring ex post implementation on the space of payoff types? We show that ex post equivalence holds when the social choice correspondence is a function and in simple quasi-linear environments. When ex post equivalence holds, we identify how large the type space must be to obtain the equivalence. We also show that ex post equivalence fails in general, including in quasi-linear environments with budget balance. For quasi-linear environments, we provide an exact characterization of when interim implementation is possible in rich type spaces. In this environment, the planner can fully extract players' belief types, so the incentive constraints reduce to conditions distinguishing types with the same beliefs about others' types but different payoff types.
-
robust Mechanism Design
Levine's Bibliography, 2003Co-Authors: Dirk Bergemann, Stephen MorrisAbstract:The Mechanism Design literature assumes too much common knowledge of the environment among the players and planner. We relax this assumption by studying implementation on richer type spaces, with more higher order uncertainty. We study the "ex post equivalence" question: When is interim implementation on all possible type spaces equivalent to requiring ex post implementation on the space of payoff types? We show that ex post equivalence holds when the social choice correspondence is a function and in simple quasi-linear environments. When ex post equivalence holds, we identify how large the type space must be to obtain the equivalence. We also show that ex post equivalence fails in general, including in quasi-linear environments with budget balance. For quasi-linear environments, we provide an exact characterization of when interim implementation is possible in rich type spaces. In this environment, the planner can fully extract players' belief types, so the incentive constraints reduce to conditions distinguishing types with the same beliefs about others' types but different payoff types.(This abstract was borrowed from another version of this item.)
