| paper | d4-conf-wine-2016-0001 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.2
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\), item supplies \(q_j\), and types \(t=(S_t,v_t,b_t)\) with \(b_t \ge v_t\), compute in time polynomial in \(m,\tau,L\) item prices \(\rho_j\) and masses \(z_{t,X}\) assigned to integral bundles \(X\subseteq S_t\). Require \(\sum_X z_{t,X}=\mu_t\), \(\sum_{t,X:j\in X}z_{t,X}\le q_j\), and every bundle receiving positive mass to maximize that type’s affordable utility at \(\rho\). The revenue must be at least \(\mathrm{OPT}_{BP}/4\), where \(\mathrm{OPT}_{BP}\) is the maximum revenue of a feasible, individually rational, bundle-price envy-free allocation on the same instance.
A society is a distribution over \(\tau\) campaign types, with per-capita supply \(q_j\) for each item class. Assign mass \(z_{t,X}\) to integral bundles \(X\); types may split mass among utility-maximizing bundles. Find item prices and a feasible assignment earning at least \(\mathrm{OPT}_{BP}/4\) for \(b_t \ge v_t\).
The \(1/4\) guarantee may lift through a routine capacitated-matching compression, limiting the new computational insight; this bounds the likely research yield but does not undermine the question.
fatal: False
The mirror covers Theorem 3.2’s \(b_t \ge v_t\) approximation guarantee; Theorem 4.1 gives a second, less secure \(b_t < v_t\) mirror. Theorem F.1 concerns fixed-price distortion, while the general inapproximability cited from [11] and incentive-compatible mechanisms are not results established here.
The strongest positive case is a high-multiplicity online advertising market. Let each item class \(j\in J\) represent an opportunity such as a publisher and placement in a planning period. A buyer type is \(t=(S_t,v_t,b_t)\): the opportunities the campaign targets, its value per opportunity, and its budget. In a market with \(N\) campaigns, type \(t\) has mass \(N\mu_t\), and class \(j\) has supply \(Nq_j\). Campaigns with the same preferences, value and budget are indistinguishable; \(N\) can be very large while the number \(\tau\) of distinct types stays moderate. Per-capita supply is a natural co-modification here: impression inventory grows with the market, and each campaign can receive an integral bundle even when the cohort allocation is fractional.
More precisely, let \(\sum_t\mu_t=1\), and let \(z_{t,X}\) be the mass of type \(t\) assigned bundle \(X\subseteq S_t\). Feasibility requires \(\sum_{t,X:j\in X}z_{t,X}\le q_j\). Each campaign gets an integral bundle; \(z_{t,X}\) records the share of its type receiving that bundle. Under item prices \(\rho_j\), a campaign pays \(\sum_{j\in X}\rho_j\) and has utility \(v_t|X|-\sum_{j\in X}\rho_j\), provided its payment is at most \(b_t\). A bundle-price menu instead offers contracts \((X,p_X)\), and assigned campaigns must prefer their contract to every other offered contract. Revenue is the mass-weighted sum of payments. Write \(\mathrm{OPT}_{BP}\) for the best revenue under bundle-price envy-freeness.
Theorem 3.2 (proved here) is my lead anchor. It says that Algorithm 1 produces an item-price envy-free outcome with revenue at least one quarter of the optimal bundle-price envy-free revenue when every buyer has \(b_i\ge v_i\). The corresponding continuous problem is: given rational \(\mu_t,q_j,v_t,b_t\) and \(b_t\ge v_t\) for every type, find an item-price envy-free mass allocation with revenue at least \(\mathrm{OPT}_{BP}/4\). The complexity question is whether this can be done in time polynomial in \(m,\tau\), and the input bit length. I expect it to be tractable. The paper’s ascending-price stages and matching arguments have a plausible mass version using capacitated flows: a type’s mass can be split among integral bundles, and rational capacities are part of the input. This is a question about the underlying revenue problem, not an encoding.
Theorem 4.1 (proved here) gives a separate, useful mirror for the other budget regime. It says that Algorithm 4 is pairwise envy-free and earns at least one quarter of optimal envy-free revenue when every buyer has \(b_i<v_i\). Its continuous problem is: on the same mass-and-supply input, with \(b_t<v_t\) for every type, find a pairwise envy-free bundle-price allocation earning at least \(\mathrm{OPT}_{BP}/4\). I again expect tractability, but this is the less secure of the two algorithmic mirrors: the proof’s partitions and comparisons between buyer groups must survive when a type’s mass can be split across contracts.
A complementary lower-bound anchor is Theorem F.1 (proved here). It says that no fixed-price scheme can approximate optimal envy-free revenue within a factor better than \(O(\log n)\) in the worst case; its construction gives a ratio of order \(1/\log n\). The continuous question is: in a mass market with \(\tau\) types, how well can one common per-unit price for every item class approximate \(\mathrm{OPT}_{BP}\)? The theorem’s construction gives a direct mirror. Use \(n\) types, each of mass \(1/n\), each interested in its own item class with supply \(1/n\), and set \(v_k=b_k=n/(n-k+1)\). Discriminatory prices earn \(H_n\) per capita, while the best single price earns \(1\). Thus the gap is \(\Theta(\log \tau)\). I expect this barrier to persist by embedding the finite construction in the mass model. This is an approximation barrier for a restricted pricing scheme, not an NP-hardness result.
These mirrors fit the authors’ motivating setting: they explicitly discuss advertisers with CPM valuations and budgets buying blocks from publishers. A market with many campaigns in recurring targeting, valuation and budget classes is a credible high-multiplicity regime. The first two questions cover the paper’s two budget-regime approximation results; the third covers its fixed-price limitation. They do not claim to cover all matching-market instances or incentive-compatible mechanisms. The paper’s cited \(\Omega(\min\{n,m\}^{1/2-\varepsilon})\) inapproximability result from [11] is relevant background, but it is not a numbered hardness theorem in this paper, so I do not use it as an anchor.
The weakest point is whether the proofs really lift. In the finite algorithms, envy-freeness and revenue bounds rely on individual buyers and integral matchings. A continuous proof must show that capacitated flows decompose into integral bundles for each agent and that the charging arguments still hold when mass splits among bundles. That seems plausible, especially in the high-budget item-price case, but it is work the mirror must earn. Further questions include whether either \(1/4\) guarantee survives in time polynomial in \(m,\tau,L\), whether exact \(\mathrm{OPT}_{BP}\) is tractable, and whether the cited hardness bound persists when the input is represented by type masses.
The strongest case against these mirrors is that the two approximation theorems may offer little new computational structure. Given rational type masses and per-capita supplies, clearing denominators turns the market into a finite replication of the same buyers and item copies. Theorem 3.2 and Theorem 4.1 then provide the same \(1/4\) guarantees. That does not settle the continuous problem’s bit complexity: the replicated instance can be enormous relative to the binary input. But for Theorem 3.2, the paper’s core operations are matching and price thresholds determined by buyer values and budgets. A capacitated matching formulation looks like a direct route to a running time polynomial in \(m,\tau,L\). If so, the mirror is valid but may amount to a routine compression of an existing algorithm, rather than a new complexity landscape.
Theorem 4.1 is a better target for skepticism because its proof tracks which individual buyers have already received items and partitions buyers by overlapping preference sets. A cohort split across different bundles or histories cannot simply be treated as one buyer with fractional demand. A continuous algorithm would need to preserve integral bundles per person and the envy comparisons across all assigned contracts; a fractional flow alone does not establish that. Still, this is a technical obstacle to the proposed proof, not a reason the type-level problem is ill-posed. The stronger mirror remains recognizable, and its complexity is open under the compressed encoding.
Theorem F.1 is the weakest anchor. Its harmonic construction carries over to masses and gives a \(\Theta(\log \tau)\) gap for common item prices. But that is a pricing-scheme distortion bound, not a complexity result. The construction largely transfers by rescaling, so it says little about what computation becomes harder or easier when the population is continuous. It is poor evidence for the programme’s computational agenda, even though it is a valid continuous question.
The larger objection—that advertisers are too individuated for high multiplicity—also does not hold universally. Exact repetition of targeting sets, values and budgets may be uncommon in some markets, but recurring standardized campaign classes with inventory that grows alongside the audience are plausible. Buyer identity does not enter this paper’s revenue or envy definitions, and the programme explicitly allows supply to scale with population.
So the negative case can argue that the first two mirrors may be incremental and that the third is not really a complexity mirror. It cannot honestly defeat the best versions of the first two on modeling grounds. I would call the case against weak: it questions the likely research yield, but does not support the claim 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.