Ascending Auctions for Combinatorial Markets with Frictions: A Unified Framework via Discrete Convex Analysis

Ryosuke Sato; Taihei Oki

arxiv: 2604.10563 · v1 · submitted 2026-04-12 · 💻 cs.GT

Ascending Auctions for Combinatorial Markets with Frictions: A Unified Framework via Discrete Convex Analysis

Taihei Oki , Ryosuke Sato This is my paper

Pith reviewed 2026-05-10 15:59 UTC · model grok-4.3

classification 💻 cs.GT

keywords ascending auctionsWalrasian equilibriacombinatorial marketsstrong substitutesdiscrete convex analysispayment frictionsbuyer-optimal equilibriumpolymatroid sum

0 comments

The pith

Ascending auctions can compute buyer-optimal Walrasian equilibria in combinatorial markets with payment frictions by using directional price updates from discrete convex analysis.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs an ascending-auction procedure that finds Walrasian equilibria when buyers have strong-substitutes valuations and payments include piecewise-linear frictions such as taxes or commissions. It extends the Gul-Stacchetti and Ausubel ascending auctions by replacing uniform price increases with heterogeneous directional updates that respect each seller's payment structure. The same construction generalizes earlier imperfectly-transferable-utility models from unit-demand to fully combinatorial settings. A key result is that the procedure can reach the minimum-price, or buyer-optimal, equilibrium—the first such guarantee for frictional combinatorial markets. The analysis rests on discrete convex analysis to identify admissible price directions and to produce a strongly polynomial algorithm that queries only demand oracles.

Core claim

The central claim is that valid price-update directions for ascending auctions in frictional combinatorial markets are characterized by the minimal solution to a lexicographic extension of the polymatroid-sum problem; this direction can be recovered in strongly polynomial time by reducing the dual to a convex flow problem and exploiting L♮-convexity. The resulting auction computes the buyer-optimal Walrasian equilibrium while using only demand-oracle queries and never handling exponential-size objects.

What carries the argument

Characterization of valid directional price updates via the minimal dual solution to a lexicographic polymatroid-sum problem, obtained through reduction to a convex flow and L♮-convexity of the dual objective.

Load-bearing premise

Valuations satisfy the strong-substitutes condition and the market admits Walrasian equilibria when payments are piecewise linear.

What would settle it

A strong-substitutes valuation profile and piecewise-linear payment functions for which no price direction exists that preserves the equilibrium property at every step of the auction.

Figures

Figures reproduced from arXiv: 2604.10563 by Ryosuke Sato, Taihei Oki.

read the original abstract

We develop a unified ascending-auction framework for computing Walrasian equilibria in combinatorial markets with strong substitutes valuations and piecewise-linear payment functions. Our auction extends the celebrated ascending auctions of Gul and Stacchetti (2000) and Ausubel (2006) to accommodate payment frictions (e.g., transaction taxes or commission fees). This is achieved by incorporating directional price updates that reflect heterogeneous payment structures. Our framework also generalizes the unit-demand imperfectly transferable utility models of Alkan (1989, 1992) to a fully combinatorial setting, thereby unifying these paradigms. Furthermore, this is the first study to compute the minimum -- also known as the buyer-optimal -- equilibrium in combinatorial markets with such frictions. Our analysis builds upon discrete convex analysis. Our main technical contribution is a characterization of valid price-update directions, together with a strongly polynomial-time algorithm for computing them. Notably, the algorithm uses only demand-oracle queries and never requires handling information of exponential size. To compute such a direction, we formulate a lexicographic extension of the polymatroid sum problem and characterize its dual solution via a reduction to a convex flow problem. Exploiting the $\text{L}^\natural$-convexity of the dual objective, we show that the desired direction can be constructed from the minimal dual solution. This convexity also yields transparent economic and potential-based interpretations of the auction dynamics, strengthening the connection between ascending auctions and discrete optimization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This extends ascending auctions to combinatorial markets with payment frictions and gives the first buyer-optimal equilibrium algorithm via discrete convex analysis.

read the letter

