| paper | d4-conf-atal-2021-0013 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.3
Given goods \(G\), a finite type support \(T\) with rational masses \(\mu_t\), budgets \(b_t\), and desired bundles \(D_t\), rational per-capita supplies \(q_g\), and threshold \(\kappa\), does there exist a price vector \(p\geq 0\) and nonnegative masses \(x_{t,S}\) assigned to integral bundles \(S\subseteq G\) such that \(\sum_S x_{t,S}=\mu_t\), \(\sum_{t,S:g\in S}x_{t,S}\leq q_g\), every bundle receiving positive mass is affordable and utility-maximizing for its type under \(v_t(S)=1\) iff \(D_t\subseteq S\), and \(\sum_{t,S}x_{t,S}v_t(S)\geq\kappa\)?
Types carry rational mass, budget, and desired bundle. Each individual receives a whole bundle, while \(x_{t,S}\) records aggregate mass; per-capita inventory \(q_g\) constrains the mass assigned each good, and prices support each type's demands.
The mirror covers Theorem 5.3's equilibrium welfare-threshold problem for single-minded markets. It leaves the paper's PAC sample-learning results and its other valuation classes aside.
I would build the positive case around Theorem 5.3, and only that anchor. It says that deciding whether a single-minded market has an equilibrium with total welfare at least \(K\) is NP-complete. The paper proves this for its pairwise-distinct-budget setting, building on the equal-budget hardness cited from Brânzei et al. [13]. This is an exact equilibrium-computation result, though it is ancillary to the paper’s main focus on learning from samples.
A direct population mirror is the Single-Minded Mass-Equilibrium Welfare Threshold problem. Its input is a finite support \(T\) of buyer types, each with rational mass \(\mu_t>0\), budget \(b_t\), and nonempty desired bundle \(D_t\subseteq G\), where \(\sum_{t\in T}\mu_t=1\). Each type has the same single-minded valuation as in the paper: \(v_t(S)=1\) if \(D_t\subseteq S\), and \(0\) otherwise. The input also gives rational per-capita supplies \(q_g\) for goods \(g\in G\) and a welfare threshold \(\kappa\).
A solution is a price vector \(p\geq0\) and masses \(x_{t,S}\geq0\) assigned to integral bundles \(S\subseteq G\). They must satisfy \(\sum_{S\subseteq G}x_{t,S}=\mu_t\) and \(\sum_{t,S:g\in S}x_{t,S}\leq q_g\). Whenever \(x_{t,S}>0\), bundle \(S\) must be affordable at \(p\) and maximize \(v_t(R)\) among all affordable bundles \(R\). The question is whether such an equilibrium exists with welfare \(\sum_{t,S}x_{t,S}v_t(S)\geq\kappa\). Individuals still receive whole bundles; only the type’s aggregate assignment is measured as mass.
This mirror has a concrete discrete bridge. Given a paper instance with \(n\) buyers, make each buyer a type of mass \(1/n\), set \(q_g=1/n\) for each good, and set \(\kappa=K/n\). Any discrete equilibrium gives a mass equilibrium. Conversely, single-minded utility prevents mass splitting from creating partial welfare: at fixed prices, if \(D_t\) is affordable, the whole type must receive utility \(1\); if it is unaffordable, no affordable bundle can contain it and the type’s utility is \(0\). Thus the continuum decision reproduces the discrete welfare threshold on these instances. I expect NP-hardness to transfer, with the general problem NP-complete: a proposed set \(U\subseteq T\) of served types and prices can certify an answer. For a fixed \(U\), the required stock constraints and affordability conditions are linear.
The market regime is a large recurring allocation market—say, housing or standardized resource bundles—with many households but a modest number \(\tau=|T|\) of recurring combinations of budget and desired bundle. Mass records their population shares; inventory scales with population and is recorded per capita. The type description includes every feature this problem uses, so aggregation does not erase relevant preferences or budgets. The mirror’s likely classification is Class B in general, because it contains the discrete instances, while also being FPT in \(\tau\): enumerate the \(2^\tau\) possible served-type sets and check each set’s pricing and stock constraints. That makes the low-support regime a substantive algorithmic question, even though Theorem 5.3’s hardness instances have \(\tau=n\).
I think the authors would recognize this as the continuous-population version of Theorem 5.3’s welfare-constrained equilibrium problem. It covers that result, not the paper’s PAC learning framework: its sample distribution is over observed bundles, not over buyers, and treating that distribution as population mass would be a different, out-of-scope continuization.
The weak point is that the paper’s distinct-budget assumption can work against a high-multiplicity scenario: if budgets are genuinely individualized, budget is part of the type and \(\tau\) can grow with \(n\). Repeated-budget cohorts are natural for the proposed market, and the paper itself treats distinct budgets as a tie-breaking convenience, but the exact hardness theorem does not establish hardness when \(\tau\ll n\). Whether the welfare problem remains hard for restricted support—or instead becomes efficiently solvable beyond the FPT enumeration bound—is the follow-up I would want the programme to ask.
Theorem 5.3 is the proponent’s strongest anchor, and I can’t honestly rule out its best mirror. Its welfare-threshold question has a natural mass version: recurring buyer types have rational population shares, budgets, and desired bundles; supplies scale per capita; and the question is whether an equilibrium serves enough mass. The discrete market maps cleanly into a special case with one type per buyer and correspondingly scaled supplies. That the resulting problem may be hard, or easier when the support is small, is not a reason to dismiss it.
The strongest negative is narrower: the paper’s NP-completeness result does not establish hardness in a genuine high-multiplicity regime. Its buyers have pairwise distinct budgets, and budget is part of a complete type. So the theorem’s instances have \(n\) distinct types for \(n\) buyers. Repeating buyers while preserving their types requires changing the distinct-budget assumption. The paper calls that assumption a way to induce priority and ensure equilibrium existence, which makes a repeated-budget variant plausible—but it is still a variant whose complexity the theorem does not settle. Conversely, perturbing budgets to preserve the paper’s assumption makes otherwise identical buyers different types, so it does not establish a small-support result.
That weakens the claimed bridge from this theorem to an algorithmic gain from continuization. But it does not defeat the mirror: the repeated-type market is recognizable and well-posed, and investigating whether its welfare problem is tractable at low support could be worthwhile in its own right. The honest negative case is therefore weak. I can challenge how directly Theorem 5.3 supports the high-multiplicity question, but not convincingly argue that no worthwhile continuous mirror exists.
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.