Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximately Optimal Mechanism Design
82
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Optimal mechanism design enjoys a beautiful and well-developed theory, and also a number of killer applications. Rules of thumb produced by the field influence everything from how governments sell wireless spectrum licenses to how the major search engines auction off online advertising. There are, however, some basic problems for which the traditional optimal mechanism design approach is ill-suited---either because it makes overly strong assumptions, or because it advocates overly complex designs. This survey reviews several common issues with optimal mechanisms, including exorbitant communication, computation, and informational requirements; and it presents several examples demonstrating that passing to the relaxed goal of an approximately optimal mechanism allows us to reason about fundamental questions that seem out of reach of the traditional theory.
rate research
Read More
We show the role that an important equation first studied by Fritz John plays in mechanism design.
Army cadets obtain occupations through a centralized process. Three objectives -- increasing retention, aligning talent, and enhancing trust -- have guided reforms to this process since 2006. West Points mechanism for the Class of 2020 exacerbated challenges implementing Army policy aims. We formulate these desiderata as axioms and study their implications theoretically and with administrative data. We show that the Armys objectives not only determine an allocation mechanism, but also a specific priority policy, a uniqueness result that integrates mechanism and priority design. These results led to a re-design of the mechanism, now adopted at both West Point and ROTC.
We consider a revenue-maximizing seller with $m$ heterogeneous items and a single buyer whose valuation $v$ for the items may exhibit both substitutes (i.e., for some $S, T$, $v(S cup T) < v(S) + v(T)$) and complements (i.e., for some $S, T$, $v(S cup T) > v(S) + v(T)$). We show that the mechanism first proposed by Babaioff et al. [2014] - the better of selling the items separately and bundling them together - guarantees a $Theta(d)$ fraction of the optimal revenue, where $d$ is a measure on the degree of complementarity. Note that this is the first approximately optimal mechanism for a buyer whose valuation exhibits any kind of complementarity, and extends the work of Rubinstein and Weinberg [2015], which proved that the same simple mechanisms achieve a constant factor approximation when buyer valuations are subadditive, the most general class of complement-free valuations. Our proof is enabled by the recent duality framework developed in Cai et al. [2016], which we use to obtain a bound on the optimal revenue in this setting. Our main technical contributions are specialized to handle the intricacies of settings with complements, and include an algorithm for partitioning edges in a hypergraph. Even nailing down the right model and notion of degree of complementarity to obtain meaningful results is of interest, as the natural extensions of previous definitions provably fail.
We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function $g$ from the $n$-dimensional hypercube to the bounded interval $[-1,1]$, and an $n times m$ matrix $A$ with bounded entries, maximize $g(Ax)$ over $x$ in the $m$-dimensional simplex. This problem arises naturally when one seeks to design a lottery over items for sale in an auction, or craft the posterior beliefs for agents in a Bayesian game through the provision of information (a.k.a. signaling). We present an approximation algorithm for this problem when $g$ simultaneously satisfies two smoothness properties: Lipschitz continuity with respect to the $L^infty$ norm, and noise stability. The latter notion, which we define and cater to our setting, controls the degree to which low-probability errors in the inputs of $g$ can impact its output. When $g$ is both $O(1)$-Lipschitz continuous and $O(1)$-stable, we obtain an (additive) PTAS for mixture selection. We also show that neither assumption suffices by itself for an additive PTAS, and both assumptions together do not suffice for an additive FPTAS. We apply our algorithm to different game-theoretic applications from mechanism design and optimal signaling. We make progress on a number of open problems suggested in prior work by easily reducing them to mixture selection: we resolve an important special case of the small-menu lottery design problem posed by Dughmi, Han, and Nisan; we resolve the problem of revenue-maximizing signaling in Bayesian second-price auctions posed by Emek et al. and Miltersen and Sheffet; we design a quasipolynomial-time approximation scheme for the optimal signaling problem in normal form games suggested by Dughmi; and we design an approximation algorithm for the optimal signaling problem in the voting model of Alonso and C^{a}mara.
Motivated by online decision-making in time-varying combinatorial environments, we study the problem of transforming offline algorithms to their online counterparts. We focus on offline combinatorial problems that are amenable to a constant factor approximation using a greedy algorithm that is robust to local errors. For such problems, we provide a general framework that efficiently transforms offline robust greedy algorithms to online ones using Blackwell approachability. We show that the resulting online algorithms have $O(sqrt{T})$ (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a $O(T^{2/3})$ (approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue management, market design, and online optimization, including product ranking optimization in online platforms, reserve price optimization in auctions, and submodular maximization. We show that our transformation, when applied to these applications, leads to new regret bounds or improves the current known bounds.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
