skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Approximately Optimal Mechanism Design
The field of optimal mechanism design enjoys a beautiful and well-developed theory, as well as several 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 article reviews several common issues with optimal mechanisms, including exorbitant communication, computation, and informational requirements; it also presents several examples demonstrating that relaxing the goal to designing an approximately optimal mechanism allows us to reason about fundamental questions that seem out of reach of the traditional theory.  more » « less
Award ID(s):
1929788
PAR ID:
10149860
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Annual Review of Economics
Volume:
11
Issue:
1
ISSN:
1941-1383
Page Range / eLocation ID:
355 to 381
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Guruswami, Venkatesan (Ed.)
    Transaction fee mechanism design is a new decentralized mechanism design problem where users bid for space on the blockchain. Several recent works showed that the transaction fee mechanism design fundamentally departs from classical mechanism design. They then systematically explored the mathematical landscape of this new decentralized mechanism design problem in two settings: in the plain setting where no cryptography is employed, and in a cryptography-assisted setting where the rules of the mechanism are enforced by a multi-party computation protocol. Unfortunately, in both settings, prior works showed that if we want the mechanism to incentivize honest behavior for both users as well as miners (possibly colluding with users), then the miner revenue has to be zero. Although adopting a relaxed, approximate notion of incentive compatibility gets around this zero miner-revenue limitation, the scaling of the miner revenue is nonetheless poor. In this paper, we show that if we make a mild reasonable-world assumption that there are sufficiently many honest users, we can circumvent the known limitations on miner revenue, and design auctions that generate asymptotically optimal miner revenue. We also systematically explore the mathematical landscape of transaction fee mechanism design under the new reasonable-world assumptions, and demonstrate how such assumptions can alter the feasibility and infeasibility landscape. 
    more » « less
  2. ; ; ; ; (, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence)
    In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of research in artificial intelligence, called solution diversity, has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space.When combined with techniques from parameterized complexity theory, the paradigm of diversity of solutions offers a powerful algorithmic framework to address problems of practical relevance. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation, a well-studied class of problems lying in the intersection of order theory and social choice theory and also in the field of order theory itself. In particular, we show that KRA is fixed-parameter tractable with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.< 
    more » « less
  3. ; ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    null (Ed.)
    The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack, and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging. 
    more » « less
  4. ; ; (, International Conference on Artificial Intelligence and Statistics)
    We present a new framework to analyze accelerated stochastic mirror descent through the lens of continuous-time stochastic dynamic systems. It enables us to design new algorithms, and perform a unified and simple analysis of the convergence rates of these algorithms. More specifically, under this framework, we provide a Lyapunov function based analysis for the continuous-time stochastic dynamics, as well as several new discrete-time algorithms derived from the continuous-time dynamics. We show that for general convex objective functions, the derived discrete-time algorithms attain the optimal convergence rate. Empirical experiments corroborate our theory. 
    more » « less
  5. ; ; ; (, TEI '21: Proceedings of the Fifteenth International Conference on Tangible, Embedded, and Embodied Interaction)
    null (Ed.)
    E-textiles, which embed circuitry into textile fabrics, blend art and creative expression with engineering, making it a popular choice for STEAM classrooms [6, 12]. Currently, e-textile development relies on tools intended for traditional embedded systems, which utilize printed circuit boards and insulated wires. These tools do not translate well to e-textiles, which utilize fabric and uninsulated conductive thread. This mismatch of tools and materials can lead to an overly complicated development process for novices. In particular, rapid prototyping tools for traditional embedded systems are poorly matched for e-textile prototyping. This paper presents the ThreadBoard, a tool that supports rapid prototyping of e-textile circuits. With rapid prototyping, students can test circuit designs and identify circuitry errors prior to their sewn project. We present the design process used to iteratively create the ThreadBoard’s layout, with the goal of improving its usability for e-textile creators. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email