| paper | d4-journals-geb-2024-0078 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L,C\); every instance admits a complete, utilitarian-optimal, envy-free plan with subsidies in \(\{0,1\}\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.20
statement extracted from the paper’s text layer
Given a support \(T\) of \(\tau\) worker types with rational shares \(\mu_t\), matroid rank valuations \(r_t\) on \(E\), and rational per-capita supplies \(\lambda_e\) of each item class, determine whether a polynomial-time algorithm can output a finite-support rational plan \(x_{t,k,p}\). Here \(k\in\mathbb{Z}_{\ge 0}^{E}\) is each worker's integral bundle of interchangeable copies, copies of a class are parallel in every type's matroid, and \(p\in\{0,1\}\) is the subsidy. Require \(\sum_{k,p}x_{t,k,p}=\mu_t\), \(\sum_{t,k,p}x_{t,k,p}k_e=\lambda_e\) for every \(e\), maximum utilitarian welfare among complete plans, and envy-freeness between every pair of positive-mass outcomes: \(r_t(\operatorname{supp}(k))+p\ge r_t(\operatorname{supp}(k'))+p'\). Measure running time in \(m=|E|\), \(\tau\), input bit length, and matroid representation cost.
A distribution of workers over matroid types with mass \(\mu_t\), receiving integral bundles of parallel item copies and subsidies in \(\{0,1\}\); each item class has supply \(\lambda_e\) per unit of population, and the plan must be complete, utilitarian-optimal, and pointwise envy-free.
Restricting subsidies to \(0\) or \(1\) makes the average subsidy bound of \(1\) automatic and loses the finite guarantee that at least one agent receives no subsidy; the mirror retains the meaningful per-worker cap.
fatal: False
The mirror covers Theorem 3.20's complete, utilitarian-optimal, envy-free allocation result for matroidal valuations. It leaves aside the truthful SE mechanism of Theorem 3.1, the lower bound of Theorem 3.19, and the results for superadditive and general valuations.
My lead is a high multiplicity version of the paper’s complete, envy-free matroidal allocation problem. There is no directly comparable hardness theorem for this problem in the paper, so the strongest anchor is its polynomial-time result.
Anchor: Theorem 3.20, proved here. For matroidal valuations, the authors give a polynomial-time algorithm that computes a complete, utilitarian-optimal, envy-free allocation with each agent receiving subsidy \(0\) or \(1\), and total subsidy at most \(n-1\). The theorem does not claim truthfulness.
Here is the continuous problem I would hand to a prover. Let \(E\) be a set of \(m\) item classes, and let \(T\) be a support of \(\tau\) worker types. Type \(t\) has a matroid rank valuation \(r_t\) on \(E\). The input gives rational population shares \(\mu_t\), summing to \(1\), and rational per-worker supplies \(\lambda_e\) of each item class \(e\). The rank function is the type’s complete relevant description; any other preference or eligibility differences belong in the type too.
Think of each class \(e\) as having many interchangeable physical copies, with copies of the same class parallel in every type’s matroid. A worker’s bundle is an integer vector \(k\in\mathbb Z_{\ge 0}^E\), and their value is \(r_t(\{e:k_e>0\})\). Thus bundles remain integral for every worker even though the population is continuous.
Call the problem Matroidal Continuous Complete EF Allocation. Its output is a finite-support rational table \(x_{t,k,p}\ge 0\), where \(x_{t,k,p}\) is the fraction of the whole population of type \(t\) receiving bundle \(k\) and subsidy \(p\in\{0,1\}\). Require
\[
\sum_{k,p}x_{t,k,p}=\mu_t
\quad\text{and}\quad
\sum_{t,k,p}x_{t,k,p}k_e=\lambda_e\ \text{for every }e.
\]
The second equality means all item copies are allocated. Require the plan to maximize utilitarian welfare among complete plans, with welfare \(\sum_{t,k,p}x_{t,k,p}r_t(\{e:k_e>0\})\). Require envy-freeness pointwise: whenever \(x_{t,k,p}>0\) and \(x_{t',k',p'}>0\),
\[
r_t(\{e:k_e>0\})+p
\;\ge\;
r_t(\{e:k'_e>0\})+p'.
\]
The average subsidy per worker is at most \(1\), the limit of the theorem’s \((n-1)/n\) bound. The computational question is whether such a plan can be found in time polynomial in \(m,\tau\), the rational input bit length \(L\), and the cost of the matroid representations—without expanding the population into individual workers.
This has a plausible workforce interpretation: a large employer repeatedly assigns task or shift copies to workers drawn from a modest number of skill and eligibility types. Type shares describe the workforce, and task supplies scale with its size. Taking a common denominator \(N\) for the input gives a finite instance with \(N\mu_t\) workers of each type and \(N\lambda_e\) copies of each item class. The cloned valuations are still matroidal, so Theorem 3.20 applies; normalizing its allocation gives a finite-support mass plan. This makes the question a direct high multiplicity version of the paper’s problem. The finite theorem supplies feasibility, but its runtime in \(N\) need not be polynomial in \(L\): the denominator can be exponentially large.
I expect this mirror to be Class A, tractable, though that is a conjecture, not a consequence of Theorem 3.20. Its structural proof uses matroid intersection and M-convex exchange, and repeated workers can potentially be represented by type masses rather than individual coordinates. The open algorithmic step is to compress those exchanges and handle envy comparisons among the bundles receiving positive mass. In particular: can one obtain a polynomial-size output and a polynomial-time algorithm in \(m,\tau,L\); and do the envy constraints force a continuum-specific hardness result instead?
The weakest point is that this mirrors Theorem 3.20’s algorithmic fair-allocation result, not the paper’s truthful SE mechanism in Theorem 3.1. Truthfulness for an infinitesimal worker needs a careful finite-to-continuum interpretation, so I would not claim this model preserves it. The paper’s broader mechanism-design story is outside this mirror’s scope. The case still stands for the complete, utilitarian-optimal, envy-free allocation problem that the authors explicitly solve in Theorem 3.20.
The best negative argument is that Theorem 3.20’s guarantee depends on a finite assignment problem: indivisible goods go to named agents, and the proof uses matroid exchange between their bundles. If the goods stay fixed while the workforce grows, the per-capita supply tends to zero; a mass allocation then loses track of the few people who receive goods. But that objection does not defeat this anchor. The proposed mirror scales supplies with the workforce, and the programme explicitly allows that co-modification when continuization requires it.
With that scaling, the mirror is a sensible high-multiplicity problem. A type can be the worker’s full matroid valuation, and a rational input can be expanded to a finite cloned instance. Theorem 3.20 then gives feasibility, but its runtime may be polynomial in the denominator \(N\), which can be exponential in the input bit length. Whether the matroid exchange structure can be compressed to run in time polynomial in \(m,\tau,L\) is a real computational question. The fact that the workers’ bundles remain integral does not undermine it: the population, rather than each worker’s bundle, is the continuous object.
There is one narrower weakness in the proposed formulation: the average subsidy bound of \(1\) is automatic when every worker’s subsidy is restricted to \(\{0,1\}\). It captures the limit of the paper’s \((n-1)/n\) bound, but loses the finite guarantee that at least one agent gets no subsidy. That loss is asymptotically natural, and it does not erase the per-worker cap of \(1\), which remains a substantive part of the result.
So I cannot honestly defeat Theorem 3.20 as an anchor. Its mirror is not guaranteed to yield a new algorithm, and its optimization structure may remain discrete and difficult. But those are open algorithmic questions, not evidence that no worthwhile mirror exists. The negative case here is weak.
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.