ICE: An Expressive Iterative Combinatorial Exchange

The strongest honest case is a qualified positive one. The paper has no numbered NP-hardness or polynomial-time complexity theorem: its statement that winner determination is NP-hard is an unnumbered claim citing Rothkopf et al. My lead anchor is therefore the paper’s own algorithmic result, Theorem 6, proved in this paper.

The natural mirror is a high-multiplicity exchange among many standardized trading agents. A type \(t\) consists of a complete bidder description: an integral initial endowment \(x_t^0\in\mathbb Z_{\ge0}^{g}\), a TBBL tree, its true valuation function \(v_t\), and the relevant valuation bounds and parameters. A society is a rational distribution \(\mu\in\mathbb Q_{\ge0}^{\tau}\), with \(\sum_t\mu_t=1\). Thus \(\mu_t\) is the mass of agents having exactly that endowment, valuation structure, prices, and strategic parameters. Goods are still indivisible for each individual agent; only population mass is divisible.

For each type \(t\), let \(\Lambda_t\) be its set of feasible integral trades. The continuous efficient-clearing problem, which I will call Continuous ICE-Welfare Clearing, has variables \(y_{t,\lambda}\ge0\), where \(y_{t,\lambda}\) is the mass of type-\(t\) agents receiving trade \(\lambda\). It asks for a feasible mass allocation maximizing \(W_v(y)=\sum_{t}\sum_{\lambda\in\Lambda_t}y_{t,\lambda}v_t(\lambda)\), subject to \(\sum_{\lambda\in\Lambda_t}y_{t,\lambda}=\mu_t\) for every \(t\), and \(\sum_{t}\sum_{\lambda\in\Lambda_t}y_{t,\lambda}\lambda_j=0\) for every good \(j\). The solution is the mass allocation \(y\), not a fractional bundle assigned to an individual.

This is exactly the population-level version of ICE’s efficient trade. Its master problem is a linear program over trade configurations, while the pricing problem for a type is the ICE best-response problem \(\max_{\lambda\in\Lambda_t}\{v_t(\lambda)-\pi\cdot\lambda\}\). With valuation bounds, the corresponding robust pricing tests are the type-level versions of MRPAR and DIAR. The continuous exchange may therefore output a final \(y\), a sequence of type-level bound refinements, and linear prices \(\pi\), with the requirement that \(W_v(y)\ge\Delta^\star\operatorname{OPT}_v\), or an equivalent additive welfare guarantee.

The regime is plausible in a cloud-capacity or airport-slot exchange. Imagine thousands or millions of standardized jobs, flight operations, or service units exchanging CPU, GPU, storage, or landing-slot bundles. There may be only a few dozen or few hundred complete types: for example, “long-haul morning flight with an evening-slot substitution option,” or “AI-training job initially holding CPU capacity and willing to exchange it for GPU-plus-storage.” Agents of one type are genuinely interchangeable for the market: they have the same endowment, TBBL valuation tree, willingness-to-pay, and relevant constraints. The number of agents can be enormous while \(\tau\) remains moderate. Resource supplies scale per capita, so the continuum is not pretending that a fixed airport with seven slots serves an infinite population.

The high-multiplicity bridge is exact for rational instances. If \(\mu_t=N_t/N\), then \(N\) agents with \(N_t\) copies of type \(t\) induce the same normalized welfare problem. Conversely, a rational mass solution can be expanded into a finite exchange after clearing denominators. Thus this is not merely “replace bidders by a distribution”; it is the high-multiplicity relaxation of the paper’s own efficient-trade problem.

The anchor is:

Theorem 6, proved here. “When ICE incorporates \(\delta\)-MRPAR and \(\epsilon\)-DIAR and when all bidders are straightforward, then the exchange terminates with a trade that is within target approximation error \(\Delta^\star\), for any \(\Delta^\star\ge0\) as \(\epsilon\to0\).” In the paper’s notation, this means the final trade satisfies the required relative-efficiency guarantee \( \mathrm{EFF}(\lambda)\ge\Delta^\star \). The theorem is proved here from the DIAR convergence argument and the direct and price-based efficiency bounds; it is not imported from another paper.

The continuous question corresponding to Theorem 6 is therefore:

Given a finite set of bidder types \(T\), rational masses \(\mu_t\), integral per-agent endowments, TBBL trees with public lower and upper valuation bounds, and access to one truthful valuation representative for each positive-mass type, run a type-level ICE process using common linear prices, \(\delta\)-MRPAR, and \(\epsilon\)-DIAR. Output a feasible mass allocation \(y\) and a transcript certifying that the true welfare of \(y\) is at least \(\Delta^\star\) times the optimum continuous welfare, with termination as \(\epsilon\to0\).

“Straightforward” becomes a natural type-level condition: every representative keeps the common true valuation \(v_t\) inside its reported bounds. The repeated agents of type \(t\) do not independently reveal different information, since that would contradict their being one complete type. A type’s mass simply weights its welfare and resource constraints. The paper’s proof strategy is well suited to this lift: the individual utility inequalities can be multiplied by \(\mu_t\) and summed over types, while DIAR needs to inspect each distinct tree only once rather than once per named bidder.

I would expect the full unrestricted continuous problem to fall in Class B rather than Class A. The combinatorics in ICE are not primarily caused by the number of named bidders; they live in bundles, interval-choice trees, and the number of goods. A finite discrete exchange embeds by giving each original bidder its own type and mass, so the known winner-determination hardness is not expected to disappear merely because mass is divisible. But this boundary makes the mirror interesting: for unit-demand types, structured TBBL trees, or other classes with polynomial pricing oracles, Continuous ICE-Welfare Clearing may become a genuine Class A configuration-LP problem. The paper’s pricing and constraint-generation machinery gives a concrete route to studying that boundary.

The main follow-up questions are whether the type-level process has a complexity bound depending on \(\tau\), tree size, goods, and input bit length rather than the population size; which TBBL subclasses admit efficient separation; how the paper’s \(n\)-dependent approximation bounds normalize when total population mass is \(1\); and whether threshold payments and budget balance have a clean mass-scaled analogue.

The weakest point is that Theorem 6 is a convergence and approximation theorem, not a polynomial-time complexity classification. It assumes straightforward bidders, lets \(\epsilon\) tend to zero, and relies computationally on MIPs. Moreover, the continuous theorem itself is not proved in the paper: the type-weighted lift and the scale-normalized efficiency bound would be new work. That is a real gap, but it is precisely the kind of gap a continuous-computational mirror should expose. The proposed question preserves ICE’s underlying combinatorial exchange, linear prices, valuation elicitation, and welfare objective while replacing redundant named bidders by a genuine distribution over complete bidder types. It is therefore a credible continuous mirror, even if its eventual classification is likely to be “hard in full generality, tractable for identifiable pricing subclasses.”