On the sufficiency of unidirectional incentive compatibility in auctions

This paper demonstrates that in optimal auction design, restricting bidders to only underbid their true values (unidirectional incentive compatibility) is sufficient to achieve the same maximum revenue as allowing unrestricted deviations, a result proven via linear programming duality in discrete models.

The Gist

Imagine you are hosting a silent auction for a single, rare item. You want to make as much money as possible, but you have a problem: the bidders know their own true value for the item, but you don't. They might try to trick you by lying about how much they want it.

Usually, in auction theory, we assume bidders can lie in two directions:

1. Underbidding: Saying "I only want this for $50" when they actually think it's worth $100 (to pay less).
2. Overbidding: Saying "I want this for $150" when they only think it's worth $100 (to try to win it, even though they might overpay).

Standard economic theory says you have to design your auction rules to stop bidders from lying in either direction. This is called "full incentive compatibility."

The Big Discovery
This paper, by Kiho Yoon, asks a fascinating question: What if we only had to worry about bidders trying to underbid? What if, for some reason, bidders were physically or legally unable to overbid (maybe they are too honest to pretend they want something they don't, or the rules prevent it)?

The paper's main finding is a surprising "magic trick" of economics: It doesn't matter.

Even if you design an auction assuming bidders could lie in both directions (underbid or overbid), the maximum amount of money you can make is exactly the same as if you designed it assuming they could only underbid.

In other words, stopping bidders from underbidding is enough to stop them from overbidding too. You don't need to build extra "fences" to stop overbidding; the fences you build to stop underbidding automatically do the job for both.

How the Author Proves It (The "Ironing" Analogy)
To prove this, the author uses a mathematical tool called "linear programming," which is like solving a giant puzzle with many constraints.

Think of the auction design like trying to build a smooth, sliding ramp for a ball (the bidder's value) to roll down.

• The Old Way (Myerson's Auction): You have to make sure the ramp is perfectly smooth and never goes up or down in a weird way (monotonicity). If the ramp dips, the ball might get stuck or roll backward, which represents a bidder lying.
• The New Way (This Paper): The author suggests a different way to look at the ramp. Instead of worrying about the shape of the ramp itself, they look at the "upper envelope" of the ramp. Imagine you have a piece of string stretched tight over the top of the ramp. If the ramp dips, the string bridges the gap.

The paper shows that if you design your auction based on this "tight string" (the upper envelope) to prevent bidders from underbidding, the math forces the ramp to be smooth enough that bidders can't overbid either. The "string" naturally fixes the bumps that would allow overbidding.

Why This Matters
Before this paper, economists knew this trick worked for a single bidder (like a solo seller dealing with one customer). But when you have many bidders competing against each other, the math gets incredibly messy because their bids affect each other.

This paper is the first to prove that this "unidirectional" trick (worrying only about underbidding) works perfectly even in a crowded room with many bidders. It simplifies the complex math of auction design, showing that the strict rules needed to prevent overbidding are actually redundant if you've already solved the underbidding problem.

In a Nutshell
If you build a lock that stops someone from stealing money from the bottom of the jar (underbidding), you don't need a second, separate lock to stop them from adding fake money to the top (overbidding). The first lock does both jobs automatically. This makes designing the perfect money-making auction much simpler than we thought.

Technical Summary

Technical Summary: On the Sufficiency of Unidirectional Incentive Compatibility in Auctions

Problem Statement
This paper investigates optimal auction design in a multi-agent environment where bidders possess private, independent, and discretely distributed valuations for a single indivisible object. The central question addresses the sufficiency of unidirectional incentive compatibility (UIC) compared to full (bidirectional) incentive compatibility (IC). Specifically, the author examines whether restricting bidders' deviations to only underbidding their true values (i.e., reporting a type lower than their actual type) is sufficient to achieve the same maximum expected revenue as allowing bidders to underbid or overbid freely.

While Moore (1984) established the sufficiency of downward constraints for a single risk-averse bidder with finite types, the extension to multi-agent environments remained an open question due to the complexities arising from the feasibility of allocation rules across multiple agents. This paper aims to resolve that open question.

Methodology
The analysis is conducted within a discrete model using linear programming (LP) duality. The methodology proceeds through the following steps:

1. Characterization of UIC: The paper first characterizes unidirectional incentive compatibility not through standard monotonicity constraints, but via the upper envelope of the allocation rule. Proposition 1 demonstrates that the UIC constraints are equivalent to a condition involving the cumulative sum of the upper envelope of the allocation probabilities.
2. Formulation of Primal Problems: Two revenue maximization problems are formulated as linear programs:
   • [P1]: Maximization under UIC constraints. The objective function incorporates an "upper envelope" term that accounts for the information rent conceded to higher-value bidders, effectively replacing the standard monotonicity constraint found in Myerson's (1981) framework.
   • [P2]: Maximization under full IC constraints. This is the standard formulation involving virtual valuations and explicit monotonicity constraints on the allocation rule.
3. Dual Analysis: The author constructs the dual programs, [D1] (dual to P1) and [D2] (dual to P2). By analyzing the structure of these duals—utilizing weak and strong duality, the lower-triangular decomposition of type matrices, and the concept of the least concave majorant—the paper establishes the relationship between the two primal problems.

Key Contributions and Results

• Equivalence of Revenue: The primary result is that the optimal revenue achievable under unidirectional incentive compatibility (where bidders can only underbid) is exactly equal to the optimal revenue under full incentive compatibility. Consequently, unidirectional incentive compatibility is sufficient for revenue maximization in multi-agent environments.
• Technical Reformulation: The paper provides an alternative formulation of Myerson's optimal auction. Instead of imposing a monotonicity constraint on the allocation rule, the author incorporates the upper envelope formula directly into the objective function. This formulation naturally accounts for the information rent required for higher types without explicitly constraining the allocation rule to be monotone in the primal problem.
• Resolution of Moore's Open Question: The paper confirms that the sufficiency of downward constraints, previously known only for single-agent settings (Moore, 1984), holds true for multi-agent environments, overcoming the difficulties related to the feasibility of allocation rules in such settings.
• Feasibility Analysis: The LP duality approach allows for a rigorous analysis of the feasibility of allocation rules in multi-agent environments, demonstrating that the relaxation of bidirectional constraints to unidirectional ones does not expand the set of achievable revenues.

Significance and Claims
The paper claims to be the first to demonstrate the sufficiency of downward incentive constraints for multi-agent environments. It positions itself as a technical contribution that bridges the gap between single-agent insights (Moore, 1984; Celik, 2006; Krämer and Strausz, 2025) and multi-agent auction design.

The author notes that while the result implies that the value of the revenue maximization problem under UIC ([S1]) is never strictly greater than that under full IC ([S2]), the proof relies on the construction and matching of the dual problems. The paper concludes by briefly mentioning that the result can be extended to continuous type spaces, though the primary technical proof is grounded in the discrete model.

Limitations and Scope
The paper is modest in its scope, focusing strictly on the theoretical equivalence of revenue outcomes under different incentive constraints. It does not propose new experimental applications, nor does it detail specific algorithmic implementations for continuous spaces beyond a brief mention of extension. The analysis is confined to independent private values and finite type spaces, with the extension to continuous types noted as a future discussion point rather than a core result of the current work.