Answer: An admissible counterexample exists for every polynomially bounded coefficient rule; the same fixed instance defeats every positive coefficient vector.
Corollary 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateUnder this mechanism, the truthful strategy of revealing all pairs dominates all untruthful ones (w.p.1).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many atomic centers \(I\), each period center \(i\) receives a rational mass vector over a finite support of complete pair types, with expected total mass \(k_i\). Types encode center ownership, compatibility, and internal-match behavior. A center may report any submass of its arrivals. Define the clearinghouse allocation by maximum-total fractional packing into legal cycles and chains; in a random center order, subject to earlier centers’ selected matched masses, choose the current center’s maximum attainable matched mass when its credit is nonnegative and its minimum otherwise, then update its credit by the corresponding best-to-worst swing. Is there a polynomially bounded coefficient \(\lambda_i\) for the update \(c_i \leftarrow c_i + \lambda_i(\text{reported mass}-k_i)\) such that full disclosure dominates every underreporting strategy with probability \(1\) and guarantees long-term individual rationality? Determine a sufficient coefficient and prove the guarantees, or give a counterexample.
There are \(n\geq2\) atomic centers. A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is support size, not the number of possible types. Masses are nonnegative and need not sum to one.
Each type specifies its owner, donor–patient compatibility, and whether it is an altruist. The input explicitly lists \(m\) permitted cycle and altruist-initiated chain templates, including type multiplicities; repeated types represent distinct individuals. Chains terminate within the period, with the final donation going to the waiting list; an employed altruist contributes one matched unit to its owner.
Arrivals are independent across periods with a common, explicitly given finite rational distribution over joint mass vectors \(a^t\), allowing dependence between centers. The known rational means satisfy \(k_i>0\), \(\mathbb E\lVert a_i^t\rVert_1=k_i\), and \(\lVert a_i^t\rVert_1\leq2k_i\). All arrivals expire after one period.
For every center, with positive probability an arriving type has positive mass that cannot be matched internally, and its matched mass differs between two globally maximum fractional packings of the full society.
A center uses a measurable policy \(S_i(a_i,c_i)=r_i\) with \(0\leq r_i\leq a_i\), and internally maximizes matched mass using the withheld vector \(a_i-r_i\) and templates entirely owned by it. Fractional packing assigns nonnegative real weights to templates, consuming their type multiplicities subject to available masses; \(u_i\) denotes the resulting matched mass owned by center \(i\).
Starting from any finite rational credit vector, first update \(c_i\leftarrow c_i+\lambda_i(\lVert r_i\rVert_1-k_i)\). Restrict to maximum-total packings of the reports, and draw an independent uniform center permutation. At center \(i\), subject to all earlier selected utilities, let \(b_i\) and \(w_i\) be its maximum and minimum attainable utilities: select \(b_i\) and subtract \(b_i-w_i\) from its credit when \(c_i\geq0\); otherwise select \(w_i\) and add \(b_i-w_i\). Fix any deterministic tie-breaking among final packings.
Let \(Q_i^S(T)\) be cumulative clearinghouse plus internal matched mass through period \(T\). Couple comparisons using identical arrivals and permutations, fixing other centers’ policies. Almost-sure truthful dominance means \(\liminf_{T\to\infty}(Q_i^F(T)-Q_i^S(T))\geq0\) almost surely from every initial state, with strict inequality almost surely on paths where \(S\) actually withholds positive mass; \(F\) reports everything. Long-term IR means \(\liminf_{T\to\infty}(Q_i^F(T)-B_i(T))/T\geq0\) almost surely, where \(B_i(T)\) is cumulative maximum internal matching of all arrivals.
Let \(L\) be the total binary input length. Coefficients must be positive rationals fixed before play and bounded by one universal polynomial in \(m,\tau,L,n,\max_i k_i\); state any running times in these quantities.
Does such a coefficient rule \((\lambda_i)\) guarantee almost-sure truthful dominance and long-term IR for every admissible arrival law, or is there an admissible counterexample to every polynomially bounded rule?
For discrete arrivals bounded by \(2k_i\), truthful dominance and long-term IR are claimed with coefficient \(4k_i\). [Hajaj et al.](https://ojs.aaai.org/index.php/AAAI/article/download/9322/9181)
No result settling this exact mass-valued mechanism was located in the literature search.
There is an admissible counterexample to every positive coefficient rule, even without a polynomial bound. The same fixed instance violates both almost-sure truthful dominance and long-term IR, from every initial credit vector.
The counterexample has genuine cross-center utility variation, two stochastic arrival states, and a deviating center that continues reporting positive mass.
There are \(n=2\) centers and \(\tau=9\) types. Every type is a donor–patient pair; there are no altruists.
In each period, independently, draw \(s\in\{1,2\}\), each with probability \(1/2\). Arrivals are:
| Types | Owner | Mass of each type |
|---|---|---|
| \(a,b\) | Center \(1\) | \(s\) |
| \(c,d\) | Center \(2\) | \(s\) |
| \(p,u,v\) | Center \(1\) | \(s/4\) |
| \(h,q\) | Center \(2\) | \(s/4\) |
The input permits exactly \(m=4\) cycle templates, each using its listed types once:
| Template | Directed cycle |
|---|---|
| \(I\) | \(a\to b\to a\) |
| \(E\) | \(a\to c\to d\to a\) |
| \(G_1\) | \(p\to h\to q\to p\) |
| \(G_2\) | \(u\to h\to v\to u\) |
Specify donor–patient compatibility by precisely these directed edges. Thus every listed template is compatible. Template \(I\) belongs entirely to center \(1\); each other template uses both centers.
The arriving masses satisfy
\(\displaystyle \lVert a_1^t\rVert_1=\frac{11s}{4},\qquad \lVert a_2^t\rVert_1=\frac{5s}{2}.\)
Since \(\mathbb E s=3/2\), the known means are
\(\displaystyle k_1=\frac{33}{8}>0,\qquad k_2=\frac{15}{4}>0.\)
The required bounds hold in both arrival states:
\(\displaystyle \lVert a_1^t\rVert_1\leq\frac{11}{2}<2k_1=\frac{33}{4},\qquad \lVert a_2^t\rVert_1\leq5<2k_2=\frac{15}{2}.\)
The arrival distribution is finite and rational. Periods are independent, while arrivals of the two centers are dependent, as permitted.
Fix either arrival state \(s\). Let \(x,y,z,w\) denote the nonnegative packing weights of \(I,E,G_1,G_2\), respectively.
The type-capacity constraints are equivalent to
\(\displaystyle x+y\leq s,\qquad z+w\leq\frac{s}{4},\qquad x,y,z,w\geq0.\)
Indeed, type \(a\) gives the first inequality and type \(h\) gives the second. Every other type appears in exactly one template, and its capacity constraint follows from these inequalities and nonnegativity.
Total matched mass is
\(\displaystyle U=2x+3y+3z+3w =3(x+y)-x+3(z+w)\leq\frac{15s}{4}.\)
The upper bound is attainable: take \(x=0\), \(y=s\), and any nonnegative \(z,w\) with \(z+w=s/4\).
Moreover, equality holds if and only if
\(\displaystyle x=0,\qquad y=s,\qquad z+w=\frac{s}{4}.\)
To verify necessity, the objective’s difference from its upper bound is
\(\displaystyle \frac{15s}{4}-U =3(s-x-y)+x+3\left(\frac{s}{4}-z-w\right).\)
All three terms are nonnegative, so equality forces each to vanish.
Center utilities are
\(\displaystyle u_1=2x+y+z+2w,\qquad u_2=2y+2z+w.\)
Consequently, every full-society maximum packing satisfies
\(\displaystyle u_1=\frac{5s}{4}+w\in\left[\frac{5s}{4},\frac{3s}{2}\right],\qquad u_2=\frac{5s}{2}-w\in\left[\frac{9s}{4},\frac{5s}{2}\right].\)
These bounds apply regardless of credits, permutation, and final tie-breaking.
Consider the two globally maximum packings
\(\displaystyle M^{(1)}=(x,y,z,w)=\left(0,s,\frac{s}{4},0\right),\qquad M^{(2)}=\left(0,s,0,\frac{s}{4}\right).\)
For center \(1\), type \(u\) has positive arriving mass \(s/4\), cannot be matched internally, and has matched mass \(0\) in \(M^{(1)}\) and \(s/4\) in \(M^{(2)}\).
For center \(2\), type \(q\) has positive arriving mass \(s/4\), cannot be matched internally, and has matched mass \(s/4\) in \(M^{(1)}\) and \(0\) in \(M^{(2)}\).
Both centers’ aggregate utilities also differ between these packings. Thus the required participation assumption holds in every arrival state, hence with probability one.
Let both centers report everything.
The only entirely center-\(1\) template is \(I\). Its maximum feasible weight on center \(1\)’s full arrivals is \(s\), so its maximum internal matched mass is exactly \(2s\).
Write \(s_t\) for the scale in period \(t\). Therefore,
\(\displaystyle B_1(T)=2\sum_{t=1}^T s_t.\)
Truthful reporting withholds nothing, so it produces no internal matches. Section 2 gives, in every period,
\(\displaystyle u_1^F(t)\leq\frac{3s_t}{2}.\)
Hence, on every arrival and permutation path,
\(\displaystyle Q_1^F(T)-B_1(T) \leq-\frac12\sum_{t=1}^T s_t \leq-\frac{T}{2}.\)
It follows that
\(\displaystyle \liminf_{T\to\infty} \frac{Q_1^F(T)-B_1(T)}{T}\leq-\frac12<0.\)
Thus long-term IR fails pathwise, from every initial credit vector and for every choice of positive coefficients.
Fix center \(2\)’s policy to report everything, independently of its credits.
Define center \(1\)’s deviating policy \(S\) to withhold all arriving mass of \(a,b\), while reporting all arriving mass of \(p,u,v\). This coordinate-wise policy is measurable and satisfies \(0\leq r_1\leq a_1\). It withholds positive mass \(2s\) in every period and reports positive mass \(3s/4\).
The withheld vector admits template \(I\) with weight \(s\), giving exactly \(2s\) internal matched mass.
In the reported society, templates \(I\) and \(E\) are unavailable because type \(a\) is absent. The clearinghouse therefore maximizes
\(\displaystyle 3z+3w\quad\text{subject to}\quad z+w\leq s/4,\quad z,w\geq0.\)
Every maximum packing has \(z+w=s/4\). Center \(1\)’s clearinghouse utility consequently satisfies
\(\displaystyle z+2w=\frac{s}{4}+w\geq\frac{s}{4}.\)
Including internal matches, its utility under \(S\) is therefore at least
\(\displaystyle 2s+\frac{s}{4}=\frac{9s}{4}.\)
Under truthful reporting its utility is at most \(3s/2\), as already proved. Coupling the two plays using identical arrivals and permutations gives, on every path,
\(\displaystyle Q_1^F(T)-Q_1^S(T) \leq\left(\frac32-\frac94\right)\sum_{t=1}^T s_t =-\frac34\sum_{t=1}^T s_t \leq-\frac{3T}{4}.\)
In particular,
\(\displaystyle \liminf_{T\to\infty}\bigl(Q_1^F(T)-Q_1^S(T)\bigr)=-\infty.\)
Even weak truthful dominance fails; the deviation withholds positive mass on every path.
Credits only determine which maximum-total packing is selected. Every full-society maximum packing gives center \(1\) strictly less than its internal benchmark. Changing coefficients cannot alter that bound.
The instance is fixed: \(n=2\), \(m=4\), \(\tau=9\), and all numerical data have constant binary length. Its construction and the displayed certificate require a constant number of rational arithmetic operations. It defeats every positive coefficient vector simultaneously, and therefore every polynomially bounded rule.
The cited discrete dominance and IR claims appear as Corollaries 1 and 2 of [Hajaj et al.](https://ojs.aaai.org/index.php/AAAI/article/download/9322/9181). The counterexample above directly analyzes the mechanism specified in this question. Its obstruction also survives multiplying every mass by four, which makes all arrival masses integral: it arises from restricting allocations to global optima while permitting internal withholding.
⟨structured verdict parsed — rendered above⟩
The counterexample is correct and resolves the stated task. It establishes that the same admissible instance defeats every positive coefficient vector, regardless of any polynomial bound. No mathematical repairs or additional clarifications are needed.
The ownership table contains exactly nine types. All arriving masses are positive binary rationals in both states, so the support size is indeed \(\tau=9\). The four explicitly permitted templates have the stated multiplicities, and every template is compatible with the specified directed edges. No altruists or chains are required by the task.
The mass calculations are correct:
\[
\lVert a_1^t\rVert_1=2s+3s/4=11s/4,\qquad
\lVert a_2^t\rVert_1=2s+2s/4=5s/2.
\]
Since \(\mathbb E s=3/2\), the means are \(k_1=33/8\) and \(k_2=15/4\). The maximum arrival masses, \(11/2\) and \(5\), respectively, satisfy the required bounds \(2k_1=33/4\) and \(2k_2=15/2\).
The two-state distribution is finite and rational. Independent draws across periods satisfy temporal independence; the shared scale creates permitted dependence between centers. The construction uses no carryover of arrivals.
The constraint reduction is exact. Type \(a\) imposes \(x+y\leq s\), while type \(h\) imposes \(z+w\leq s/4\).
The remaining constraints are \(x\leq s\) from \(b\), \(y\leq s\) from \(c,d\), \(z\leq s/4\) from \(p,q\), and \(w\leq s/4\) from \(u,v\). Each follows from the displayed two inequalities and nonnegativity. Conversely, every feasible packing satisfies those two inequalities. No capacity constraint has been omitted.
Each unit of template \(I\) matches two units; each other template matches three. Thus
\[
U=2x+3y+3z+3w
\]
is the correct total objective.
The displayed identity
\[
15s/4-U=3(s-x-y)+x+3(s/4-z-w)
\]
is algebraically correct, and every term on its right is nonnegative on the feasible region. The proposed packings attain \(15s/4\).
Equality forces \(x=0\), \(x+y=s\), and \(z+w=s/4\), which is exactly the claimed characterization. Conversely, those conditions attain the upper bound. The proof therefore characterizes every maximum packing, rather than merely exhibiting some maxima.
The ownership counts give the stated utilities:
\[
u_1=2x+y+z+2w,\qquad u_2=2y+2z+w.
\]
Substitution of the maximum-packing conditions yields
\[
u_1=5s/4+w,\qquad u_2=5s/2-w,\qquad 0\leq w\leq s/4.
\]
Both utility intervals are correct.
The two displayed packings are feasible global maxima. Type \(u\), owned by center \(1\), cannot participate in any entirely internal permitted template, and its matched mass changes from \(0\) to \(s/4\). Type \(q\), owned by center \(2\), likewise cannot be matched internally, and its matched mass changes from \(s/4\) to \(0\).
This verifies the participation condition for each center in both arrival states. The aggregate center utilities also differ, so the construction satisfies either relevant reading of the participation statement.
Center \(1\)'s only internal template is \(I\), whose maximum weight on its full arrivals is \(s\). Consequently, its internal benchmark is exactly \(2s\) per period.
Under full reporting there is no withheld mass and hence no internal contribution. Every selected clearinghouse packing remains a global maximum, so its center-\(1\) utility is at most \(3s/2\), independently of credits and permutation.
The cumulative comparison therefore follows:
\[
Q_1^F(T)-B_1(T)\leq-\frac12\sum_{t=1}^T s_t\leq-T/2.
\]
Dividing by \(T\) proves the asserted failure of long-term IR. This holds on every path; no probabilistic limit theorem is needed.
The deviating policy is a fixed coordinate projection, hence measurable and feasible. It withholds exactly the arriving masses of \(a,b\), totaling \(2s>0\), and reports \(3s/4>0\).
Its withheld vector supports \(I\) at weight \(s\), giving exactly \(2s\) internal matches. In the reported society, the zero capacity of \(a\) forces \(x=y=0\). The remaining maximum-packing condition is precisely \(z+w=s/4\).
Center \(1\)'s clearinghouse utility is then \(z+2w=s/4+w\geq s/4\). Its combined utility is therefore at least \(9s/4\), as claimed.
Center \(2\)'s fixed full-reporting policy is an allowed choice of the other center's policy. The payoff bounds hold for every selected maximum packing in both plays. Thus different evolving credit balances do not compromise the coupled comparison:
\[
Q_1^F(T)-Q_1^S(T)\leq-\frac34\sum_{t=1}^T s_t\leq-3T/4.
\]
This implies convergence to \(-\infty\), and therefore the stated liminf. Weak truthful dominance already fails, while positive withholding occurs on every path.
Neither comparison restricts initial credits or coefficient values. Credits only select among global maxima, all of which satisfy the required bounds. Consequently, the fixed instance defeats every positive coefficient vector simultaneously and therefore every polynomially bounded rule.
The constant-size construction and certificate justify the stated constant number of rational arithmetic operations. Multiplying all masses by four does make every arrival mass integral and preserves the displayed packing and payoff comparisons.
The attribution of truthful dominance and long-term IR to Corollaries 1 and 2 is accurate. Those claims appear in the [cited paper](https://ojs.aaai.org/index.php/AAAI/article/download/9322/9181). The counterexample does not invoke them as supporting theorems, so its validity does not depend on reconciling their proofs with this mechanism.
No unjustified step, false assertion, missing hypothesis, or blocking issue was found. The result is an impossibility for the specified mechanism; it does not establish a computational complexity classification. Accordingly, the required continuous_status is "unresolved" despite the task itself being resolved.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.