Overview
Research introduces a unified ascending-auction framework designed for combinatorial markets that feature strong substitutes valuations and piecewise-linear payment functions. This framework integrates directional price updates to accommodate heterogeneous payment structures, such as transaction taxes or commission fees. The approach aims to compute Walrasian equilibria in these complex market environments.
Research Context
The developed auction framework extends the established ascending auctions of Gul and Stacchetti (2000) and Ausubel (2006). A key aspect of this extension is its capacity to address payment frictions within the auction mechanism. Furthermore, the framework generalizes the unit-demand imperfectly transferable utility models, initially proposed by Alkan (1989, 1992), to a fully combinatorial setting. This generalization unifies these distinct paradigms. The study is noted as the first to compute the minimum, or buyer-optimal, equilibrium specifically in combinatorial markets that incorporate such frictions.
Approach
The analysis underpinning this framework is built upon discrete convex analysis. A primary technical contribution involves the characterization of valid price-update directions. Associated with this characterization is a strongly polynomial-time algorithm for computing these directions. This algorithm is designed to use only demand- and exchange-oracle queries, thereby avoiding the necessity of handling information that could be of exponential size. To compute a specific direction, the researchers formulated a lexicographic extension of the polymatroid sum problem. The dual solution to this problem is characterized through a reduction to a convex flow problem. The $\text{L}^\natural$-convexity of the dual objective function is exploited to demonstrate that the desired price-update direction can be constructed from the minimal dual solution. This identified convexity also facilitates economic and potential-based interpretations of the auction dynamics, reinforcing the link between ascending auctions and discrete optimization principles.