The main thing to know is that the paper unifies ascending auctions for combinatorial markets that include payment frictions such as taxes or commissions, and it claims to be the first to compute the buyer-optimal equilibrium under those conditions. It does this by generalizing the Gul-Stacchetti and Ausubel ascending auctions plus Alkan's unit-demand models to full combinatorial settings with piecewise-linear payments, all while staying inside strong substitutes valuations. The technical step forward is a characterization of valid price-update directions that uses a lexicographic polymatroid sum, reduces the dual to a convex flow problem, and extracts the minimal solution via L-natural-convexity. This yields a strongly polynomial, demand-oracle algorithm that never materializes exponential-size information and supplies potential-based interpretations of the price dynamics. Those pieces line up with the existing literature and avoid obvious circularity or invented objects. The assumptions are the usual ones in this area, so they are not hidden weaknesses, though they do restrict the markets covered. A referee would still want to verify the details of the dual minimality argument and the exact reduction steps, since the abstract alone leaves those as black boxes. Nothing in the described chain suggests a load-bearing gap. This is aimed at researchers in algorithmic mechanism design who already work with discrete convex methods or combinatorial auctions. A reader focused on practical frictions in market design would get concrete value from the new reductions and the unification. I would send it to peer review; the problem is relevant and the technical approach looks grounded enough to deserve referee attention.

Referee Report

0 major / 2 minor

Summary. The manuscript develops a unified ascending-auction framework for computing Walrasian equilibria in combinatorial markets with strong substitutes valuations and piecewise-linear payment functions. It extends the ascending auctions of Gul and Stacchetti (2000) and Ausubel (2006) to accommodate payment frictions and generalizes Alkan's (1989, 1992) unit-demand imperfectly transferable utility models to a fully combinatorial setting. The central technical contribution is a characterization of valid price-update directions together with a strongly polynomial-time algorithm that uses only demand-oracle queries, obtained by formulating a lexicographic extension of the polymatroid-sum problem, reducing its dual to a convex flow problem, and extracting the minimal dual solution via L♮-convexity of the dual objective.

Significance. If the derivations hold, this is a significant contribution to algorithmic mechanism design. It is the first work to compute the buyer-optimal equilibrium in combinatorial markets with such frictions, unifies several prior paradigms under discrete convex analysis, and supplies a demand-oracle algorithm whose strong polynomiality and avoidance of exponential-size information are valuable. The L♮-convexity arguments also furnish transparent economic and potential-based interpretations of the auction dynamics.

minor comments (2)

The abstract asserts that this is the 'first study' to compute the buyer-optimal equilibrium; the introduction should contain an explicit comparison paragraph that situates the result against all prior ascending-auction and frictional-market papers to substantiate the novelty claim.
The reduction of the lexicographic polymatroid-sum dual to a convex flow problem is described at a high level; adding a short paragraph or figure that sketches the flow network (nodes, arcs, capacities) would improve accessibility for readers outside discrete convex analysis.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our manuscript, the recognition of its significance as a unifying framework, and the recommendation for minor revision. We are pleased that the technical contributions via discrete convex analysis and the demand-oracle algorithm are viewed as valuable.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via external discrete convex analysis

full rationale

The paper's core claims rest on a new characterization of price-update directions via lexicographic polymatroid-sum dual reduced to convex flow, using only demand oracles and L♮-convexity properties. These steps extend established results from discrete convex analysis (Murota et al. and related literature) and prior ascending-auction frameworks (Gul-Stacchetti, Ausubel, Alkan) without any reduction of the buyer-optimal equilibrium computation or strong polynomiality to self-definitions, fitted parameters, or load-bearing self-citations. The unification and first-computation claim for frictional markets follows directly from the oracle model and convexity arguments, which are independently verifiable outside the paper's fitted values or internal loops.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The framework relies on standard assumptions from combinatorial auction theory and properties from discrete convex analysis to derive the algorithm and unification.

axioms (3)

