| paper | d4-conf-sagt-2014-0024 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: For every input, \(W_\infty\) exists and is characterized by the remaining-supply flow. It can be approximated deterministically to additive error \(\varepsilon\) in time polynomial in \(m,\tau,L,1/\varepsilon\), together with exact computation of \(\nu^*\). The universal guarantee \(W_\infty\ge(\nu^*)^2/e\) holds. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\) and category supplies \(\rho_j\), each summing to \(1\), and normalized values \(v_t(j)\in[0,1]\), define a market with \(D\mu_t\) agents of type \(t\) and \(D\rho_j\) items of category \(j\), for common-denominator multiples \(D\). What is the limiting per-capita expected welfare \(W_\infty=\lim_{D\to\infty}\mathbb{E}[\mathrm{SW}(\mathrm{RSD})]/D\), and can it be computed to additive error \(\varepsilon\)? Compute also \(\nu^*=\max_x\sum_{t,j}v_t(j)x_{tj}\), subject to \(\sum_jx_{tj}=\mu_t\) and \(\sum_tx_{tj}=\rho_j\), and determine whether \(W_\infty\ge(\nu^*)^2/e\).
Types are complete value vectors over \(q\) interchangeable item categories, with mass \(\mu_t\); category \(j\) has supply \(\rho_j\). Aggregate assignment variables \(x_{tj}\) are fractional flows, while each individual still receives one indivisible item. The benchmark maximizes \(\sum_{t,j}v_t(j)x_{tj}\) subject to the type-mass and category-supply constraints. Fluid-RSD processes type mass in random-priority proportions: with residual supply \(y_j(s)\), types choose their highest-valued available categories and split ties in proportion to residual supply; the task is to compute the resulting welfare.
Theorem 3’s numeric guarantee follows from finite replications if convergence holds, so the new computational contribution may mainly be proving and evaluating the fluid limit.
fatal: False
The mirror covers the welfare of RSD and the optimal-welfare benchmark in normalized repeated-category markets, corresponding to Theorem 3; the dichotomous version also covers Theorem 2. It leaves Theorem 1’s truthfulness and symmetry claims, Theorem 4’s mechanism impossibility bound, and the counting discussion around Claim 1 outside its scope.
The strongest mirror here is RSD welfare in a large, repeated-category assignment market. Imagine a large university assigning instructors to course sections, or a large organization assigning workers to shifts. There are many agents, but relatively few distinct preference vectors and item categories: population size \(N\) is much larger than the number \(\tau\) of represented agent types, while the number \(q\) of item categories is fixed or moderate. A type is a complete value vector over those categories; its mass is its fraction of the population. Each person still receives one indivisible item. Fractional allocations describe only the aggregate flow of many people of the same type, and item supplies scale with population size.
For a precise model, let \(J=[q]\) be the item categories, with per-capita supplies \(\rho_j\ge 0\), \(\sum_j\rho_j=1\). Let \(T\) be the \(\tau\) supported agent types, with rational masses \(\mu_t\ge 0\), \(\sum_t\mu_t=1\). Type \(t\) has value \(v_t(j)\) for category \(j\). A feasible aggregate assignment is a flow \(x_{tj}\ge 0\) with \(\sum_jx_{tj}=\mu_t\) and \(\sum_tx_{tj}=\rho_j\). Thus every individual gets one ordinary item, while \(x_{tj}\) may be fractional.
The continuous RSD mirror is the fluid limit of the paper’s RSD: agents arrive in uniformly random priority order and choose a highest-valued remaining item, breaking ties uniformly among such items. Write \(y_j(s)\) for the remaining supply of category \(j\) after mass \(s\) has been processed, and \(M_t(y)=\arg\max_{j:y_j>0}v_t(j)\). The limiting allocation rate for type \(t\) is
\[
f_{tj}(s)=
\begin{cases}
\displaystyle \mu_t\frac{y_j(s)}{\sum_{k\in M_t(y(s))}y_k(s)},&j\in M_t(y(s)),\\
0,&\text{otherwise},
\end{cases}
\qquad
\dot y_j(s)=-\sum_t f_{tj}(s),\quad y_j(0)=\rho_j.
\]
The fluid allocation is \(x^{\mathrm{RSD}}_{tj}=\int_0^1 f_{tj}(s)\,ds\). Its welfare is \(W=\sum_{t,j}v_t(j)x^{\mathrm{RSD}}_{tj}\). The benchmark is the maximum welfare
\[
\nu^*=\max_x\sum_{t,j}v_t(j)x_{tj}
\]
over feasible aggregate assignments.
My lead anchor is Theorem 2, proved in Section 4: for dichotomous preferences, RSD’s expected welfare is at least one third of maximum welfare, for every one-sided matching instance. Its mirror is Dichotomous Fluid-RSD Welfare. The input is rational masses \(\mu_t\) over approval-set types \(A_t\subseteq J\), and rational category supplies \(\rho\). The task is to compute the limiting RSD welfare to additive error \(\varepsilon\), along with the maximum welfare \(\nu^*\); a solution returns an \(\varepsilon\)-accurate welfare value and establishes or refutes the universal guarantee \(W\ge\nu^*/3\). This is the cleanest mirror because it retains the paper’s RSD rule and dichotomous welfare question while making the population itself the mass distribution. Replicating the types and supplies gives finite instances of the kind in Theorem 2, so the one-third guarantee should pass to the fluid limit once convergence is shown.
A second, broader anchor is Theorem 3, proved in Section 5: with \(n\) agents and \(n\) items and values in \([0,1]\), RSD’s expected welfare is at least \(\nu(O)^2/(en)\). Its mirror is Normalized Fluid-RSD Welfare: use the same instance and task with rational \(v_t(j)\in[0,1]\), and ask for the fluid RSD welfare and \(\nu^*\). Since total population mass is one, the corresponding guarantee is \(W\ge(\nu^*)^2/e\). This is a genuine extension beyond approval sets, not a different outcome-space relaxation.
For both questions, I expect Class A: the benchmark is a transportation LP, and the RSD limit is a finite-dimensional, piecewise-defined flow driven by the explicit type masses and residual supplies. The concrete computational target is an algorithm polynomial in \(q,\tau,L,1/\varepsilon\) for additive-\(\varepsilon\) evaluation. The number of item categories that can exhaust is finite, but efficient numerical treatment of the flow—especially as \(q\) varies—is the main technical question. Further questions include the tight worst-case fluid approximation ratio and quantitative bounds on how quickly finite RSD markets approach the fluid welfare.
The paper’s #P-complete counting remark near Claim 1 is not my hardness anchor: it concerns counting maximum matchings and motivates a conjecture about a different optimal mechanism. I also leave Theorems 1 and 4 out of scope. Their truthfulness claims rely on individuals’ reports affecting outcomes; for zero-mass individuals in a nonatomic model, that incentive condition can become vacuous.
The weakest point is that the paper proves bounds for finite random permutations, not a fluid-limit theorem or an algorithm for evaluating the limiting flow. A referee could reasonably ask whether the new task is sufficiently the authors’ problem. I think the mirror survives that objection: it keeps their RSD allocation rule, welfare objective, and repeated assignment setting, while making the natural large-market case—many people, few recurring preference and item types—explicit.
The strongest case against these mirrors is a scope objection: Theorems 2 and 3 analyze the welfare of a particular randomized mechanism. They do not classify the complexity of finding an intervention, designing an optimal mechanism, or solving a new allocation problem. The proposed task—evaluate a fluid version of RSD and compare it with optimal welfare—could become a useful asymptotic analysis without advancing the programme’s central complexity questions. Its optimal-welfare benchmark is a transportation LP, and its RSD component is a limit-flow calculation. That makes it a less direct fit than a mirror about bribery, control, or robustness.
But that objection does not defeat either anchor. Replicate a rational type distribution and item supplies by a common denominator \(D\). The finite market then has \(D\) agents and \(D\) items, and its RSD tie-breaking among identical item categories selects a category in proportion to its remaining supply—the behavior in the proposed flow. If the finite welfare and optimum are \(D W\) and \(D\nu^*\), Theorem 2 gives \(W\ge\nu^*/3\) after normalization. Theorem 3 gives \(W\ge(\nu^*)^2/e\). So neither bound degenerates as the population grows. Establishing convergence to the proposed flow, and computing that flow efficiently, would still be continuous-population results. The fact that the finite theorems strongly suggest their answers is not a sound reason to reject the questions.
The same objection applies to both anchors, but Theorem 3 is especially hard to dismiss: normalization produces a meaningful per-capita bound, and the model accepts fractional type-level flows while each person still receives one item. Theorem 2 also has a natural dichotomous version, with repeated shifts or course sections as item categories. In either case, requiring item categories to be genuinely interchangeable may limit the useful regimes; if schedules or other item features matter, they must be represented. That narrows the setting, but the paper’s matching examples and the proposed repeated-category markets supply plausible regimes.
I would not claim a stronger universal objection. A mirror of truthfulness might raise a more fundamental question: in a nonatomic model, how should a unilateral report change be represented when one agent has zero mass? Yet that does not undermine these two welfare anchors, which do not rely on strategic incentives. And even for truthfulness, a test agent’s report could affect that agent’s own allocation while leaving the population flow unchanged.
So the negative case is weak under the programme’s stated standard. The best criticism is that these mirrors may sit at the edge of the programme’s computational agenda, and their headline welfare inequalities may follow from the finite results once fluid convergence is proved. That is a case for narrowing the contribution, not for saying no worthwhile continuous mirror exists. Both named anchors survive.
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.