| paper | d4-conf-ijcai-2018-0732 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: The decision problem is in \(\mathrm P\), with bit-operation running time \(O((\tau\log(\tau+1)+|A|+1)L^2)\), independent of the numerical value of \(m\) except through \(L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), a directed visibility graph \(H=(T,A)\), single-minded valuations \(v_t\) with preferred integral bundle sizes \(q_t\le M\), and rational supply \(B\) per unit population, choose nonnegative prices \(p_t\) and nonnegative masses \(y_{t,j}\) assigned integral bundle sizes \(j\in\{0,\ldots,M\}\) to maximize \(\sum_{t,j} y_{t,j}v_t(j)\). Require \(\sum_j y_{t,j}=\mu_t\), \(\sum_{t,j}j y_{t,j}\le B\), \(p_t\le p_s\) for each \((t,s)\in A\), and positive \(y_{t,j}\) only when \(j\) maximizes \(v_t(j)-p_tj\); characterize the complexity in \(M, |T|, |A|\), and input bit length, or decide whether the optimum is at least a given rational \(K\).
Group buyers with identical valuations and price-visibility relations into types with masses \(\mu_t\). Assign a price to each type and mass to integral bundle sizes, allowing a type's mass to split only among utility-maximizing choices; maximize aggregate welfare subject to fair prices and supply \(B\) per unit population.
The mirror covers only the single-minded social-welfare clause of Theorem 3 over buyer-type masses; it leaves the revenue clause, approximation bounds, general valuations, and topology-restricted algorithms unmirrored.
A credible mirror is the single-minded social-welfare problem, where the population becomes a distribution over buyer cohorts. I would name it Continuous Cohort Fair-Welfare Pricing.
The anchor is Theorem 3, proved in this paper by a reduction from Densest \(k\)-Subgraph. Its full claim is that both \((\mathrm{SINGLE},\mathrm{WELFARE})\)-pricing and \((\mathrm{SINGLE},\mathrm{REVENUE})\)-pricing are strongly NP-hard. The reduction creates a buyer for each vertex and edge of a graph, gives vertex buyers a large preferred bundle and edge buyers a one-item demand, and links each endpoint buyer to its edge buyer in the social graph. The supply is chosen so that selecting vertex buyers and serving their eligible edge buyers encodes a dense \(k\)-vertex subgraph. I use the welfare clause as my lead; the mirror below does not claim to cover the revenue clause.
An instance has a finite set \(T\) of types, rational masses \(\mu_t\) summing to \(1\), single-minded valuation functions \(v_t\), a directed graph \(H=(T,A)\), and a rational supply \(B\) per capita. A type is complete for this market: it specifies both the buyer’s valuation and the buyer’s price-visibility pattern. An arc \((t,s)\) means buyers of type \(t\) can see the offers to type \(s\). The decision variable is a price \(p_t\) per item for each type, together with \(y_{t,j}\), the mass of type \(t\) receiving \(j\) items. Require
\[
\sum_{j=0}^{M} y_{t,j}=\mu_t,\qquad
\sum_{t\in T}\sum_{j=0}^{M} j\,y_{t,j}\le B,\qquad
p_t\le p_s\ \text{for every }(t,s)\in A,
\]
and require \(y_{t,j}>0\) only when \(j\) maximizes \(v_t(q)-p_tq\) over \(q\in\{0,\ldots,M\}\). The question is whether such prices and allocations can achieve per-capita welfare
\[
\sum_{t\in T}\sum_{j=0}^{M} y_{t,j}v_t(j)\ge K.
\]
The masses may split across bundle sizes only when those sizes are tied as utility-maximizing choices. Each person still receives an integral bundle; the aggregate allocation and supply are continuous. The natural complexity parameters include \(M\), the support size \(\tau=|T|\), the input bit length \(L\), and \(|A|\).
A plausible regime is a large wholesale or commodity market with many buyers in recurring procurement cohorts. Members of a cohort have the same demand schedule and the same access to other cohorts’ offers; their mass records the cohort’s share of the customer base. The number of people can be far larger than the number of cohorts. The graph in Theorem 3’s reduction can remain on the cohort types, while each role is repeated many times. Its support can grow with the reduction input, so I am not claiming hardness at fixed \(\tau\). Per-capita supply is the natural co-modification: if a discrete market has \(n\) buyers and \(m\) items, its supply becomes \(m/n\).
This remains recognizably the authors’ pricing problem: same multi-unit demand, price per copy, envy-free choice, supply constraint, and fairness along information links. It aggregates duplicate buyers; it does not make the items divisible. The paper’s related work on homogeneous multi-unit markets supports the plausibility of repeated buyer profiles; it is not a collision with this continuous-population question.
My tentative prediction for the welfare version is Class A. A mass allocation and linear welfare objective may allow the single-minded choices to be handled by a piecewise-linear or LP-style method over type masses. The difficult step is expressing demand support and the type-price inequalities together; that is the central question for a prover, not an established algorithm. Further questions are whether the runtime can be polynomial in \(M,\tau,L\), whether graph structure changes the answer, and whether any resulting continuous solution can be rounded to a discrete high-multiplicity market with useful additive error.
The weakest point is also clear: the Densest \(k\)-Subgraph reduction uses discrete buyer choices, while a continuous cohort can split its mass at an indifference price. That may erase the reduction’s selection gadget, so Theorem 3 does not transfer by itself. If so, the tractability would be a substantive continuization result. The mirror still deserves study even if hardness survives: its type-level price and mass-allocation question is a well-posed computational problem the paper’s finite-buyer analysis does not answer.
The strongest case against the proposed mirror is that the reduction in Theorem 3 gets its combinatorial structure from the buyer graph. Its Densest \(k\)-Subgraph construction gives roles to individual vertex and edge buyers, with the incidence graph carrying the hard instance. To represent that faithfully, a continuous model must include those roles in its type support. For a general graph, the support can grow with the whole reduction instance; identical valuations alone do not create interchangeable types when buyers have different network roles.
That objection weakens the claimed computational payoff, but it does not defeat the mirror. Replicate each role many times and connect the resulting cohorts according to a type-level graph. This yields high multiplicity while retaining the market’s core ingredients. It imposes a block-structured social graph, which may be restrictive, but cohort-to-cohort visibility is plausible for some markets. A more general model could record masses of valuation-and-network types and their link structure; that is harder to compress, yet remains a well-posed population question.
The paper’s price and allocation objectives aggregate over buyers, so they do not require tracking who receives each copy. Fractional cohort allocation at an indifference price is also a natural high-multiplicity representation. Earlier work on envy-free pricing in large markets confirms that continuous population models are sensible in adjacent pricing problems, though it does not answer this paper’s graph-constrained discriminatory-pricing question ([Anshelevich et al., *Envy-Free Pricing in Large Markets*](https://doi.org/10.1145/3105786)).
So the negative case is limited: Theorem 3’s reduction does not itself establish a meaningful continuous advantage, and the most faithful model may preserve a large graph as part of its input. But neither point shows that no worthwhile mirror exists. The sole anchor is a named computational hardness result, and a repeated-cohort version of its pricing problem is coherent. I cannot honestly defeat it; the case against is weaker than the case for.
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.