Nonbossy Mechanisms: Mechanism Design Robust to Secondary Goals

Renato Paes Leme, Jon Schneider, Hanrui ZhangarXiv 2023 · DOI · arXiv

Abstract

Standard mechanism design relies on the assumption that agents are purely self-interested, caring only about their own allocation and payment. However, in real-world scenarios, agents often possess "secondary goals"—such as altruism toward a partner or spite toward a competitor—that can destabilize even the most well-regarded mechanisms. This paper introduces and characterizes "Nonbossy Mechanisms," proving that a mechanism is robust to any secondary goal if and only if it is both Incentive Compatible (IC) and Nonbossy. While robustness in single-item auctions restricts designers to sequential posted-price offers, we demonstrate that in complex environments, a broader class of "decision lists with exceptions" can significantly outperform simple posted prices in both welfare approximation and revenue extraction.

Introduction

In the traditional framework of mechanism design, we assume agents are "rational" in a narrow sense: they seek to maximize a primary utility function based solely on their own outcomes. We design Incentive Compatible (IC) mechanisms to ensure that truth-telling is the optimal strategy under these conditions.

Yet, real-world interactions are rarely so isolated. A broker may have a preference for which client wins a contract, or a firm may be willing to take a slight hit to ensure a rival pays a higher price. These "hidden agendas" or secondary goals create a fragility in standard mechanisms. For example, in a classic Second-Price Auction, a losing bidder is indifferent between bidding $1 or $1,000, as their primary utility remains zero. However, if they wish to spite the winner, they can bid just below the winner's value to drive up the price. This "bossy" behavior—changing others' outcomes without affecting one's own—is the central problem addressed by researchers from Google and Carnegie Mellon in this work.

The Framework of Nonbossiness

To address this fragility, the authors focus on the concept of Nonbossiness (NB). A mechanism is defined as nonbossy if an agent cannot change the outcome or payment of any other agent without also changing their own outcome or payment.

The paper establishes a fundamental equivalence: a mechanism is robust to any secondary goal if and only if it satisfies both IC and Nonbossiness. This provides a clear mathematical target for designers who wish to create mechanisms that remain stable even when agents have complex, external motivations.

Characterizing Payments and Structure

The methodology follows a rigorous path to characterize these robust mechanisms:

  1. The Upper Semilattice Property: The authors identify that in most common environments, the payments in any nonbossy mechanism must be a function of the outcome vector alone.
  2. Public Decisions: In settings where a single outcome affects everyone (e.g., selecting a location for a public facility), the authors find a result reminiscent of the Gibbard-Satterthwaite theorem. Robustness is extremely restrictive here, often forcing the mechanism to be either a dictatorship or limited to only two possible outcomes.
  3. Single-Item Auctions: The paper provides the first characterization of Sequential Posted-Price Mechanisms (SPPMs) based on robustness, proving they are the only mechanisms that are IC, individually rational, and nonbossy in this setting.

Beyond Posted Prices: Decision Lists with Exceptions

While SPPMs are the only robust option for single-item auctions, the authors uncover a much richer landscape in more complex environments, such as combinatorial auctions or settings with feasibility constraints. They introduce a new class of mechanisms: Decision Lists with Exceptions.

These mechanisms operate by checking a prioritized list of price vectors. The mechanism iterates through the list and selects the first outcome where all agents accept the associated prices, provided that the outcome does not trigger a predefined "exception." This structure allows for significantly more flexibility than simple sequential offers.

Key Performance Results

The theoretical analysis demonstrates that nonbossy mechanisms are strictly more powerful than SPPMs in complex settings:

  • Welfare Approximation: In environments with complex constraints, nonbossy mechanisms can achieve an $O(\log r)$ approximation of optimal welfare (where $r$ is the rank of the feasible set). In contrast, SPPMs are mathematically capped at an $\Omega(r)$ gap, representing a significant loss in efficiency.
  • Revenue Extraction: In scenarios with correlated valuations, a nonbossy "decision list" can potentially extract 100% of the optimal welfare as revenue. The best possible SPPM in the same scenario might only capture 80% (4/5).
  • Tractability: The authors prove that the space of IC, IR, and NB mechanisms is finite-dimensional. This suggests that finding the optimal robust mechanism for a given setting is a computationally tractable optimization problem.

Limitations and Future Directions

The current work focuses primarily on deterministic mechanisms. While nonbossiness can be achieved relatively easily through randomization (e.g., by adding a small probability of a strictly monotone outcome), such approaches often sacrifice the simplicity and predictability that make deterministic nonbossy mechanisms attractive for real-world implementation.

Future research is poised to explore the computational complexity of generating optimal decision lists in high-dimensional environments and extending these characterizations to multi-parameter settings where agents have non-linear preferences. Additionally, the "menu size" of these decision lists—specifically, how many exceptions are required to reach near-optimal performance—remains an open and vital question for practical mechanism design.

Summary updated

Abstract

We study mechanism design when agents may have hidden secondary goals which will play a role when the primary utility of the outcomes is the same. We show that in such cases, a mechanism is immune to strategic manipulation if and only if it is incentive compatible with regard to primary utility -- a property we term "primary incentive compatibility" -- and nonbossy -- a well-studied property in the context of matching and allocation mechanisms. We give complete characterizations of primarily incentive-compatible and nonbossy mechanisms in various settings, including auctions with single-parameter agents and public decision settings where all agents share a common outcome. In particular, we show that in the single-item setting, a mechanism is primarily incentive compatible, individually rational, and nonbossy if and only if it is a sequential posted-price mechanism.
BibTeX
@misc{leme2023nonbossy,
  author = {Renato Paes Leme and Jon Schneider and Hanrui Zhang},
  title = {{Nonbossy Mechanisms: Mechanism Design Robust to Secondary Goals}},
  year = {2023},
  eprint = {2307.11967},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.11967},
}
Figure