| paper | d4-conf-ijcai-2018-0899 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given a finite support of complete trader types with rational masses \(\mu_t\), explicit gross-substitutes valuations, and integral bundles, compute a price vector \(p\) and type-level allocation masses \(y_{t,a}\) that clear every good, maximize total gain from trade, and use only actions maximizing each type’s gain net of prices; characterize the running time in the number of goods, support size, input bit length, and valuation-table size.
A gross-substitutes market over a distribution of complete trader types. Each variable \(y_{t,a}\) assigns mass of type \(t\) to an integral bundle action \(a\); the objective maximizes aggregate gain from trade, subject to each type’s mass being allocated and total net trade being zero. A supporting price vector \(p\) makes every action used by positive mass optimal for its type.
Theorem 2’s finite-market rate depends on sampling fluctuations that disappear under exact mass splitting, so this mirror does not transfer that rate.
fatal: False
Covers Theorem 2’s gain-from-trade guarantee in the mass-market limit; leaves out its finite-market sampling rate and Theorem 1’s truthfulness result.
The strongest mirror is Continuous MIDA for computing a market-clearing trade. The paper gives no named NP-hardness or P-versus-NP result; its computational anchors are mechanism results. I would anchor this case on Theorem 2, proved in the paper’s Section 3.
A type is a complete trader description: buyer or seller, gross-substitute valuation over bundles, and, for a seller, initial endowment. Let \(\mu_t\) be the mass of type \(t\), with \(\sum_t\mu_t=1\), and let \(N\) scale the population, so type \(t\) has mass \(N\mu_t\). A plausible regime is a large exchange for substitute medicines, with many patients and suppliers who share standardized valuation and endowment profiles: perhaps \(N\) in the hundreds of thousands and support size \(\tau\) in the hundreds or thousands. The repeated contracts and profiles make the types plausible; if each trader instead has unique terms, then \(\tau\) may be close to \(N\), and the high-multiplicity case is less useful.
Individuals still trade integral bundles. What can be fractional is the *type-level allocation*: mass of one type can be assigned across different bundles, as when otherwise identical patients receive different integral bundles by lottery. Let \(a\) denote a type’s net trade vector: \(a=X\) for a buyer acquiring bundle \(X\), and \(a=-X\) for a seller supplying \(X\). Let \(g_t(a)\) be that trader’s gain before money changes hands. The continuous optimization problem is:
\[ \max_{y\ge 0}\ \sum_{t,a} y_{t,a}g_t(a) \quad\text{subject to}\quad \sum_a y_{t,a}=N\mu_t\ \ \forall t,\qquad \sum_{t,a}y_{t,a}a=0. \]
Here \(y_{t,a}\) is the mass of type \(t\) taking action \(a\); the last constraint clears every good. A solution to Continuous MIDA Equilibrium Computation must provide a price vector \(p\) and such an allocation \(y\), with every action used by positive mass maximizing \(g_t(a)-p\cdot a\) for that type. Payments at those prices balance, and the allocation maximizes gain-from-trade. Thus goods remain indivisible for each person; the fractional quantity is an aggregate of agents.
Theorem 2’s finite-market anchor says: if all traders have gross-substitute valuations, MIDA’s expected competitive ratio is at least
\[
1-\frac{18M^{2G+2}c\ln(10Gk_{\max})}{\sqrt{k_{\max}}}
-o(1/k_{\max}),
\]
where \(G\) is the number of goods, \(M\) the maximum number of units of one good held or traded by one trader, \(k_{\max}=\max_x k_x\), \(k_{\min}=\min_x k_x\), and \(c=k_{\max}/k_{\min}\). This is proved here, not cited from another source. With \(G\), \(M\), and \(c\) bounded, the bound tends to \(1\) as the market grows.
The continuous question preserves that market and its objective. Split each type’s mass equally between two halves, compute a Walrasian price in each, and trade in each half at the other half’s price. Because both halves now have exactly the same type distribution, they can use the same market-clearing price and allocation. Gross substitutes supports a Walrasian equilibrium, so this mass version can achieve the maximum gain-from-trade. A prover could be asked to classify the exact computation’s running time in \(G,\tau\), the bit length of the rational masses and valuations, and the bundle representation. With explicit bundle-value tables, the allocation problem is a finite LP over type–bundle pairs; I would expect Class A in that representation. Succinct valuation or demand-oracle access raises a separate pricing and separation question.
This mirrors Theorem 2’s welfare guarantee, not Theorem 1’s truthfulness result. I would not add truthfulness to this problem: the paper’s guarantee in Theorem 2 does not require single-good sellers, while its truthfulness theorem does. A truthful continuum analogue would be a separate question.
The weak point is that exact mass splitting removes the sampling fluctuations that drive Theorem 2’s finite-market analysis. The continuous equilibrium may therefore be a simpler limit of the authors’ problem, rather than a new hard algorithmic question. Still, the mirror is about the population: it groups traders by their full market-relevant type, keeps individual bundles integral, and asks for a computation over the resulting mass distribution. Its next questions are whether the exact solver remains efficient for succinct gross-substitute valuations, how to round its allocation for finite high-multiplicity markets, and whether additional assumptions can recover truthfulness for sellers who trade several goods.
The proponent’s market is a sensible high-multiplicity regime: many traders can share the same gross-substitute valuation and endowment. I would not object to that modeling choice. The problem is that the anchor, Theorem 2, is an approximation guarantee for a randomized mechanism, not a computational-complexity result. None of Theorems 1–3 classifies the running time or complexity of a computational problem.
Grant the proposed continuous model. Its LP is a natural way to compute an optimal mass allocation, but it changes the target: it asks for Walrasian welfare maximization, while Theorem 2 analyzes MIDA’s expected gain-from-trade under random partitioning and trading. For fixed \(G\) and \(M\), the LP has \(O(\tau(M+1)^G)\) type–bundle variables and \(O(\tau+G)\) constraints when valuations are given explicitly. Its dual supplies supporting prices. The paper already notes that gross-substitute valuations admit a Walrasian equilibrium and that one can find it efficiently. With succinct valuations, the remaining difficulty is the demand or pricing problem for each type; population mass enters as coefficients. Any new complexity result would therefore depend chiefly on the valuation representation, not on continuizing the society.
There is also a specific collapse in this anchor. Splitting each type’s mass equally makes the two halves identical, removing the sampling fluctuations that drive Theorem 2’s analysis. The proposed LP can return an optimal market-clearing allocation at any scale. That is a useful observation about the continuous economy, but it no longer studies MIDA’s finite-sample guarantee. The stronger alternative—retaining MIDA’s truthfulness and strong budget balance while asking for an exact continuum analogue—runs into the mechanism’s individual-level structure: reports affect queue positions and outcomes. In an atomless population, one person’s report does not change the aggregate distribution, so that strategic content disappears unless finite agents and their sampling effects are restored.
A direct mechanism for atomless traders could still be worth studying, with a carefully defined incentive notion. But it would be a different mechanism-design question, and its results would not classify the computation behind this paper’s theorems. Restoring the theorem’s finite-agent incentives and random fluctuations brings back a high-multiplicity discrete market, which is a valid regime but not the continuous mirror proposed here.
So I would argue against giving this paper a ChoCo mirror slot, on a limited basis: its best proposed mirror replaces the paper’s central mechanism guarantee with a familiar equilibrium computation, and preserving the guarantee’s strategic content requires reintroducing finite agents. This is not an airtight claim that no useful continuum question can be posed; it is a case that the proposed anchor does not open a substantial new computational question about the continuous population.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.