| paper | d4-conf-ijcai-2019-0596 |
| 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: Every society in the product family satisfies \(R_\infty\le (k-1)/(1+(k-2)\mu)\le 1/\mu\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given \(k\) item classes and a finite support \(\{(v_t,\rho_t)\}_{t=1}^{\tau}\), where \(v_t\in[0,1]^k\), \(\rho_t\in\mathbb{Q}_{>0}\), and \(\sum_t\rho_t=1\), with per-capita supply \(1/k\) of each class, compute the ratio of optimal welfare to Random Priority welfare in the fluid limit of replicas with \(K\rho_t\) agents of type \(t\) and \(K/k\) indivisible copies of each class. For the product-type family where the first two coordinates are fixed at \(1\) and \(0\), and the remaining coordinates are independent draws from a finite-support rational distribution \(D\) on \([0,1]\) with mean \(\mu>0\), does this limiting ratio always satisfy \(R_\infty\le 1/\mu\)?
Types are complete valuation vectors \(v_t\) with masses \(\rho_t\); each item class has mass supply \(1/k\). The optimum is a transportation LP over type-to-class mass assignments. Random Priority is the fluid limit of uniform priority orders in compatible finite replicas, with each type taking its highest-valued class still available; the objective is the ratio of the two per-capita welfares.
The fixed-\(k\) fluid limit suppresses the profile and priority fluctuations in Theorem 2 and replaces \(n\) growing item identities with repeated item classes, so relating its ratio to the theorem's average-case quantity requires a separate limit argument.
fatal: False
The mirror covers Theorem 2's iid Random Priority welfare-ratio guarantee for a finite-support product family; it leaves the growing-item regime, Theorem 4's nonidentical distributions, and the paper's other results without a continuous analogue.
The strongest positive case is Theorem 2, proved in this paper. It gives an average-case approximation guarantee for the Random Priority algorithm: with \(n\) agents and \(n\) items, two valuation entries per agent fixed at \(0\) and \(1\), and the remaining entries drawn independently from a common distribution \(D\) on \([0,1]\) with mean \(\mu>0\), the paper shows that the expected pointwise ratio \( \mathbb{E}[SW_{\mathrm{OPT}}/SW_{\mathrm{RP}}] \) is asymptotically bounded by \(1/\mu\). Here \(SW_{\mathrm{OPT}}\) is maximum-weight matching welfare and \(SW_{\mathrm{RP}}\) is the welfare of Random Priority. This is an approximation-result anchor, though not a hardness or complexity-classification result.
A concrete mirror is Product-Type High-Multiplicity Random Priority Ratio. Fix \(k\) item classes, each with per-capita supply \(1/k\). A type is a complete valuation vector \(v_t\in[0,1]^k\), and the society is a finite-support distribution \(\rho\) over those types, with rational masses summing to \(1\). To match Theorem 2’s setup, take \(\rho\) to be the product law whose first two coordinates are fixed at \(1\) and \(0\), and whose remaining coordinates are independent draws from a finite-support rational distribution \(D\) of mean \(\mu\). Thus the number of types is at most \(|\operatorname{supp}(D)|^{k-2}\), while the population can be arbitrarily large.
The continuous optimum is the transportation LP
\[
\max \sum_{t,j}x_{tj}v_{tj}
\quad\text{subject to}\quad
\sum_j x_{tj}=\rho_t,\qquad
\sum_t x_{tj}=1/k,\qquad x_{tj}\ge 0.
\]
Define continuum Random Priority as the fluid limit of finite replicas: take \(K\rho_t\) agents of each type and \(K/k\) indivisible copies of each item class, order the agents uniformly at random, and have each take their highest-valued available class. Equivalently, in the limit, type \(t\) arrives at rate \(\rho_t\) and takes its favourite class with remaining capacity. The question is: given the rational type masses and valuations, compute the limiting ratio \(R_\infty=SW_{\mathrm{OPT}}^\infty/SW_{\mathrm{RP}}^\infty\); for the product-type family, does \(R_\infty\le 1/\mu\) hold? A solution would give the exact ratio for an instance and either prove that bound for the family or provide a counterexample. The finite-replica average pointwise ratio is the closest match to the paper’s expectation; its convergence to this fluid ratio is an inference from concentration of type counts and the priority process.
I expect the instance-evaluation problem to be tractable, in Class A: the optimum is an LP, and the fluid priority process has finitely many capacity-filling events. The \(1/\mu\) guarantee is the natural conjecture to test. This mirror covers only Theorem 2’s Random Priority welfare guarantee, not the paper’s other results or incentive properties. Further questions include finite-population convergence rates, unequal item supplies, and correlated or non-identical type laws.
The weak point is substantial: in the paper, values are independently drawn for each agent–item pair while the number of distinct items grows with the population. In the mirror, item classes have many identical copies and agents repeat a bounded set of complete valuation types. The paper’s \(n^2\)-entry concentration argument therefore does not transfer directly. Still, assignment welfare and Random Priority remain the underlying problem, and repeated types with per-capita supplies are a plausible high-multiplicity regime. A referee could reasonably accept the question as a continuous extension of Theorem 2, but the bound would be a new result, not a consequence of the paper’s proof.
The only serious anchor is Theorem 2, with Theorem 4 as its non-identically distributed counterpart. They bound the expected welfare ratio of a fixed mechanism under a random valuation matrix; they do not classify a computational problem or give an algorithm for computing that expectation. Asking for the ratio on a mass distribution creates a new computational task. For finite-support valuation types, its continuous Random Priority process can be simulated by tracking type flows until item capacities are exhausted, while the optimum is a transportation LP. That is a sensible model, but it looks like a routine fluid calculation attached to this paper’s probabilistic analysis, not a new complexity question.
There is a dilemma in making that model match the theorem. If the number of items grows with the population, as it does in the paper, then a complete type records \(n\) values. For a product distribution with \(d\) possible values, its support can have size \(d^{n-2}\); for a continuous distribution, it is uncountable. A compact product-law encoding could avoid listing those types, but that changes the input model and asks a new question about a succinctly represented distribution. If instead the number of item classes \(k\) stays fixed to keep the type representation manageable, the mirror has changed the asymptotic regime: the population grows while the item space stays fixed.
That fixed-\(k\) fluid model also removes the main feature of the theorem’s analysis. In the paper, the expectation is over random valuation matrices, and the proof explicitly controls the rare profiles where Random Priority has unusually low welfare. With fixed type masses, the fluid process is deterministic; those profile fluctuations disappear. Taking the fluid limit first and then letting the item count grow may be interesting, but it is a different limit, and the paper’s \(1/\mu\) bound does not by itself motivate or establish it.
I cannot make the negative case airtight. Assignment welfare is aggregative, repeated valuation types are plausible in large allocation settings, and a continuous priority process is well defined. The stronger objection is that every repair either changes the paper’s growing-item regime and discards the randomness its result studies, or requires a new distribution encoding and a separate two-limit analysis. That makes this a weak fit for ChoCo’s complexity programme, even though the resulting fluid-market question could be worthwhile on its own.
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.