| paper | d4-conf-sigecom-2011-0022 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: For every fixed \(c\ge 1\), no polynomial-time algorithm produces an explicitly represented feasible mass allocation with \(W(x)\ge\mathrm{OPT}/2^{m^c}\), assuming \(\mathrm{NP}\not\subseteq\bigcap_{\varepsilon>0}\mathrm{BPTIME}(2^{n^\varepsilon})\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 17
statement extracted from the paper’s text layer
Given finitely many consumer types \(t\) with rational masses \(\mu_t\), finite goods sets \(V_t\), compactly represented monotone supermodular utilities \(F_t:2^{V_t}\to\mathbb{R}_+\), prices \(p_t\), and budgets \(b_t\), compute a utility-maximizing mass allocation \(x_{t,S}\) over integral bundles \(S\subseteq V_t\) satisfying \(p_t(S)\le b_t\), with \(\sum_{S:p_t(S)\le b_t}x_{t,S}=\mu_t\) and \(x_{t,S}\ge0\). In the one-type, unit-price case with \(b_t=k\), determine the complexity of maximizing \(\sum_{S:|S|\le k}x_{t,S}F_t(S)\).
A finite-support population of consumer types, each specified by its goods, utility, prices, and budget; rational mass \(\mu_t\) is assigned across feasible integral bundles \(S\) via \(x_{t,S}\), maximizing aggregate utility \(\sum_t\sum_S x_{t,S}F_t(S)\). There is no shared supply constraint, and the one-type unit-price instance embeds Theorem 17.
The mass-allocation problem separates by type, so multiplicity only scales each type’s individual optimum; its population interpretation depends on accepting a large cohort with identical graph-encoded preferences.
fatal: False
The mirror covers Theorem 17’s budgeted supermodular utility maximization result, restricted to a population of consumer types with integral bundles. It leaves the revealed-preference rationalization results, Walrasian equilibrium rationalizability, and the general framework aside.
My lead is Mass Supermodular Consumer Choice\(_\infty\), a high multiplicity version of the paper’s budgeted utility maximization problem.
The regime is a large population of households choosing from the same catalogue of indivisible goods under standardized budgets. A type is the complete consumer profile relevant to choice: its goods \(V_t\), monotone supermodular utility \(F_t\), prices, and budget. Think of many households in each of a small number \(\tau\) of standardized purchasing segments. The number of households is large relative to \(\tau\); each household still receives an integral bundle, though the fraction of a type assigned to each bundle can be fractional.
Here is the continuous problem. The input is a finite support of types with rational masses \(\mu_t\), summing to \(1\). For the anchor below, use unit prices and a cardinality budget \(k_t\). Let \(x_{t,S}\) be the mass of type \(t\) receiving bundle \(S\). Choose \(x\) to maximize aggregate utility:
\[ \max \sum_t \sum_{\substack{S\subseteq V_t\\ |S|\le k_t}} x_{t,S}F_t(S) \quad\text{subject to}\quad \sum_{\substack{S\subseteq V_t\\ |S|\le k_t}}x_{t,S}=\mu_t,\qquad x_{t,S}\ge 0. \]
A solution is the mass assigned to each feasible bundle; it also determines aggregate demand. This asks for the population’s utility maximizing choices at fixed prices and budgets. It does not ask for a Walrasian equilibrium, which the paper explicitly says is a separate computational question.
My anchor is Theorem 17, proved in this paper. It states that for every fixed constant \(c\ge 1\), there is no polynomial time \(2^{n^c}\)-approximation for maximizing a monotone supermodular function subject to a cardinality constraint, unless \(NP\subseteq\bigcap_{\epsilon>0}\mathrm{BPTIME}(2^{n^\epsilon})\); here \(n=\log_2|\operatorname{dom}(f)|\), the size of the function’s ground set. The theorem’s proof builds hard utilities from graph instances, so the mirror can use that same compact graph based representation of the utility.
The one type case, with \(\mu_t=1\), embeds the anchored problem exactly. Any feasible mass allocation is a weighted average of utilities of feasible bundles, so its value cannot exceed the best bundle’s value; assigning all mass to that bundle attains the discrete optimum. Conversely, from an explicitly represented approximate mass allocation, some bundle in its support has utility at least the allocation’s average utility. Thus an approximation algorithm for the continuous problem would give one for the discrete problem with the same guarantee. The LP has a column for each feasible bundle, and its pricing question is precisely which bundle maximizes \(F_t(S)\). I expect hardness transfers: the difficulty is in the goods and their complementarities, not in the number of consumers.
The paper’s discussion of multiple utility maximizing agents in its Walrasian section supports this as a natural regime for the authors: individual consumers face prices and budgets, and aggregate demand is the sum of their choices. This mirror covers the computational task of finding those choices for a high multiplicity population; it does not claim to continuize every result in the paper.
The weakest point is that the population does not couple consumers through a shared supply constraint, so the continuous mass variables do not create a new optimization tradeoff. That is deliberate: adding a shared constraint would change the consumer choice problem, and Theorem 17 would no longer establish the same hardness. Here the mirror preserves each consumer’s integral choice and budget while making the population itself continuous. It is a narrow mirror, but a credible one, and its hardness result marks a clear place where continuization does not make the problem tractable.
Theorem 17 is a real complexity result, so the case against cannot be that there is nothing to mirror. The difficulty is that its proposed mirror gives the population no computational role.
For each type \(t\) with \(\mu_t>0\), the displayed optimization puts all its mass on bundles maximizing \(F_t(S)\). There is no constraint linking one type’s choice to another’s, and no effect of the mass distribution on any type’s demand. The variables \(x_{t,S}\) describe a planner assigning consumers to bundles; under the stated objective, that assignment reduces to solving each type’s individual demand problem. Fractional mass can split among bundles only when the type is indifferent. This makes the aggregate formulation a poor mirror of a computational question about a continuous society: the population measure contributes weights, but nothing for those weights to govern.
The more compelling population model would make choices interact through scarce supply or market clearing. That would give the masses a real role, but it changes the problem. The paper discusses Walrasian equilibrium and explicitly says it does not study the computational complexity of finding one. A supply-constrained welfare problem or a continuum equilibrium problem may be worth studying in its own right; it is not a continuous version of Theorem 17’s budgeted maximization result.
A richer finite set of consumer types does not fix the mismatch. Without shared constraints, each type still solves its own problem independently. With shared constraints, the model has moved to the collective allocation problem. And the proposed one-type case, which carries the hardness, asks a large cohort to share the same graph-encoded utility over the same catalogue. That is formally coherent, but its population is just repeated copies of the hard consumer instance.
This is the strongest negative case, and it has a limit: the clone regime is not impossible or incoherent. Under the programme’s definition of a type, identical consumers can form a high-multiplicity population, and the question of computing their common demand is well posed. Saying that the measure factors out risks dismissing a valid mirror merely because its answer may reduce to the individual problem. So the objection is strongest against the claimed *population* contribution of this formulation; it does not establish that no worthwhile continuous mirror of the paper 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.