Smoothness for Simultaneous Composition of Mechanisms with Admission

DOI10.1007/978-3-662-54110-4_21MaRDI QIDQ2959837zbMATH OpenOpenAlexFDO

Authors Martin Hoefer, Thomas Kesselheim, Bojana Kodric

Publication date 10 February 2017

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.00337

zbMATH Keywords

learningrepeated gamesocial welfare

Mathematics Subject Classification ID

Multistage and repeated games (91A20) Rationality and learning in game theory (91A26) Welfare economics (91B15)

Abstract: We study social welfare of learning outcomes in mechanisms with admission. In our repeated game there are $n$ bidders and $m$ mechanisms, and in each round each mechanism is available for each bidder only with a certain probability. Our scenario is an elementary case of simple mechanism design with incomplete information, where availabilities are bidder types. It captures natural applications in online markets with limited supply and can be used to model access of unreliable channels in wireless networks. If mechanisms satisfy a smoothness guarantee, existing results show that learning outcomes recover a significant fraction of the optimal social welfare. These approaches, however, have serious drawbacks in terms of plausibility and computational complexity. Also, the guarantees apply only when availabilities are stochastically independent among bidders. In contrast, we propose an alternative approach where each bidder uses a single no-regret learning algorithm and applies it in all rounds. This results in what we call availability-oblivious coarse correlated equilibria. It exponentially decreases the learning burden, simplifies implementation (e.g., as a method for channel access in wireless devices), and thereby addresses some of the concerns about Bayes-Nash equilibria and learning outcomes in Bayesian settings. Our main results are general composition theorems for smooth mechanisms when valuation functions of bidders are lattice-submodular. They rely on an interesting connection to the notion of correlation gap of submodular functions over product lattices.

Recommendations

• Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
• Smooth multibidding mechanisms
• Smoothing approach to Nash equilibrium formulations for a class of equilibrium problems with shared complementarity constraints
• Smooth equilibrium measures and approximation
• Smoothing techniques for computing Nash equilibria of sequential games
• Approximation in mechanism design with interdependent values
• Multiplicity of mixed equilibria in mechanisms: a unified approach to exact and approximate implementation
• Aggregation of smooth preferences
• Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
• Approximation techniques for utilitarian mechanism design

Cites work

• Bayesian Combinatorial Auctions
• Bounding the inefficiency of outcomes in generalized second price auctions
• Composable and efficient mechanisms
• Correlation robust stochastic optimization
• scientific article; zbMATH DE number 6783427 (Why is no real title available?)
• Learning and Efficiency in Games with Dynamic Population
• Learning, regret minimization, and equilibria
• On the complexity of computing an equilibrium in combinatorial auctions
• Price of anarchy for greedy auctions
• Simultaneous auctions are (almost) efficient
• Smoothness for Simultaneous Composition of Mechanisms with Admission
• Welfare guarantees for combinatorial auctions with item bidding

Cited in

(2)

• Smoothness for Simultaneous Composition of Mechanisms with Admission
• Composable and efficient mechanisms

This page was built for publication: Smoothness for Simultaneous Composition of Mechanisms with Admission

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959837)