This website uses cookies.

By clicking the "Accept" button or continuing to browse our site, you agree to first-party and session-only cookies being stored on your device to enhance site navigation and analyze site performance and traffic. For more information on our use of cookies, please see our Privacy Policy.

  1. Home
  2. ASSA Annual Meeting
  3. 2023
  4. Program
  5. Advances in Mechanism Design
« Back to Results

Advances in Mechanism Design

Paper Session

Sunday, Jan. 8, 2023 1:00 PM - 3:00 PM (CST)

Hilton Riverside, Norwich
Hosted By: Econometric Society
  • Chair: Xianwen Shi, University of Toronto

Zero-Knowledge Mechanisms

Ran Canetti
,
Boston University
Amos Fiat
,
Tel Aviv University
Yannai A. Gonczarowski
,
Harvard University

Abstract

In a mechanism design setting (with private information and/or private actions), the mechanism designer chooses a mechanism to optimize some target function, and announces the mechanism. The fact that the mechanism is an "open book" incentivizes agents to participate: by inspection, they can verify properties of interest, such as incentive compatibility and individual rationality. However, inspecting the mechanism might also have the side effect of revealing to the agents—whether explicitly or implicitly—information that the mechanism designer may have actually preferred to conceal, such as her target function, or her private costs. Such information being revealed might have real cost (exogenous or endogenous) to the mechanism designer. Transparency, therefore, may turn out to be a double-edged sword. Using cryptographic tools such as zero-knowledge proofs, we present a general technique for a mechanism designer to endogenously commit to an undisclosed mechanism, while still proving its properties of interest, such as incentive compatibility and individual rationality, to agents, and at the end of the day proving that the mechanism was indeed run as planned, including that any random draws performed by the mechanism were fair. In a precise sense, agents learn nothing more about the mechanism than its outcome, and in fact, only its realized outcome if the mechanism is randomized. Preliminary applications include bargaining, negotiations, ad auctions, and more. Finally, using ideas from prior literature on cryptographic hiding of bids in auctions, we also present an extension that allows both the mechanism and the bids to remain private, in the form of a general *un*revelation principle, opening the door for a new layer of mechanism customization that we call "revelation design." (No prior knowledge in cryptography will be assumed in the presentation.)

Greedy Allocations and Equitable Matchings

Quitze Valenzuela-Stookey
,
University of California-Berkeley

Abstract

I provide a novel approach to characterizing the set of interim realizable allocations, in the spirit of Matthews (1984) and Border (1991). The approach allows me to identify precisely why exact characterizations are difficult to obtain in some settings. The main results of the paper then show how to adapt the approach in order to obtain approximate characterizations of the interim realizable set in such settings.

As an application, I study multi-item allocation problems when agents have capacity constraints. I identify necessary conditions for interim realizability, and show that these conditions are sufficient for realizability when the interim allocation in question is scaled by 1/2. I then characterize a subset of the realizable polytope which contains all such scaled allocations. This polytope is generated by a majorization relationship between the scaled interim allocations and allocations induced by a certain "greedy algorithm". I use these results to study mechanism design with equity concerns and model ambiguity. I also relate optimal mechanisms to the commonly used deferred acceptance and serial dictatorship matching algorithms. For example, I provide conditions on the principal's objective such that by carefully choosing school priorities and running deferred acceptance, the principal can guarantee at least half of the optimal (full information) payoff.

Mechanisms without Transfers for Fully Biased Agents

Deniz Kattwinkel
,
University College London
Axel Niemeyer
,
University of Bonn
Justus Preusser
,
University of Bonn
Alexander Winter
,
University of Bonn

Abstract

A principal must decide between two options. Which one she prefers depends on the private information of two agents. One agent always prefers the first option; the other always prefers the second. Transfers are infeasible. One application of this setting is the efficient division of a fixed budget between two competing departments. We first characterize all implementable mechanisms under arbitrary correlation. Second, we study when there exists a mechanism that yields the principal a higher payoff than she could receive by choosing the ex-ante optimal decision without consulting the agents. In the budget example, a profitable mechanism exists if and only if the information of one department is also relevant for the expected returns of the other department. When types are independent this result generalizes to a setting with n agents. We apply this insight to derive necessary and sufficient conditions for the existence of a profitable mechanism in the n-agent allocation problem.

Stochastic Sequential Screening

Hao Li
,
University of British Columbia
Xianwen Shi
,
University of Toronto

Abstract

We study when and how randomization can help improve the seller's revenue in the sequential screening setting. Using a model with discrete ex ante types and a continuum of ex post valuations, we demonstrate why the standard approach based on solving a relaxed problem that keeps only local downward incentive compatibility constraints often fails and show how randomization is needed to realize the full potential of sequential screening. Under a strengthening of first-order stochastic dominance ordering on the valuation distribution functions of ex ante types, we introduce and solve a modified relaxed problem by retaining all local incentive compatibility constraints, provide necessary and sufficient conditions for optimal mechanisms to be stochastic, and characterize optimal stochastic contracts. Our analysis mostly focuses on the case of three ex ante types, but our methodology of solving the modified problem can be extended to any finite number of ex ante types.
JEL Classifications
  • C7 - Game Theory and Bargaining Theory
  • D4 - Market Structure, Pricing, and Design