Market Pricing for Matroid Rank Valuations

Kristóf Bérczi, Naonori Kakimura, Yusuke Kobayashi

Abstract

In the study of market equilibria, the existence of Walrasian prices typically assumes the presence of a central coordinator to break ties when buyers are indifferent between multiple utility-maximizing bundles. This paper investigates the existence of "robust" prices—prices where any utility-maximizing choice made by a buyer independently leads to a social welfare-maximizing outcome. Focusing on markets with two buyers having matroid rank valuations, we provide polynomial-time algorithms for specific matroid classes and prove a fundamental reduction theorem: the complex weighted version of the robust pricing problem is equivalent to its unweighted counterpart. These results advance the understanding of the Dütting and Végh (2017) conjecture and extend the reach of discrete convex analysis in economic theory.

Introduction

In a classical Walrasian equilibrium, a seller sets prices for a set of items, and buyers select bundles that maximize their individual utility (the difference between the bundle's value and its price). When the market clears, the resulting allocation maximizes total social welfare. However, a significant theoretical and practical hurdle exists: the tie-breaking problem. If a buyer is indifferent between two or more optimal bundles, their arbitrary choice may prevent other buyers from obtaining their own optimal bundles, thereby failing to reach a social welfare-maximizing state.

Standard economic theory bypasses this by assuming a "central coordinator" who breaks ties in a way that ensures global optimality. In decentralized markets, however, such coordination is absent. This paper addresses a conjecture by Dütting and Végh (2017), which asks whether prices can be set such that any utility-maximizing choice by the buyers—regardless of how they break ties—results in an optimal allocation. We specifically examine this through the lens of matroid rank valuations, a robust framework for modeling preferences over sets of items.

Methodological Framework

Our approach integrates techniques from Matroid Theory and Discrete Convex Analysis to construct and verify robust prices.

Graph-Theoretic Constructions

To identify prices that satisfy the robust equilibrium condition, we utilize bipartite digraphs based on Krogdahl’s dependence graphs. By applying topological sorting to these graphs, we can assign prices that ensure certain exchange properties are met. If the resulting graph is acyclic, it serves as a certificate that prices can be assigned to satisfy the required conditions for tie-breaking robustness.

Weight-Splitting and Reductions

A central contribution of this work is the application of Frank’s weight-splitting theorem for matroid intersection. We demonstrate that the search for robust prices in a market with weighted items can be simplified. Specifically, we prove that if a pricing solution exists for the "unweighted" version of the problem (where item values are binary), a solution necessarily exists for the weighted version. This reduction significantly narrows the search space for a general proof of the Dütting and Végh conjecture.

Dual Matroids and Gross Substitutes

By rephrasing the pricing conditions using dual matroids, we simplify the constraints necessary for equilibrium. Furthermore, we extend our reduction techniques to the class of $M^\natural$-concave functions. These functions are equivalent to "gross substitutes" valuations, which are considered the gold standard for well-behaved preferences in combinatorial auctions.

Key Results

Algorithmic Successes

We provide polynomial-time algorithms to find robust prices for two buyers in two significant cases:

  1. When one buyer has a partition matroid preference (e.g., requiring a specific number of items from disjoint categories).
  2. When both buyers have strongly base orderable preferences.

The Equivalence Theorem

Theorem 3 establishes that the weighted version of the pricing conjecture is equivalent to the unweighted version. This is further generalized in Theorem 19, which shows that the pricing problem for the complex gross substitutes valuation class can be reduced to a simpler set-membership problem involving $M^\natural$-convex sets.

Applications to Bipartite Matching

As a corollary of our findings (Corollary 17), we demonstrate an application to graph theory: it is possible to weight the edges of a bipartite graph such that for every vertex, the "lightest" incident edge is guaranteed to belong to a perfect matching. This provides a new perspective on the intersection of matching theory and market pricing.

Discussion and Future Work

While this paper makes significant strides, several challenges remain. Our concrete algorithmic results are currently limited to the two-buyer case. While the reduction techniques are general, finding robust prices for three or more buyers remains an open and complex problem.

Additionally, the general Dütting and Végh conjecture—that such prices exist for any two matroids—remains unproven, though our work clears the path by resolving the weighted-to-unweighted transition. Finally, our current methods for gross substitutes may occasionally yield negative prices. Future research is needed to determine conditions under which robust prices can be guaranteed to be non-negative, ensuring greater applicability to real-world market design.

Summary updated

BibTeX
@article{berczi2021market,
  author = {Kristóf Bérczi and Naonori Kakimura and Yusuke Kobayashi},
  title = {{Market Pricing for Matroid Rank Valuations}},
  journal = {SIAM J. Discret. Math.},
  year = {2021},
  doi = {10.1137/20m1386335},
}
Figure