| paper | d4-conf-ijcai-2015-0557 |
| 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→P discrete result → its continuous mirror
Answer: The continuous revenue-threshold problem is in \(\mathrm P\), with an exact algorithm using \(O(\tau\log(\tau+1)L^2)\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite-support distribution μ over single-minded buyer types \(t=(k_t,w_t)\), with rational masses \(μ_t\) summing to \(1\), and a rational supply \(β\) of units per unit mass, choose a uniform item price \(p\ge 0\) and allocation masses \(x_{t,q}\ge 0\) to maximize revenue \(p\sum_{t,q}q x_{t,q}\). Require Σ_q x_{t,q}=μ_t\), Σ_{t,q}q x_{t,q}\le\beta\), and every quantity \(q\) assigned positive mass to maximize \(v_t(q)-pq\) over integral \(q\ge 0\), where \(v_t(q)=0\) for \(q<k_t\) and \(v_t(q)=w_t\) for \(q\ge k_t\).
An atomless multi-unit market with a finite support of buyer types \(t=(k_t,w_t)\), where μ_t is each type's population mass and β is supply per unit mass. The seller chooses one price per unit and masses of each type to assign each integral bundle size; each buyer must receive a utility-maximizing quantity, and the seller maximizes total revenue.
The mirror covers Theorem 2's single-minded, envy-free item-pricing result. It leaves the paper's general-valuation, pair-envy-free, and bundle-pricing results aside.
The lead mirror is Atomless Envy-Free Item Pricing for Single-Minded Types. Consider a large market with \(N\) buyers and \(M\) identical units of a resource, where \(M/N=\beta\). There are \(\tau\) buyer types. Type \(t\) has mass \(\mu_t\), with \(\sum_t\mu_t=1\), and values receiving at least \(k_t\) units at \(w_t\), but values fewer than \(k_t\) at zero. The seller posts one price \(p\) per unit and wants to maximize revenue while making every buyer’s allocation utility-maximizing.
A solution assigns masses \(x_{t,0}\) and \(x_{t,k_t}\) of each type to receive zero or \(k_t\) units. It must satisfy
\[
x_{t,0}+x_{t,k_t}=\mu_t,\qquad
\sum_t k_t x_{t,k_t}\le\beta,
\]
and any positive assigned mass must receive a quantity that maximizes \(v_t(q)-pq\) over integer quantities \(q\ge 0\). The objective is
\[
\max\ p\sum_t k_t x_{t,k_t}.
\]
The population is continuous; each infinitesimal buyer still gets an integral number of units. Thus the resource remains homogeneous and indivisible at the buyer level. What becomes fractional is the mass of a type receiving a particular bundle.
The anchor is Theorem 2, proved in this paper, not cited as an outside result. It says that EFIP-MUL—revenue-maximizing envy-free item pricing with single-minded valuations and free disposal—is NP-hard, but has an FPTAS. In the paper’s finite model, there are \(n\) buyers, \(m\) homogeneous items, and buyer \(i\) values any bundle of at least \(k_i\) items at \(w_i\), with smaller bundles worth zero. The theorem’s hardness is shown by reduction from Subset Sum; its approximation scheme uses candidate prices and a knapsack FPTAS.
The continuous version has a direct exact solution. For \(p>0\), a type’s only possible demanded quantities are zero and \(k_t\). Set \(\rho_t=w_t/k_t\). If \(p<\rho_t\), every buyer of type \(t\) strictly prefers \(k_t\); if \(p>\rho_t\), every one strictly prefers zero; and at \(p=\rho_t\), they are indifferent and their mass can be split between the two. For a candidate price \(p\), define
\[
D_{>}(p)=\sum_{\rho_t>p}\mu_t k_t,\qquad
D_{=}(p)=\sum_{\rho_t=p}\mu_t k_t.
\]
If \(D_{>}(p)\le\beta\), the best revenue at that price is
\[
p\left(D_{>}(p)+\min\{D_{=}(p),\,\beta-D_{>}(p)\}\right).
\]
If strict demand exceeds supply, that price is infeasible. Between successive values of \(\rho_t\), demand is fixed and revenue increases with price, so it suffices to check the \(\tau\) ratios. Sorting and evaluating them takes time polynomial in \(\tau\) and the input bit length. I therefore expect this mirror to be tractable: the continuous model replaces the finite subset-sum choice among indifferent buyers with fractional rationing of the indifferent type mass.
A plausible regime is a large platform selling identical reserved compute units to many recurring customer classes. A class is described by its requested minimum quantity \(k_t\) and its total willingness to pay \(w_t\). There may be millions of buyers, but only dozens or hundreds of recurring classes, each with many members, and total supply scales with the population. The type captures everything the pricing problem uses; the result does not depend on named buyers. This is a recognizable version of the paper’s same seller, resource, price, revenue objective, and envy-freeness condition. High-multiplicity pricing supports the case for the mirror rather than colliding with it. The mirror covers Theorem 2’s single-minded, envy-free item-pricing result; it does not claim to cover the paper’s pair-envy-free or bundle-pricing results.
There is also a concrete bridge back to finite instances. At a continuous optimum, strict-demand types must be served in full; only types at the chosen price threshold need fractional rationing. For a finite market with \(N\mu_t\) buyers of each type, rounding the number served at a tied type down to an integer loses fewer than \(k_t\) units for that type and preserves envy-freeness. When the \(k_t\) are bounded, this gives an additive loss of at most \(p\sum_{\rho_t=p} k_t\) units’ worth of revenue, rather than a per-capita loss that persists as \(N\) grows. It does not solve the finite exact problem: selecting whole indifferent buyers is precisely where Subset Sum can remain.
My weakest point is that atomless rationing is not literal for a small cohort: one cannot serve \(3.7\) buyers. It is credible when each type represents a large cohort, which is the regime this mirror asserts. A natural follow-up is to characterize the exact gap between fractional rationing and whole-buyer selection in terms of \(\tau\) and the largest \(k_t\), and to ask whether that structure yields fixed-parameter algorithms for the finite problem.
The strongest case against this mirror is that its computational payoff may be too slight for ChoCo. Theorem 2 is a real anchor: it proves NP-hardness and an FPTAS for envy-free item pricing with single-minded buyers. But for the proposed atomless version, each type’s ratio \(w_t/k_t\) determines its behavior at every positive price. Types above the price must be served, types below it must be left out, and only types exactly at the price can be rationed. Checking those finitely many ratios gives the optimum. There is no difficult pricing oracle or broader continuous-optimization machinery here; the gain comes entirely from allowing fractional rationing among indifferent buyers.
A more careful scenario does not remove that concern. Large cohorts sharing exact package sizes and willingness to pay make a sensible high-multiplicity market, and the seller can ration tied cohorts without tracking identities. But that makes the answer almost immediate. If instead the buyers have a genuinely continuous spread of values, the finite-support type list disappears and the input becomes a distributional model; that may be interesting, but it is a different computational question. The finite bridge also has limited reach: the stated additive rounding bound is useful when the support and bundle sizes stay fixed, but need not remain small if they grow with the market. Meanwhile, the paper already gives a finite-market FPTAS.
That is a case for low research priority, not a fundamental objection to the mirror. The single-minded, envy-free item-pricing version is a coherent population continuization, and the tractable answer is itself a legitimate result under the programme’s standards. I cannot honestly claim this anchor has been defeated; the negative case is weak precisely because a plausible high-multiplicity regime survives.
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.