| paper | d4-conf-ijcai-2021-0652 |
| 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 instance is feasible; a satisfying assignment can be found in polynomial time with polynomial output length. · discrete side: other · adjudication: proved
full proof & adversarial review →
Lemma 5
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\), per-capita supplies \(q_g\), and nonnegative values \(v_{tg}\) with \(\sum_g q_gv_{tg}=1\), compute a finite-support rational assignment \(\lambda_{t,B}\), where each recipient receives an integral bundle \(B\in\mathbb{Z}_{\ge 0}^{G}\). Require \(\sum_B\lambda_{t,B}=\mu_t\), \(\sum_{t,B}\lambda_{t,B}B_g=q_g\), and, for every \((t,B)\) with \(\lambda_{t,B}>0\), \(v_t(B)+d_t(\lambda)\ge 1\), where \(v_t(B)=\sum_gv_{tg}B_g\) and \(d_t(\lambda)=\max_{C:\exists s,\lambda_{s,C}>0}\min_{g:C_g>0}v_{tg}\), with \(d_t(\lambda)=0\) if no nonempty bundle is assigned. Is such an assignment computable in time polynomial in \(\tau\), \(r\), the input bit length \(L\), and the output length?
A continuous population over complete valuation types, with mass assigned to integral bundle patterns and rational per-capita supplies of repeated goods. The \(\mathrm{PROP}_m\) benchmark is the maximum, over bundles receiving positive mass, of each type’s least-valued item in that bundle.
The \(\mathrm{PROP}_m\) benchmark depends on whether a bundle has any positive mass, so a cohort whose mass tends to zero can retain a full fairness effect.
fatal: False
Covers the paper’s \(\mathrm{PROP}_m\) allocation guarantee and algorithm; it leaves the paper’s discussion of other fairness notions, including EFx and a-EFx, aside.
There is no eligible numbered computational anchor in this paper. Its main result—PROP\(_m\) allocations always exist and Algorithm 1 computes one in time polynomial in the number of agents and goods—is proved here, but stated in the abstract and Sections 3 and 7 without a numbered theorem, lemma, corollary, or proposition. The numbered Theorem 4 is useful structural support, not a complexity result: it says that if the divider receives \(S_\ell\), and no item from \(S_1\cup\cdots\cup S_{\ell-1}\) is allocated to the same agent as an item from \(S_{\ell+1}\cup\cdots\cup S_n\), then the divider is PROP\(_m\)-satisfied. I can’t honestly present that as an anchor for a complexity mirror.
The strongest positive case is therefore for a mirror of the paper’s unnumbered polynomial-time result. Call it PROPm Cohort Allocation. Its intended regime is a large allocation programme in which many households receive indivisible goods, but households fall into a modest number \(\tau\) of complete valuation types, and goods come in a modest number \(r\) of categories with identical values for every type. The population and supplies grow together; \(\tau\) and \(r\) stay small relative to the number of households. For example, households in a large public distribution programme could share a small set of needs profiles and receive integral bundles of repeated goods.
An instance gives rational type masses \(\mu_t\), with \(\sum_t\mu_t=1\); rational per-capita supplies \(q_g\) of goods in categories \(g\in G\); and nonnegative rational values \(v_{tg}\). Normalize so that \(\sum_g q_gv_{tg}=1\) for each type and \(v_{tg}\leq 1\). A solution is a finite-support rational assignment \(\lambda_{t,B}\geq0\), where \(\lambda_{t,B}\) is the fraction of the population of type \(t\) receiving the integral bundle \(B\in\mathbb{Z}_{\geq0}^{G}\). It must satisfy
\[
\sum_B\lambda_{t,B}=\mu_t
\quad\text{and}\quad
\sum_{t,B}\lambda_{t,B}B_g=q_g\ \text{for every }g.
\]
For a type \(t\), let \(v_t(B)=\sum_gv_{tg}B_g\), and let
\[
d_t(\lambda)=
\max_{C:\,\exists s,\ \lambda_{s,C}>0}
\ \min_{g:C_g>0}v_{tg},
\]
taking \(d_t=0\) if no nonempty bundle is assigned. The fairness requirement is \(v_t(B)+d_t(\lambda)\geq1\) for every pair \((t,B)\) with \(\lambda_{t,B}>0\). The computational question is: given the instance in binary, compute such an assignment in time polynomial in \(\tau\), \(r\), the input bit length \(L\), and the output length.
This formulation keeps each recipient’s outcome indivisible and makes the population the continuous object: only the mass assigned to each type-and-bundle pair is fractional. It also has an exact high-multiplicity bridge. For any sufficiently divisible \(N\), make \(N\mu_t\) agents of type \(t\), \(Nq_g\) copies of good \(g\), and value each copy at \(v_{tg}/N\). Every agent then values all goods at \(1\), and each item is worth at most \(1/N\). An assignment \(\lambda\) lifts to a finite allocation by giving \(N\lambda_{t,B}\) agents bundle \(B\); multiplying the finite PROP\(_m\) condition by \(N\) gives precisely the inequality above. Thus the model describes the same fairness question for large cohorts with repeated types, not fractional bundles for individual agents.
I would tentatively expect this problem to be Class A. The paper’s divider and graph-based exchanges suggest a route in which mass transfers replace individual-agent swaps, and proportional subproblems remain the organizing principle. That is a research hypothesis, not a consequence of the paper’s runtime: \(N\) can be exponentially large in \(L\), so running Algorithm 1 on the expanded instance does not meet the proposed bound. Further questions include whether a mass-based exchange procedure can be encoded compactly, how small a support a solution can have, and whether adding efficiency requirements preserves tractability.
The weakest point is PROP\(_m\)’s sensitivity to rare allocations. In a finite instance, even a single agent’s bundle can determine another agent’s maximin item. The mass formulation uses bundles assigned positive population mass; a vanishingly rare bundle may disappear from that description while still affecting finite-instance fairness. The mirror is most convincing for cohort policies in which every assigned bundle goes to a positive share of a genuinely large group. If the authors regard protection against singleton exceptions as essential to PROP\(_m\), they may reject this as a faithful population-level version. The paper’s numbered Theorem 4 supports the case that PROP\(_m\) admits structural reasoning about decomposed groups, but it does not settle that concern or supply the missing numbered computational anchor.
The formal anchor is weaker than the case for suggests: the paper’s polynomial-time result is stated in the abstract and Sections 3 and 7, but no numbered theorem or lemma asserts it. Theorem 4 is numbered, but it is a structural condition for the divider’s PROP\(_m\) guarantee, not a complexity result. That is a real limitation under the requested anchor format, though it does not erase the paper’s central algorithmic contribution.
The proposed cohort problem is a credible mirror. With repeated good categories and complete valuation types, its population can be continuous while every recipient still gets an integral bundle. The finite lift also works when the rational masses and supplies are scaled to integers. I would not reject it on the grounds that prices or valuations become type-level, or that the finite algorithm does not immediately give the desired compressed runtime.
The strongest objection is that PROP\(_m\)’s benchmark is driven by the existence of a bundle, not by how much population receives it. A bundle’s least-valued item can raise \(d_i\) for everyone else even when only one person gets that bundle. Under the proposed scaling, one item worth \(1/N\) can contribute the full \(1/N\) proportionality threshold; in per-capita units, its fairness effect remains order one even when its recipient has mass \(1/N\). As that mass tends to zero, the item disappears from the limiting society but its effect on the finite population does not tend to zero.
The cohort formulation preserves this effect by letting every positive mass count in the support maximum, however small. That keeps the exact finite notion under suitable lifts, but makes the fairness benchmark discontinuous at zero mass: an arbitrarily small cohort can matter as much as a large one, and removing it entirely can change the guarantee abruptly. Requiring a minimum cohort size would lose the singleton case; weighting or smoothing the benchmark would change PROP\(_m\). This is a serious weakness for presenting the construction as a stable continuum limit.
It is not enough, though, to show that the exact rational-mass problem is unworthy of study. One can ask a well-posed computational question about that discontinuous support-based model, and its compressed complexity is not answered by the paper’s algorithm. So I cannot honestly defeat the cohort-allocation anchor: the negative case narrows its claim to “the limit is not a smooth averaging of PROP\(_m\),” but does not establish 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.