domain assumption Strong substitutes property of valuations
Required for Walrasian equilibria to exist and for the auction to converge as in prior works like Gul and Stacchetti.
domain assumption Piecewise-linear structure of payment functions
Models the frictions and enables the directional updates.
standard math L^♮-convexity of the dual objective
Used to show that the desired direction can be constructed from the minimal dual solution.

pith-pipeline@v0.9.0 · 5560 in / 1515 out tokens · 50367 ms · 2026-05-10T15:59:07.607466+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages

[1]

The optimal value of problems (P 2) and (D2) is 2 +γlog 0.5

to (D2) is given byz ∗ 1 =z ∗ 2 = 1−γlog 2 = 1+γlog 0.5. The optimal value of problems (P 2) and (D2) is 2 +γlog 0.5. Then, the desired direction isd 0 = (0.5,0.5) from Theorem 4.4. Using this direction, the minimal demand sets remain unchanged for all buyers. After the price perturbation alongd 0, the minimal demand sets remain identical to those atp. Vi...

work page
[2]

Then, the desired direction isd 1 = (0.5,0.125) from Theorem 4.4

to (D2) is given byz ∗ 1 = 1−γlog 2 = 1+γlog 0.5 andz ∗ 2 = 1−γlog 8 = 1 +γlog 0.125. Then, the desired direction isd 1 = (0.5,0.125) from Theorem 4.4. After the price perturbation alongd 1, the minimal demand sets change to: ˇD1(p+εd 1) ={(1,0)}, ˇD2(p+εd 1) ={(1,0),(0,1)},and ˇD3(p+εd 1) ={(0,1)}. Therefore, the minimal maximally over-demanded set remai...

work page
[3]

This shows that the violation of(LSC)is caused by Case (iv)

to (D 2) changes toz ∗ 1 = 1−γlog 2 = 1 +γlog 0.5 andz ∗ 2 = 1−γlog 1.6 = 1 +γlog 0.625. This shows that the violation of(LSC)is caused by Case (iv). Then, the desired direction isd 2 = (0.5,0.625). After the price perturbation alongd 2, the minimal demand sets change to: ˇD1(p+εd 2) ={(1,0),(0,1)}, ˇD2(p+εd 2) ={(1,0)},and ˇD3(p+εd 2) ={(0,1)}. 45

work page

[1] [1]

The optimal value of problems (P 2) and (D2) is 2 +γlog 0.5

to (D2) is given byz ∗ 1 =z ∗ 2 = 1−γlog 2 = 1+γlog 0.5. The optimal value of problems (P 2) and (D2) is 2 +γlog 0.5. Then, the desired direction isd 0 = (0.5,0.5) from Theorem 4.4. Using this direction, the minimal demand sets remain unchanged for all buyers. After the price perturbation alongd 0, the minimal demand sets remain identical to those atp. Vi...

work page

[2] [2]

Then, the desired direction isd 1 = (0.5,0.125) from Theorem 4.4

to (D2) is given byz ∗ 1 = 1−γlog 2 = 1+γlog 0.5 andz ∗ 2 = 1−γlog 8 = 1 +γlog 0.125. Then, the desired direction isd 1 = (0.5,0.125) from Theorem 4.4. After the price perturbation alongd 1, the minimal demand sets change to: ˇD1(p+εd 1) ={(1,0)}, ˇD2(p+εd 1) ={(1,0),(0,1)},and ˇD3(p+εd 1) ={(0,1)}. Therefore, the minimal maximally over-demanded set remai...

work page

[3] [3]

This shows that the violation of(LSC)is caused by Case (iv)

to (D 2) changes toz ∗ 1 = 1−γlog 2 = 1 +γlog 0.5 andz ∗ 2 = 1−γlog 1.6 = 1 +γlog 0.625. This shows that the violation of(LSC)is caused by Case (iv). Then, the desired direction isd 2 = (0.5,0.625). After the price perturbation alongd 2, the minimal demand sets change to: ˇD1(p+εd 2) ={(1,0),(0,1)}, ˇD2(p+εd 2) ={(1,0)},and ˇD3(p+εd 2) ={(0,1)}. 45

work page