Abstract
Walrasian Equilibrium (WE) is the gold standard for market efficiency, yet it frequently fails to exist in markets with indivisible items and complex buyer valuations. This paper introduces Two-Price Equilibrium (2PE), a novel relaxation where each item is assigned two prices: a lower price for its current owner and a higher price for all other participants. We demonstrate that 2PEs are guaranteed to exist in settings where traditional equilibria do not. By introducing a "discrepancy" metric, we prove that 2PEs provide a constant-fraction guarantee of optimal social welfare, even for buyers with heterogeneous subadditive valuations. This framework provides a theoretical bridge between equilibrium pricing and the performance of common auction formats like Simultaneous Second Price Auctions (S2PA).
Introduction
In market design, the Walrasian Equilibrium represents a state where supply equals demand and every participant receives their most preferred bundle at market prices. However, the existence of a WE is highly sensitive to the nature of buyer valuations. When items are indivisible, a WE typically only exists under restrictive conditions, such as "gross substitutes." For more complex but common valuations—such as subadditive valuations, where the value of a bundle is less than or equal to the sum of its parts—traditional equilibrium notions often collapse.
Previous attempts to relax these requirements, such as Conditional Equilibrium (CE), have expanded the range of viable markets but still fail to guarantee existence in many subadditive settings. This paper addresses this gap by proposing the Two-Price Equilibrium (2PE), a stable market state that mirrors real-world behaviors and ensures high social welfare.
The Two-Price Equilibrium Framework
A Two-Price Equilibrium is defined by a tuple $(\mathbf{S}, \hat{\mathbf{p}}, \check{\mathbf{p}})$, where $\mathbf{S}$ represents the allocation of items, $\check{\mathbf{p}}$ is a vector of "low" prices for current owners, and $\hat{\mathbf{p}}$ is a vector of "high" prices for non-owners.
In this model, a buyer is considered "maximally happy" if their current bundle (purchased at the low price) is preferred over any other possible bundle (where any item not currently owned must be purchased at the high price). This structure effectively incorporates a mathematical version of the "endowment effect," where the cost of acquisition is higher than the cost of retention.
Measuring Efficiency: Discrepancy
To evaluate the quality of a 2PE, the authors introduce the concept of discrepancy ($d$). Discrepancy is defined as the sum of the differences between the high and low prices across all items, normalized by the total social welfare. This metric is crucial because it directly relates to the efficiency of the market. The authors prove a "Graceful Degradation" property: any 2PE with a discrepancy $d$ is guaranteed to capture at least a $\frac{1}{d+1}$ fraction of the optimal social welfare.
Theoretical Insights and Auction Correspondence
One of the most significant contributions of this work is the formal link established between 2PE and Simultaneous Second Price Auctions (S2PA). The authors show that every Pure Nash Equilibrium of an S2PA corresponds to a 2PE. This provides a rigorous theoretical foundation for why S2PAs—which are widely used in practice—often result in high-efficiency outcomes despite the theoretical non-existence of Walrasian prices.
Furthermore, the paper utilizes new geometric tools for analyzing symmetric valuations, specifically the concepts of max-forward-slope and min-backward-slope. These tools allow researchers to bound the deviation between high and low prices while maintaining the equilibrium state.
Welfare Guarantees for Subadditive Valuations
The paper provides the first constant-fraction welfare guarantees for several classes of subadditive valuations over identical items:
- Two Identical Buyers: A 2PE always exists with a discrepancy of at most 2, ensuring at least 1/3 of the optimal welfare.
- Multiple Identical Buyers: A 2PE exists with a discrepancy of at most 2.5, ensuring at least 2/7 of the optimal welfare.
- Heterogeneous Buyers: Even when buyers have different subadditive valuations, a 2PE exists with a discrepancy of at most 6, guaranteeing at least 1/7 of the optimal welfare.
These results are achieved through an algorithmic framework (Algorithm 1) designed to find allocations that minimize discrepancy by balancing price deviations against buyer valuations.
Conclusion and Future Work
The Two-Price Equilibrium offers a powerful new lens for understanding market stability and efficiency. By relaxing the single-price constraint of Walrasian models, 2PE provides existence guarantees and robust welfare bounds in complex combinatorial settings.
While the current results focus primarily on identical items (symmetric valuations), the 2PE definition is broad enough to encompass heterogeneous items. Future research is needed to establish low-discrepancy bounds for these more general cases and to explore how the 2PE framework might inform the design of next-generation auction mechanisms that are both stable and efficient.
Summary updated