Abstract: We initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple different mechanisms simultaneously or sequentially. We define the class of smooth mechanisms, related to smooth games defined by Roughgarden, that can be thought of as mechanisms that generate approximately market clearing prices. We show that smooth mechanisms result in high quality outcome in equilibrium both in the full information setting and in the Bayesian setting with uncertainty about participants, as well as in learning outcomes. Our main result is to show that such mechanisms compose well: smoothness locally at each mechanism implies efficiency globally. For mechanisms where good performance requires that bidders do not bid above their value, we identify the notion of a weakly smooth mechanism. Weakly smooth mechanisms, such as the Vickrey auction, are approximately efficient under the no-overbidding assumption. Similar to smooth mechanisms, weakly smooth mechanisms behave well in composition, and have high quality outcome in equilibrium (assuming no overbidding) both in the full information setting and in the Bayesian setting, as well as in learning outcomes. In most of the paper we assume participants have quasi-linear valuations. We also extend some of our results to settings where participants have budget constraints.
Recommendations
Cited in
(50)- A note on the efficiency of position mechanisms with budget constraints
- On the efficiency of all-pay mechanisms
- Simple combinatorial auctions with budget constraints
- Principal-agent VCG contracts
- Towards a characterization of worst case equilibria in the discriminatory price auction
- Learning in auctions: regret is hard, envy is easy
- Best-response dynamics in combinatorial auctions with item bidding
- Interconnected pay-as-bid auctions
- A unified and composable take on ratcheting
- Simultaneous auctions without complements are (almost) efficient
- Bounding the inefficiency of outcomes in generalized second price auctions
- Smooth multibidding mechanisms
- Item Pricing for Combinatorial Public Projects
- Limits of efficiency in sequential auctions
- Optimal cost-sharing in general resource selection games
- Correlated and Coarse Equilibria of Single-Item Auctions
- Smoothness for Simultaneous Composition of Mechanisms with Admission
- Approximating gains-from-trade in bilateral trading
- Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
- On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources
- On the efficiency of all-pay mechanisms
- Online submodular welfare maximization: greedy beats 1/2 in random order
- Algorithms as mechanisms: the price of anarchy of relax and round
- The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users
- Price of Anarchy for Mechanisms with Risk-Averse Agents
- Welfare guarantees for proportional allocations
- On the efficiency of the proportional allocation mechanism for divisible resources
- Capturing complementarity in set functions by going beyond submodularity/subadditivity
- Game efficiency through linear programming duality
- Expressiveness and robustness of first-price position auctions
- Item bidding for combinatorial public projects
- Equilibria of greedy combinatorial auctions
- An O(\log \log m) Prophet Inequality for Subadditive Combinatorial Auctions
- Multi-Item Nontruthful Auctions Achieve Good Revenue
- Mechanism design for perturbation stable combinatorial auctions
- Tight welfare guarantees for pure Nash equilibria of the uniform price auction
- Simultaneous 2nd price item auctions with no-underbidding
- Independent learning in stochastic games
- Robust implementation in general mechanisms
- Complexity of equilibria in first-price auctions under general tie-breaking rules
- Multi-agent contracts
- Polyhedral clinching auctions for indivisible goods
- Quantifying the inefficiency of multi-unit auctions for normal goods
- Competitive mechanisms for energy-efficient cloud computing
- First price auction is 1-1/e^2 efficient
- The price of anarchy of strategic queuing systems
- Multi-agent contracts
- Title not available (Why is no real title available?)
- Uniform price auctions: equilibria and efficiency
- Inefficiency of games with social context
This page was built for publication: Composable and efficient mechanisms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495791)
