When is multidimensional screening a convex program?

Alessio Figalli, Young-Heon Kim, Robert J. McCann

TL;DR

This paper tackles the complex problem of a monopolist designing product offerings and prices to maximize profits when customers have diverse, multidimensional preferences. They identify a crucial mathematical condition, "non-negative cross-curvature," that transforms this intractable problem into a solvable convex program, enabling more robust analysis and unique solutions. This is a significant step towards understanding how businesses can effectively cater to diverse customer needs in complex markets.

What Problem Does This Paper Address?

Imagine a car manufacturer (the "principal") trying to sell cars (the "products") to a diverse group of potential buyers (the "agents"). Each buyer has unique preferences for different car features (e.g., fuel efficiency, luxury, performance), and these preferences can be described by multiple characteristics (multidimensional). The manufacturer knows the general distribution of these preferences but not each individual buyer's specific taste. On top of this, manufacturing each car has a cost. The manufacturer's goal is to set prices and product variations to maximize their profit.

This "principal-agent" problem is notoriously difficult, especially when customer preferences are multidimensional. Traditional economic models often simplify this by assuming one-dimensional preferences or a limited number of products. However, real-world markets are far more complex. The core challenge is that the manufacturer's profit-maximization problem, when dealing with multidimensional preferences, often becomes mathematically "non-convex." Non-convex optimization problems are notoriously hard to solve, both theoretically and computationally, meaning it's difficult to guarantee finding the absolute best solution, or even to know if the solution found is stable or unique. This paper aims to find a specific condition on customer preferences that makes this complex problem mathematically convex, thereby making it tractable.

Methods

The authors introduce a mathematical condition called "non-negative cross-curvature" (condition B3) on the customer preference function, denoted by $b(x, y)$, where $x$ represents the agent's type and $y$ represents the product type. This condition, along with other regularity assumptions on preferences and costs (B0-B2), is shown to be both necessary and sufficient for the set of "b-convex functions" to be convex.

The key insight is that the principal's profit maximization problem can be reformulated as minimizing a function over the set of b-convex functions. If this set is convex (thanks to the non-negative cross-curvature condition), and if the principal's cost function is also "b*-convex" (a related concept), then the entire optimization problem becomes a convex program. This transformation is crucial because convex programs have well-behaved properties: any local minimum is a global minimum, and standard algorithms can efficiently find solutions. They leverage concepts from optimal transportation theory and functional analysis to prove these results.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on mathematical conditions and their implications for economic models, rather than empirical testing on specific datasets.

Key Insights and Ideas

  • The "Convexity" Key: The paper's central idea is that a specific mathematical property of customer preferences (non-negative cross-curvature) is the "magic ingredient" that turns a complex, intractable optimization problem into a well-behaved convex one.
  • Beyond Simple Preferences: The non-negative cross-curvature condition is a generalization of simpler "single-crossing" conditions used in economics, allowing for more realistic multidimensional customer preferences.
  • Robustness and Uniqueness: Achieving convexity not only makes the problem solvable but also leads to unique and stable optimal strategies for both the principal (manufacturer) and the agents (customers). This is a significant improvement over non-convex models where solutions can be ambiguous.
  • Exclusion as a Feature: The paper confirms and generalizes the economic phenomenon of "exclusion," where a monopolist might strategically price certain products so high that a fraction of customers are priced out of the market. This is shown to be a robust outcome in models satisfying their conditions.

Key Results

  • Necessary and Sufficient Condition: The paper establishes that "non-negative cross-curvature" (B3) is a necessary and sufficient condition for the set of b-convex functions to be convex, given standard regularity assumptions (B0-B2).
  • Convex Program Transformation: When the preference function satisfies B3 and the cost function is b*-convex, the principal's profit maximization problem becomes a convex program.
  • Uniqueness and Stability: Under slightly stronger conditions (strict b*-convexity of costs or positive cross-curvature of preferences), the authors prove the uniqueness and stability of optimal strategies for both the principal and the agents.
  • Desirability of Exclusion: The paper shows that the phenomenon of excluding a fraction of customers from the market is a robust outcome in a broad class of multidimensionally screened models satisfying their conditions.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, establishing mathematical conditions for convexity. While it has strong implications for economic modeling, it doesn't present empirical validation on real-world market data.
  • Assumptions: The analysis relies on several mathematical assumptions (e.g., $C^4$ differentiability of preferences, open and bounded type spaces). While these are standard in such theoretical work, their relaxation could be a direction for future research.
  • Computational Aspects: While convexity implies tractability, the paper doesn't delve into specific computational algorithms for solving these convex programs in the multidimensional setting, beyond mentioning that standard techniques could be applied.
  • Future Work: The authors suggest that their findings enable a more complete theoretical and computational analysis of multidimensional principal-agent problems. They also conjecture that non-negative cross-curvature is essential for the robustness of phenomena like exclusion and bunching observed in simpler models. Further exploration of these robustness properties and the development of practical computational tools are implied future directions.

Summary updated

Abstract

A principal wishes to transact business with a multidimensional distribution of agents whose preferences are known only in the aggregate. Assuming a twist (= generalized Spence-Mirrlees single-crossing) hypothesis and that agents can choose only pure strategies, we identify a structural condition on the preference b(x,y) of agent type x for product type y -- and on the principal's costs c(y) -- which is necessary and sufficient for reducing the profit maximization problem faced by the principal to a convex program. This is a key step toward making the principal's problem theoretically and computationally tractable; in particular, it allows us to derive uniqueness and stability of the principal's optimum strategy -- and similarly of the strategy maximizing the expected welfare of the agents when the principal's profitability is constrained. We call this condition non-negative cross-curvature: it is also (i) necessary and sufficient to guarantee convexity of the set of b-convex functions, (ii) invariant under reparametrization of agent and/or product types by diffeomorphisms, and (iii) a strengthening of Ma, Trudinger and Wang's necessary and sufficient condition (A3w) for continuity of the correspondence between an exogenously prescribed distribution of agents and of products. We derive the persistence of economic effects such as the desirability for a monopoly to establish prices so high they effectively exclude a positive fraction of its potential customers, in nearly the full range of non-negatively cross-curved models.
BibTeX
@article{figalli2011when,
  author = {Alessio Figalli and Young-Heon Kim and Robert J. McCann},
  title = {{When is multidimensional screening a convex program?}},
  journal = {J. Econ. Theory},
  year = {2011},
  doi = {10.1016/j.jet.2010.11.006},
}
Figure