| paper | d4-conf-ijcai-2016-0264 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Achievable: a strategyproof rule guarantees \(W(A)\geq0.67776W^*\) for every input society. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 6
Given a finite support \(\mathcal P\) of bilateral utility-pair types \(p=(u_1^p,u_2^p)\), with rational masses \(\mu_p\) summing to one, and \(m\) divisible items in each cell, output a strategyproof rule and feasible allocations for each supported type such that aggregate welfare is at least \(0.67776\) times \(\sum_{p\in\mathcal P}\mu_p\sum_{j=1}^m\max\{u_{1j}^p,u_{2j}^p\}\).
A continuum of independent bilateral sharing cells: each type \(p\) specifies both agents' normalized utility vectors, and mass \(\mu_p\) is the fraction of cells of that type. Apply the Theorem 6 mechanism in each cell; its allocation variables are the agents' bundles within that cell, and the objective is mass-weighted welfare across supported types.
The masses only average independent two-agent applications; they create no shared feasibility constraint or population-level strategic interaction, so the theorem yields no distribution-specific computation.
fatal: False
The mirror covers Theorem 6's competitive guarantee only. It leaves aside the two-item upper bounds and the Dynamic-Increasing-Price discussion, for which the paper gives no corresponding continuous-population result.
The strongest anchor is Theorem 6 (proved here, using Partial Allocation mechanisms from Cole et al.). It gives a specific mechanism for two agents and any number of divisible items: \(\frac{1029}{4000}\,\mathrm{PA}_{0.421}+\frac{1029}{4000}\,\mathrm{PA}_{1/0.421}+\frac{971}{2000}\,\mathrm{PA}_{\max}\) is strategyproof and at least \(0.67776\)-competitive against the first-best allocation. Here \(\mathrm{PA}_c\) optimizes a product of the two agents’ utilities and then scales their allocations; \(\mathrm{PA}_{\max}\) chooses the higher-welfare outcome between \(\mathrm{PA}_1\) and an equal split. This is a named competitive-ratio result, not a P-versus-NP result; the paper has no comparable hardness anchor.
My lead mirror is the *Continuum of Bilateral Sharing Cells*. Take many independent two-person resource-sharing cells. Each cell has \(m\) divisible items, one unit of each, and two participants with normalized linear utility vectors. A cell type is the ordered pair \(p=(u_1^p,u_2^p)\); the society is a finite support \(\mathcal P\) with rational masses \(\mu_p\) summing to one. Thus \(\mu_p\) is the fraction of cells of that utility-pair type, and clearing the denominators gives an exact finite population of repeated cells. The number of cells can be large while the number \(\tau=|\mathcal P|\) of distinct cell types stays small. This fits a repeated peer-to-peer sharing setting, and each participant remains an individual strategic agent.
An instance consists of \(m\), the rational support \(\mathcal P\), and its masses \(\mu\). A solution is a direct rule \(M\) that takes the two reported utility vectors in a cell and returns bundles \(x_1,x_2\in[0,1]^m\), with \(x_{1j}+x_{2j}\leq1\) for every item. It must make truth-telling a dominant strategy for either participant in every cell. Its population welfare is \(W_\mu(M)=\sum_{p\in\mathcal P}\mu_p\bigl(u_1^p\cdot x_1^M(p)+u_2^p\cdot x_2^M(p)\bigr)\), and the first-best benchmark is \(\mathrm{OPT}_\mu=\sum_{p\in\mathcal P}\mu_p\sum_j\max\{u_{1j}^p,u_{2j}^p\}\). The question is to produce such a rule and its allocations on the supported cell types with \(W_\mu(M)\geq0.67776\,\mathrm{OPT}_\mu\).
Theorem 6 answers this mirror by applying its mechanism independently in each cell. Feasibility and individual strategyproofness hold cell by cell, and summing the per-cell guarantees with weights \(\mu_p\) gives the population guarantee. I expect this fixed-support computation to be Class A: it reduces to evaluating the PA rules on \(\tau\) utility pairs, and their product objectives can be written as concave log-utility objectives over feasible allocation polytopes. Theorem 6 itself does not prove a bit-complexity bound, so that runtime claim would need its own analysis. Follow-up questions include whether a distribution-specific rule can beat \(0.67776\), and whether the guarantee survives when items can be pooled across cells.
The weak point is that the paper studies one two-agent market, while this mirror studies a population of independent markets. The masses average repeated instances; they do not create strategic interaction across the society, and the paired cell type records more context than an individual utility vector alone. I think the authors could recognize this as a repeated deployment of their bilateral allocation problem, especially given the paper’s peer-to-peer-sharing motivation, but it is a narrow extension rather than a mirror of a shared-pool, many-agent mechanism-design problem. It covers Theorem 6 only.
The offered cell construction is easy to extend mathematically: if each cell runs Theorem 6’s mechanism, its guarantee sums over the cell distribution:
\[
W_\mu=\sum_p\mu_p W(p)\ \geq\ 0.67776\sum_p\mu_p\mathrm{OPT}(p)
=0.67776\,\mathrm{OPT}_\mu.
\]
But the masses only average independent two-person instances. They create no shared resource constraint or strategic interaction across cells; evaluating the mechanism on \(\tau\) supported cell types is just \(\tau\) independent applications. Optimizing for a known distribution of cells would add prior information to the paper’s no-prior problem. That makes the proposed mirror a weak computational anchor.
The strongest objection I can make is that a shared-pool model would be a substantial change to Theorem 6’s setting. Put a mass distribution \(\mu\) over individual utility-vector types, give each person a fixed per-capita share of the item supply, and seek a strategyproof allocation rule that maximizes welfare against the feasible first best. Now allocations across types compete for the same stock, and a person’s report can affect their own bundle. The two-agent PA mixture does not directly solve this problem: applying it pairwise would require a new rule to keep the shared allocation feasible. The problem would need its own incentive constraints and computational analysis.
That objection does not establish that the new question is unworthwhile. A high-multiplicity population sharing divisible resources fits the paper’s broad motivation, and its Dynamic-Increasing-Price discussion explicitly reaches toward mechanisms for any number of agents. The two-agent theorem therefore lacks a direct, nontrivial population mirror, while the stronger shared-pool version remains plausible and recognizable as part of the paper’s problem area.
So the best negative case defeats the proponent’s *cell formulation* as a substantial complexity question. It cannot honestly defeat every plausible scenario. The requested universal case against a worthwhile continuous mirror is weak here.
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.