| paper | Mechanisms for Fair Allocation Problems: No-Punishment Payment Rules in Verifiable Settings |
| authors | G. Greco, Francesco Scarcello |
| venue | JAIR 2014 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 6.1
statement extracted from the paper’s text layer
Given finite worker types \(T\), job classes \(G\), rational masses \(\mu\), rational per-capita supplies \(\rho\), capacities \(\zeta_t\), verified values \(v_{tg}\), and an optimal mass allocation \(y^\star\) over integral bundles \(b\), define \(F_\rho(\nu)=\max\{\sum_{t,b}y_{t,b}v_t(b):\sum_b y_{t,b}=\nu_t,\ \sum_{t,b}b_g y_{t,b}\le\rho_g,\ y_{t,b}\ge0\}\) for \(\nu\le\mu\), where \(b\in\mathbb{Z}_{\ge0}^{G}\) and \(\sum_g b_g\le\zeta_t\). Under replication with \(N\mu_t\) workers of type \(t\) and \(N\rho_g\) jobs of class \(g\), compute exactly \(u_t=\int_0^1D_tF_\rho(\lambda\mu)\,d\lambda\) and \(P_t=\mu_tu_t-\sum_b y^\star_{t,b}v_t(b)\) for every \(t\) with \(\mu_t>0\), using verified values on the allocated support.
A high-multiplicity assignment market in which type mass \(\mu\) receives integral bundles, job classes have per-capita supplies \(\rho\), aggregate bundle masses \(y_{t,b}\) maximize verified welfare, and each type's payment is its Aumann–Shapley utility \(U_t=\mu_t\int_0^1D_tF_\rho(\lambda\mu)\,d\lambda\) minus its allocated verified value.
The paper does not itself specify the Aumann–Shapley normalization or prove convergence under the chosen scaling of \(\rho\), so a prover must establish that this is the appropriate high-multiplicity limit rather than merely one plausible fluid variant.
fatal: False
The mirror covers the \(\#\mathrm{P}\)-complete Shapley-value and payment-computation results in Theorem 6.1 and Corollary 6.2. It leaves the truthfulness, fairness, error-tolerance, and randomized-payment results unmirrored.
The strongest positive case is a single mirror, anchored on the paper’s payment-complexity result.
The lead anchor is Theorem 6.1, proved in this paper. It states that computing the Shapley value of the allocation games introduced in Definition 5.1 is \(\#\mathrm{P}\)-complete. For a coalition \(C\), the “best” game has value \( \mathrm{best}_w(C)=\operatorname{opt}(\langle C,G,\zeta_t\rangle,w_t) \), while the dual marginal game has value \( \mathrm{marg}_w(C)=\operatorname{opt}(\langle A,G,\zeta_t\rangle,w_t)-\operatorname{opt}(\langle A\setminus C,G,\zeta_t\rangle,w_t) \). The paper proves hardness by reducing from counting perfect matchings: it creates nine agent clones for every graph edge, and the Shapley value of a distinguished agent encodes the numbers of matchings of every cardinality. Corollary 6.2, also proved here as an immediate consequence of Lemma 4.8 and Theorem 5.5, specializes this statement to the mechanism itself: computing the payments \(p_\xi\) is \(\#\mathrm{P}\)-complete. I regard these as one hardness anchor, with Corollary 6.2 making the mechanism-design interpretation explicit.
A natural high-multiplicity regime comes from the paper’s own cooperative scheduling and task-allocation application. Imagine a large dispatch platform with \(N\) workers and \(N\)-scale batches of jobs. Workers have one of finitely many complete profiles: skill level, capacity, eligibility, speed, and values for job classes. Jobs are individually indivisible, but many jobs belong to the same objectively measurable class. A realistic instance might have hundreds of thousands of workers but only a few dozen or a few hundred worker types. A type is complete in the paper’s sense: workers with the same type are indistinguishable for capacity, valuation, verification, and payment purposes.
The continuous instance is a rational distribution \( \mu=(\mu_t)_{t\in T} \) of worker types and rational per-capita supplies \( \sigma=(\sigma_g)_{g\in G} \) of job classes. A unit of population still receives an integral bundle. If \(b\in\mathbb Z_{\ge 0}^{G}\) is a bundle with \( \sum_g b_g\le \zeta_t \), let \(y_{t,b}\) be the mass of type \(t\) receiving \(b\). The allocation variables satisfy \( \sum_b y_{t,b}=\mu_t \) and \( \sum_{t,b}b_g y_{t,b}\le\sigma_g \). Thus \(y\) is fractional only at the aggregate level: it mixes integral bundles across a repeated population.
Given an optimal allocation \(y^\star\), let \( \rho_g \) be the mass of actually allocated jobs of class \(g\), and let \(v_t(b)=\sum_g b_gv_{tg}\) be the verified value of bundle \(b\). For every subpopulation \( \nu\le\mu \), define the underlying allocation-game value
\[ F_\rho(\nu)=\max_y \sum_{t,b}y_{t,b}v_t(b), \]
subject to \( \sum_b y_{t,b}=\nu_t \) and \( \sum_{t,b}b_gy_{t,b}\le\rho_g \). This is the continuous analogue of the paper’s \( \mathrm{best}_w(C) \) game, using only the verified image of the chosen allocation, just as \(p_\xi\) does.
The named continuous problem is:
Continuous No-Punishment Shapley Payment Computation. Given \(T,G,\mu,\rho,\zeta,v\), and an optimal mass allocation \(y^\star\), compute the exact type-level Shapley utilities and payments. For each type \(t\), define its per-unit utility by the high-multiplicity Shapley limit
\[ u_t=\int_0^1 D_tF_\rho(\lambda\mu)\,d\lambda, \]
where \(D_tF_\rho\) is the right marginal value of adding type-\(t\) mass. The total utility of type \(t\) is \(U_t=\mu_tu_t\). Its payment is
\[ P_t=U_t-\sum_b y^\star_{t,b}v_t(b). \]
The required output is the vector \( (P_t)_{t:\mu_t>0} \), or equivalently the type-level utilities and payments. Reports may determine \(y^\star\), but after allocation the values on its support are replaced by verified values; changing declarations about unallocated jobs must not change the payment. That preserves the paper’s no-punishment and partial-verification semantics.
This is genuinely a population continuization. For a common denominator \(N\), the corresponding finite instance has \(N\mu_t\) agents of type \(t\) and \(N\sigma_g\) job copies of class \(g\). Every agent still receives an integral bundle. Under a uniformly random finite ordering of agents, the predecessor population converges to \( \lambda\mu \), so the displayed integral is the natural \(N\to\infty\) limit of the paper’s finite Shapley payments. The parallel marginal game is \(M(\nu)=F_\rho(\mu)-F_\rho(\mu-\nu)\), mirroring the paper’s equality between the best and marginal Shapley values.
I expect this continuous problem to be Class A, although the exact classification is itself worthwhile. The allocation value \(F_\rho\) is a transportation or matching LP with fractional type masses, and each individual bundle remains integral. In the paper’s \(\#\mathrm{P}\)-hardness construction, the difficulty comes from enumerating individually distinguishable coalitions and thereby counting matchings. After aggregation, the nine clones associated with one edge become mass of one edge type; the relevant optimization is fractional matching, not counting edge subsets. The remaining exact question is whether the one-parameter integral of LP marginal values can be computed with polynomial bit complexity. Even if exact integration has unexpectedly many breakpoints, the problem has a clear approximation route through the paper’s sampling ideas.
This mirror covers the paper’s payment-computation contribution, not every fairness theorem. It generates further questions about exact parametric-LP integration, finite-\(N\) approximation error, rounding an aggregate allocation back to integral bundles, and whether budget balance and individual optimality survive at the type level.
The weakest point is incentive compatibility. In an atomless population, one infinitesimal worker cannot change the aggregate report or allocation, so individual dominant-strategy truthfulness becomes vacuous unless the model also permits positive-mass type coalitions or retains finite atoms. I would therefore not claim that Theorem 4.9 transfers automatically. The positive case is narrower but still substantial: the paper’s own named \(\#\mathrm{P}\)-complete payment problem has a natural high-multiplicity continuous form, and its central question is precisely whether the population-level counting obstruction disappears when identical agents are represented by mass.
The only serious negative argument targets the anchor itself: Theorem 6.1 and Corollary 6.2 derive their \(\#\mathrm{P}\)-hardness from the Shapley value over coalitions of individually named agents. In the reduction, the nine clones associated with each edge are deliberately separate players. The hard quantity is the enumeration of subsets of those players encoding matchings.
Once those players are replaced by mass, the paper’s Shapley value disappears. A nonatomic individual has zero marginal contribution, while a Shapley value over type masses is not defined by the paper. The proposed formula
\[ u_t=\int_0^1 D_tF_\rho(\lambda\mu)\,d\lambda \]
is instead an Aumann–Shapley-style value for a newly defined fluid game. It may be a sensible object, but it is not the payment rule \(p_\xi\) whose computation is proved \(\#\mathrm{P}\)-complete. The key combinatorial information—whether a coalition contains one particular clone, or several clones of the same edge—is erased. Retaining those distinctions preserves the original finite-player problem rather than continuizing the population; erasing them replaces the fairness concept and its computational content.
There is also no unique continuous extension forced by the paper. One can hold the verified image \(\rho\) fixed while scaling the population, scale available goods with the coalition, or define payments over type blocks rather than infinitesimal agents. These choices produce different marginal paths and different payment rules. The paper’s axioms do not select the displayed path, so the proposed problem needs an additional modelling decision that is external to the result being mirrored.
That is the strongest case against the anchor, but it is not decisive under the programme’s rules. The proponent has supplied a plausible high-multiplicity regime: repeated worker profiles, repeated job classes, and per-capita supplies. Aggregate allocations can still mix integral bundles while remaining exact finite allocations after replication. More importantly, the proposed integral is plausibly the limit of the finite Shapley payments under a specified replication scheme. The fact that the \(\#\mathrm{P}\) obstruction may vanish is precisely the kind of computational question the programme is meant to expose, not an objection to asking it.
Thus I cannot honestly defeat this anchor. The continuum-specific Shapley/Aumann–Shapley limit is a legitimate computational mirror, even though it no longer preserves individual truthfulness and requires a carefully stated replication convention. The negative case is therefore weak: it identifies a change of solution concept, but cannot show that the resulting continuous payment problem is unworthy of study.
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.