| paper | d4-conf-ecai-2014-0298 |
| 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: Constructible in \(\operatorname{poly}(m,\tau,L)\) time and output size, with at most \(\tau+m\) occupied pairs. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), item categories \(E\), rational per-capita supplies \(b_e\ge 0\), and nonnegative rational utilities \(u_t(e)\) normalized by \(\sum_{e\in E} b_e u_t(e)=1\), construct an explicit polynomial-size distribution \(y_{t,k}\) over integral bundles \(k\in\mathbb{Z}_{\ge 0}^{E}\). Require \(\sum_k y_{t,k}=\mu_t\), \(\sum_{t,k}y_{t,k}k_e=b_e\) for each \(e\), and, for every two occupied type-bundle pairs \((t,k)\) and \((t',k')\) with \(k'\ne 0\), \(U_t(k)\ge U_{t'}(k')-\min_{e:k'_e>0}u_{t'}(e)\), where \(U_t(k)=\sum_e u_t(e)k_e\). Is such a distribution constructible in time polynomial in \(|E|\), \(|T|\), and the binary input length \(L\)?
A free-matroid allocation for a population of branches grouped by complete utility type, with rational type masses and per-capita supplies. The decision variables assign each type’s mass to integral individual bundle patterns; the output is an explicit feasible distribution satisfying the paper’s near-jealousy test. There is no welfare objective.
The mirror covers Theorem 3 for free-matroid allocations; it leaves the general matroid setting and the paper’s proportionality and envy-freeness results aside.
The strongest named anchor is Theorem 3, proved in this paper: for a matroid \(M=(X,\mathcal F)\), \(n\) agents, and additive nonnegative utilities, a nearly jealousy-free base allocation always exists and can be computed in \(O(nm\ln m)\) time. Here “nearly jealousy-free” means that for every pair \(i,j\) and every element \(x\in B_j\), \(u_i(B_i)\ge u_j(B_j-\{x\})\). The stated running time neglects independence-oracle cost, as the paper specifies.
The paper does say in unnumbered prose that deciding whether an exactly equitable, proportional, or envy-free allocation exists is NP-complete. Those would be attractive hardness leads, but they are not numbered results of the kind required for an anchor. I would use Theorem 3 alone. Theorem 4’s proportionality guarantee is less suitable for a population limit because its \(1/n\) benchmark tends to zero; Theorem 5 fixes the number of agents at two.
Here is a continuous mirror of Theorem 3, restricted to the free-matroid case, which the paper identifies with ordinary allocation of indivisible goods. Consider a recurring equipment programme serving many regional branches. A branch’s type is its complete utility vector over equipment categories. There are \(N\) branches but only \(\tau\) such types, with \(N\gg\tau\). The programme’s stock grows with its reach, so category \(e\) has \(b_e\) indivisible items per branch on average. This is the setting in which mass is useful: a standardized branch type may account for a rational fraction \(\mu_t\) of the population, while the branches in that type can still receive different integral bundles.
Call the problem Continuous Near-Jealous Allocation. Its input is a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), a finite set \(E\) of item categories, rational per-capita supplies \(b_e\), and nonnegative rational utilities \(u_t(e)\), normalized by \(\sum_{e\in E}b_eu_t(e)=1\) for every type. A solution is a finite list of bundle patterns \(k\in\mathbb Z_{\ge0}^{E}\) and rational masses \(y_{t,k}\ge0\). They must exhaust each type and the stock: \(\sum_k y_{t,k}=\mu_t\) and \(\sum_{t,k}y_{t,k}k_e=b_e\) for every \(e\). Write \(U_t(k)=\sum_e u_t(e)k_e\). For every two occupied type-bundle pairs \((t,k)\), \((t',k')\), with \(k'\ne0\), require \(U_t(k)\ge U_{t'}(k')-\min_{e:k'_e>0}u_{t'}(e)\). That is exactly the paper’s near-jealousy test, applied to every pair of individual bundle patterns used by positive population mass. The task is to construct such a \(y\); there is no welfare objective in the anchor or in this mirror.
The finite-population bridge is unusually direct. For rational \(\mu\) and \(b\), clear denominators with some \(q\), create \(q\mu_t\) agents of each type and \(qb_e\) copies of each item category, and give each copy utility \(u_t(e)/q\). The full stock then has value \(1\) to each type, matching the paper’s normalization. Theorem 3 supplies a discrete allocation, and its bundle frequencies give a rational \(y\). Conversely, any rational \(y\) can be scaled into a finite allocation. Thus the existence half is already implied by the paper’s theorem. The substantive continuous question is whether one can construct a compact allocation in time polynomial in \(|E|\), \(\tau\), and the binary input length \(L\): clearing denominators may make \(q\), and the paper’s \(O(nm\ln m)\) running time, exponential in \(L\).
For this free-matroid mirror, I would expect Class A, because repeated agents of the same type may let a greedy construction process masses and repeated bundle patterns in batches. That is a route to investigate, not a result established by the paper: the pairwise fairness constraints depend on which bundle patterns actually receive positive mass, so a compact construction might still face a hard support-selection or pricing problem. The next questions are whether a polynomial-bit sparse output always exists, whether batch processing gives a polynomial-time construction, and whether the method extends from the free matroid to partition or general matroids.
The authors should recognize the underlying question: many agents with shared utility types receive indivisible bundles from a stock, and the allocation must satisfy their stated near-jealousy condition. The model preserves that condition rather than replacing it with ordinary envy-freeness or a type-average fairness test. Its scope is deliberately limited to Theorem 3’s free-matroid special case; it does not claim a mirror of the general matroid setting or the other fairness theorems.
The soft spot is the scaling of supply and the change from named agents to masses over bundle patterns. The branches must be numerous, and their stock must grow with them; otherwise most branches get nothing and the limit loses substance. And although \(y\) records the exact distribution of integral individual bundles, the paper’s sequential algorithm does not itself provide a polynomial-size, polynomial-time mass representation. The denominator-clearing bridge makes existence credible; it does not settle the continuous complexity question.
The strongest objection to the proposed mirror is that Theorem 3 already settles its existence guarantee. For rational \(\mu\) and per-capita supplies \(b_e\), clear denominators with \(q\), create \(q\mu_t\) agents of each type and \(qb_e\) copies of each item category, and scale item utilities by \(1/q\). The theorem’s allocation then gives bundle frequencies satisfying the proposed continuous fairness condition. So the remaining question is whether those frequencies can be constructed and represented compactly in time polynomial in \(|E|,\tau,L\). The paper’s \(O(nm\log m)\) algorithm does not answer that: \(q\) can be exponential in the binary input length.
That makes the mirror narrower than its statement may suggest. “Construct \(y\)” needs an explicit output-size requirement. An explicit list of bundle patterns could itself have size exponential in \(L\); a polynomial-size output would turn the problem into a meaningful compactness and high-multiplicity algorithm question. That is a real formulation weakness, but it does not defeat the best version of the mirror: finding a compact construction is exactly the unresolved computational question.
The broader negative case does not hold up. Scaling per-capita supplies and retaining integral individual bundles is a legitimate population co-modification. The pairwise condition preserves the paper’s fairness test across actual bundle patterns, and the one-item allowance remains meaningful when utilities are scaled consistently. Repeated branches with standardized equipment may be a narrow scenario, but the free-matroid allocation problem is still a sensible high-multiplicity regime. Neither the result’s computational character nor the type model supplies a fundamental obstruction.
So the honest case against is weak: the proposed mirror inherits its existence result, and its compact-output specification needs sharpening. I cannot honestly turn that into a case that no worthwhile continuous mirror exists. The compact high-multiplicity construction question survives.
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.