Stronger core results with multidimensional prices

1. Problem Statement

The paper addresses the problem of one-sided matching with endowments in the absence of money. In this setting:

• There are $n$ agents and $n$ indivisible goods.
• Each agent $i$ has an initial endowment $\omega_i$ (a vector of goods) and von Neumann-Morgenstern (vNM) utility functions over lotteries of goods.
• The goal is to find an efficient and fair allocation (a randomized matching).

The Core Challenge:
In markets with satiated agents (agents who can be fully satisfied and do not desire more goods), standard Competitive Equilibrium (CE) concepts often fail.

• Non-existence: A competitive equilibrium may not exist because satiated agents may spend less than the value of their endowment, creating a surplus that cannot be redistributed to clear the market without violating individual rationality or efficiency.
• Empty Strong Core: The strong core (where no coalition can improve some members without hurting others) may be empty.
• Limitations of Existing Solutions: Previous attempts, such as Dividend Equilibria (redistributing surplus) or Quasi-equilibria (allowing free disposal for zero-income agents), either do not always exist or fail to satisfy strong stability properties like the Rejective Core.

2. Methodology: Lexicographic Dividend Equilibrium (LDE)

The authors propose a novel solution concept called the Lexicographic Dividend Equilibrium (LDE). This concept generalizes competitive equilibria by introducing multi-dimensional prices and a specific structure for budget constraints.

Key Components of an LDE

An LDE consists of three components:

1. Allocation ($x$): A randomized matching of agents to goods.
2. Price Matrix ($P \in \mathbb{R}^{d \times n}$): Instead of a single price vector, each good $j$ has a price vector $p_j$ of dimension $d$.
   • The prices are ordered lexicographically. The first non-zero entry of any price vector must be positive.
   • This creates a hierarchy of "currencies" where the first currency is infinitely more valuable than the second, the second is infinitely more valuable than the third, and so on.
3. Redistribution Matrix ($\alpha \in \mathbb{R}^{d \times n}_+$): Represents dividends (surplus redistribution) given to agents in each currency dimension.

Budget Constraints

An agent $i$ with endowment $\omega_i$ and dividend $\alpha_i$ faces a budget set defined by lexicographic ordering ($\le_{lex}$):
$$C_i(P, \alpha) = \text{closure}(\{ x \in \Delta_n : Px \le_{lex} P\omega_i + \alpha_i \})$$

• Mechanism: Agents prioritize spending their most valuable currency. If they have a positive balance in the first currency, goods with zero price in the first currency are effectively "free" to them (even if they have positive prices in lower currencies), because they can exchange an $\epsilon$ amount of the first currency for an infinite amount of the second.
• Surplus Handling: If an agent has a surplus in a lower currency (because they cannot afford goods in higher currencies), this surplus is redistributed to other agents who lack income in higher currencies but have demand for goods priced in lower currencies.

Stability Properties

The paper defines three "cheapest bundle" properties to ensure efficiency and stability:

1. Strong Cheapest Bundle: No agent can find a weakly preferred bundle that is lexicographically cheaper.
2. Weak Cheapest Bundle: No agent can find a weakly preferred bundle that is strictly cheaper in the most valuable currency they possess.
3. Aggregate Cheapest Bundle: No coalition can redistribute their collective allocation to achieve a weakly preferred outcome that is lexicographically cheaper.

3. Key Contributions and Results

Main Result 1: Existence and Rejective Core Stability

Theorem: For all one-sided matching markets with endowments, a Lexicographic Dividend Equilibrium (LDE) satisfying the strong cheapest bundle property always exists.

• Significance: This resolves the non-existence problem of competitive equilibria in satiated economies.
• Stability: The set of LDEs is contained within the Rejective Core (a stability concept introduced by Konishi, 2005).
  • Rejective Core Definition: An allocation is in the rejective core if no coalition can trade among themselves (using some members' endowments and others' allocations) to make some members strictly better off and others weakly better off.
  • The authors prove that LDEs are strictly stronger than weak core stability and imply individual rationality and ex-ante Pareto optimality.

Main Result 2: Core Convergence

Theorem: As the economy is replicated (scaled up with $N$ copies of each agent), the intersection of the Rejective Core over all replica economies coincides exactly with the set of LDEs satisfying the strong cheapest bundle property.
$$\text{LDE}^+ = \bigcap_{N=1}^{\infty} \text{RC}(\text{Replica}_N)$$

• Significance: This establishes LDEs as the unique viable market outcomes in large markets, extending the classic core convergence theorems (e.g., Debreu-Scarf) to settings with satiation and endowments, without requiring non-satiation assumptions.

4. Technical Approach and Proof Sketch

1. Approximation via Perturbation:
   The existence proof relies on a limiting argument. The authors construct a sequence of economies $(u, \omega_\epsilon)$ where a small fraction $\epsilon$ of goods is redistributed to ensure a standard 1-dimensional competitive equilibrium exists.
2. Decomposition of Prices:
   As $\epsilon \to 0$, the prices in the perturbed economy converge to zero at different rates. The authors analyze the convergence rates (orders of magnitude) of these prices.
   • Goods with prices $\Theta(1)$ form the first currency.
   • Goods with prices $O(\epsilon)$ form the second currency, and so on.
   • This decomposition naturally yields the multi-dimensional price matrix $P$ and the dividend matrix $\alpha$.
3. Separating Hyperplanes:
   For the core convergence result, the proof uses a recursive separation argument (inspired by Debreu-Scarf). It constructs hyperplanes to separate the set of preferred trades from the negative orthant, iteratively pricing goods until all agents receive their favorite affordable bundles or all goods are priced.

5. Significance and Implications

• Theoretical Breakthrough: The paper provides the first solution concept that always exists in one-sided matching with endowments and satiation while satisfying strong stability properties (Rejective Core).
• Generalization of CEEI: It extends the Competitive Equilibrium from Equal Incomes (CEEI) framework to markets with private endowments and satiation, overcoming the "satiability" barrier that previously led to empty cores or non-existent equilibria.
• Practical Interpretation: The multi-dimensional prices can be interpreted as a hierarchy of currencies. This offers a mechanism design perspective where "free" goods for wealthy agents (in the first currency) are funded by the surplus of poorer agents (in lower currencies), ensuring market clearing without external subsidies.
• Limitations and Open Questions:
  • The proof relies on linear preferences (vNM utilities). Extending this to general convex preferences remains an open question, as the linear constraints used to modify prices may become infinite.
  • It is an open question whether two currencies always suffice to clear any such market (the paper provides examples with $d=3$, but conjectures $d=2$ might be sufficient).

In summary, the paper successfully bridges the gap between the theoretical impossibility of competitive equilibria in satiated markets and the practical need for stable, efficient allocations by introducing a robust, multi-dimensional pricing mechanism that guarantees existence and strong core stability.