Pricing Equilibria and Graphical Valuations

Ozan Candogan, Asuman E. Ozdaglar, Pablo A. ParriloACM Trans. Economics and Comput 2018 · DOI

TL;DR

This paper investigates whether simpler pricing rules can guarantee efficient market outcomes (pricing equilibria) for graphical valuations, a class of valuations that capture item complementarities and substitutabilities. The authors find that while anonymous graphical pricing is more powerful than anonymous item pricing (Walrasian equilibrium), it doesn't always guarantee an equilibrium, especially for simpler graph structures.

What Problem Does This Paper Address?

In markets with multiple items, a key challenge is how a seller can allocate items efficiently to buyers to maximize overall welfare. This is often achieved through a "pricing equilibrium," where market prices support an efficient allocation and clear the market. A standard concept is the Walrasian equilibrium, which relies on anonymous item prices. However, Walrasian equilibria don't always exist, especially when items have complementary values (e.g., the value of owning both item A and item B is greater than the sum of their individual values).

This paper focuses on "graphical valuations," where item relationships (complementarity/substitutability) are represented by a graph. The authors explore whether simpler pricing rules, beyond anonymous item pricing, can guarantee pricing equilibria for these graphical valuations, even when Walrasian equilibria fail. They specifically examine "anonymous graphical pricing" (where prices can include pairwise discounts/markups) and "agent-specific item pricing" (where each agent has unique prices for individual items).

Methods

The paper employs a combination of theoretical analysis and linear programming formulations.

  • Linear Programming (LP) Formulations: The authors adapt existing LP formulations for efficient allocation problems to the context of graphical valuations. They introduce new LP formulations (LP2 and LP2c) specifically for anonymous graphical pricing.
  • Duality Theory: They leverage the dual of these LP problems to derive pricing rules and analyze the existence of pricing equilibria.
  • Graph Theory: Concepts like series-parallel graphs and graph minors are used to characterize the structure of the value graphs and their implications for equilibrium existence.
  • Constructive Proofs: The authors provide explicit examples and constructions to demonstrate their theoretical findings, particularly for non-existence results.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Anonymous Graphical Pricing is More Powerful: Anonymous graphical pricing (allowing pairwise discounts/markups) can guarantee pricing equilibria in a broader set of graphical valuations compared to anonymous item pricing (Walrasian equilibrium). This means it can support efficient outcomes in some scenarios where Walrasian equilibria fail.
  • Structure Matters: The structure of the underlying value graph is crucial. For "simple" series-parallel graphs, anonymous graphical pricing offers no advantage over anonymous item pricing – an equilibrium exists with one if and only if it exists with the other.
  • Non-Existence is Pervasive: Even for simple graphical valuations (like those with only pairwise complementarities or substitutabilities), Walrasian equilibria (and thus agent-specific item pricing equilibria) may not exist. This highlights the limitations of simpler pricing rules.
  • Trade-off Between Simplicity and Guarantee: There's a fundamental trade-off. While agent-specific graphical pricing can always guarantee an equilibrium, it's computationally impractical. The paper explores if simpler, more practical pricing rules can offer similar guarantees, finding that they often fall short.

Key Results

  • Agent-Specific Item Pricing Equivalence: A pricing equilibrium with agent-specific item pricing exists if and only if a pricing equilibrium with anonymous item pricing (Walrasian equilibrium) exists. This implies that this pricing rule doesn't help overcome Walrasian non-existence.
  • Series-Parallel Graphs: For graphical valuations with series-parallel value graphs, a pricing equilibrium with anonymous graphical pricing exists if and only if a Walrasian equilibrium exists.
  • General Graphical Valuations: For more general graphical valuations (not necessarily series-parallel), anonymous graphical pricing can guarantee a pricing equilibrium even when a Walrasian equilibrium does not exist. This is demonstrated with an example involving a K5 graph.
  • Non-Existence Examples: The paper provides examples of graphical valuations with simple structures (e.g., tree-like graphs) where Walrasian equilibria do not exist, and consequently, pricing equilibria with agent-specific item pricing and anonymous graphical pricing also do not exist.

Limitations and Future Work

  • No General Sufficient Conditions: The paper notes that there are no known general sufficient conditions for the existence of a pricing equilibrium with anonymous graphical pricing. This is identified as an important direction for future research.
  • Exploring Richer Pricing Rules: The authors suggest investigating whether allowing discount/markup terms for bundles of cardinality greater than two, while preserving anonymity, could lead to pricing equilibria in more cases.
  • Generalizing to Additively Decomposable Valuations: The paper introduces additively decomposable valuations, which generalize graphical valuations, and shows that LP formulations can still be used to find equilibria. This suggests a path for extending the analysis to more complex valuation structures.

Summary updated

BibTeX
@article{candogan2018pricing,
  author = {Ozan Candogan and Asuman E. Ozdaglar and Pablo A. Parrilo},
  title = {{Pricing Equilibria and Graphical Valuations}},
  journal = {ACM Trans. Economics and Comput.},
  year = {2018},
  doi = {10.1145/3175495},
}
Figure