| paper | ‘Why Didn’t You Allocate This Task to Them?’ |
| authors | — |
| venue | AAAI 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper’s labeled Lemma, Corollary, and Proposition are unnumbered existence or validity claims, not named complexity or algorithmic results of the required kind. Therefore bit (a) fails regardless of whether CNAE is a plausible high-multiplicity extension. The opponent also identifies a serious mismatch between the paper’s finite named-agent negotiation tree and the proposed type-level flow model.
fails bit a — no named computational result to mirror
The proposed continuum replaces named-agent, indivisible, finite no-repeat negotiation with type-level bloc bargaining over aggregate flows, so the finite backward-induction proposition no longer transfers without defining a new game.
fatal: True
The proposed mirror covers negotiation-aware allocation, counterfactual contestation, and explanation certificates, but not the human-subject fairness and convincingness findings or noise experiments.
The strict verdict is that this paper has no qualifying computational anchor. It prints no numbered Theorem, Lemma, Corollary, or Proposition asserting membership in P, NP-hardness, parameterized complexity, or any comparable classification. Its closest named results are an unnumbered “Lemma” proving existence of an SPE, an unnumbered “Corollary” that backward induction returns an acceptable allocation, and an unnumbered “Proposition” that an explanation always exists. These are proved here, in proof sketches, rather than cited from elsewhere. The paper also explicitly observes that exhaustive enumeration may contain \(n^m\) allocations, but gives no named complexity theorem.
That means the following is the strongest positive case, but it is necessarily a provisional one rather than a programme-compliant complexity result.
The best mirror is built around the paper’s unnumbered Proposition:
“Given allocation \(o\) (the explicable allocation offered by AITA) and a counterfactual allocation \(o_i\) … there will always exist an explanation.”
I would call the continuous problem Continuum Negotiation-Aware Explanation, or CNAE.
Consider a hospital or large service operation with \(N\) workers and a large repeated roster of task slots. Workers are not treated as named individuals when they are identical for the purposes of the allocation: the same qualifications, availability, task-cost vector, incapabilities, bargaining priority, discount factor, beliefs about other workers, and beliefs about team-performance costs. Let \(T=\{1,\ldots,\tau\}\) be the resulting worker types, with mass \(\mu_k\) of type \(k\), \(\sum_k\mu_k=1\). A realistic regime might have \(10^4\)–\(10^6\) workers but only \(20\)–\(200\) types.
Let \(J=\{1,\ldots,q\}\) be repeated task or shift classes, with demand \(d_j\). The continuous allocation is a transport matrix
\[ x\in\mathbb R_{\ge 0}^{\tau\times q}, \]
where \(x_{kj}\) is the mass of type-\(k\) workers assigned to task class \(j\), subject to
\[ \sum_j x_{kj}=\mu_k,\qquad \sum_k x_{kj}=d_j. \]
Thus the continuous object is genuinely the population of workers. It is not merely a lottery over one five-task instance: a rational \(x\) is the normalized aggregate of many individual assignments in the corresponding high-multiplicity roster.
For type \(k\), define its average true cost by
\[ C_k(x)=\frac{1}{\mu_k}\sum_j c_{kj}x_{kj}, \]
where \(c_{kj}\) is the cost of assigning one unit of type \(k\) to task class \(j\). Each type may also carry the paper’s incomplete-information data \(\widehat c_{k\ell j}\), representing its estimate of another type’s cost. The allocator has a rational aggregate performance function \(P(x)\), for example a linear or piecewise-linear convex function representing completion time, coverage shortfall, or service quality.
The CNAE instance consists of these type masses, task demands, true and perceived costs, the proposer order, discount factors, a finite negotiation horizon \(H\), a baseline allocation \(x^0\), a focal type \(i\), and a counterfactual allocation \(y\). The counterfactual must satisfy
\[ C_i(y)<C_i(x^0). \]
The type-level negotiation proceeds in the paper’s round-robin style. At each round, either the allocator proposes an allocation minimizing \(P(x)\), or a worker type proposes an allocation minimizing its perceived cost. Other types accept or reject by comparing their cost at the proposed allocation with their continuation cost from the next round. Backward induction determines the subgame-perfect outcome. In the continuous version, the horizon \(H\) is explicit because the paper’s exhaustive “no previously seen allocation” rule relies on a finite allocation set and cannot be carried literally to a continuum.
A solution to CNAE is a finite contrastive certificate beginning at \(y\), consisting of the successive aggregate allocations proposed after rejection, the proposer at each step, the accepting or rejecting types, and certificates that each proposal is optimal for its proposer over the feasible allocation polytope. It must terminate at an accepted allocation \(\widehat x\) satisfying
\[ C_i(\widehat x)\ge C_i(x^0). \]
In other words, the certificate explains why the apparently better counterfactual for type \(i\) cannot survive negotiation. For linear costs and piecewise-linear \(P\), the local optimality claims can be accompanied by LP dual certificates, giving a compact analogue of the paper’s negotiation tree.
This is recognisably the authors’ problem. It retains their additive individual costs, a separate team-performance metric, mixed-motive agents, incomplete information, sequential offers, counterfactual allocations, and explanations that certify why a proposed allocation is preferable. The only change is the natural high-multiplicity regime: repeated workers and repeated task classes are represented by masses and flows. A staffing manager negotiating with representatives of interchangeable worker classes is not an unrelated optimization problem; it is the paper’s allocation-and-contestation problem at the scale where aggregate proportions are the meaningful quantities.
My expectation is that the structured version of CNAE is Class A. For a bounded horizon and linear or convex piecewise-linear cost/performance functions, the feasible allocations form a transportation polytope, and each proposal or continuation calculation is a continuous optimization problem. The question is whether the backward-induction computation and its explanation can be kept polynomial in \(\tau\), \(q\), \(H\), and the input bit length, rather than in the number of underlying workers. A full unbounded-horizon version, or one with an arbitrary nonconvex performance function, may instead become continuum-specifically hard. The paper provides no discrete hardness theorem, so there is no basis for claiming hardness transfer.
This mirror covers only the paper’s explanation-existence claim and the associated backward-induction mechanism. It does not claim to mirror the human-subject results about perceived fairness or convincingness, nor the numerical experiments on noise and explanation length. Those are empirical findings, not named computational results.
The weakest point is substantial: the paper’s proof of explanation existence depends on a finite set of allocations and exhaustive backward induction over that set. In the continuous setting, the offer space is infinite, and a naïve negotiation tree may be infinite or may have no attained “best remaining offer.” Introducing a bounded horizon and aggregate type representatives is therefore a genuine modelling choice, not a theorem that follows automatically from the paper. If the authors regard named individual bargaining and finite exhaustive enumeration as essential, they could reasonably reject CNAE as a different problem.
The positive case survives only in the narrower claim that their substantive allocation question has a credible high-multiplicity form, and that its missing computational question is precisely whether negotiation-aware allocation and contrastive explanation admit compact continuous certificates. That is a worthwhile mirror, but this paper itself does not supply the qualifying complexity anchor required by the programme.
The negative case is stronger than the proponent admits, although it is not a proof that no conceivable staffing model could be continuous. The decisive point is that this paper does not contain a qualifying computational anchor in the first place.
Its “Lemma,” “Corollary,” and “Proposition” are existence claims proved by definition and backward induction. The observation that the allocation tree may have \(n^m\) nodes is not a complexity theorem, and the approximate algorithm is evaluated numerically rather than classified. In particular, the Proposition that an explanation always exists does not assert a computational property of a problem. It says that, because the chosen allocation is defined by exhaustive backward induction over a finite game, a better accepted counterfactual cannot exist. There is no stated decision, optimization, approximation, or parameterized problem whose continuous complexity could be mirrored.
The proposed CNAE model also changes the object that the Proposition concerns. In the paper, negotiation is among named humans in a fixed round-robin order. The identity of the next proposer, the history of rejected allocations, each human’s private information, and the focal human’s own cost are all strategically relevant. Under the programme’s correct definition of type, bargaining position and turn order are part of an agent’s complete description. If they are retained, otherwise identical workers in different positions are different types, so the proposed population compression disappears. If they are discarded, “a type proposes” and “a type accepts” define a representative or bloc bargaining game that the paper never studies.
The allocation flow \(x_{kj}\) loses the paper’s central contrastive object as well. A human contests a particular assignment of particular indivisible tasks and asks why their alternative would not be accepted. A mass assignment gives a type an average workload. If the focal human is represented by a positive-mass type, the explanation is now addressed to a bloc whose members may receive different bundles; if the focal human is infinitesimal, changing their assignment changes the aggregate state by measure zero and cannot affect the continuous negotiation outcome. Tagging that person as an atom repairs the latter problem only by reintroducing a discrete individual into the model.
The proposed finite horizon is not a harmless technical adjustment. The paper’s game relies on a finite set of allocations and on excluding every previously proposed allocation. In a continuum, after excluding one optimum there need not be a next optimum: minimizing \(x\) over \([0,1]\setminus\{0\}\) has infimum \(0\) but no minimizer. A bounded horizon, a finite offer menu, or a rule permitting repeated offers therefore defines a new bargaining game. LP dual certificates can certify an optimum of one aggregate allocation problem; they do not restore the paper’s finite no-repeat negotiation tree or its backward-induction argument.
One can certainly formulate a new model in which representatives of worker populations bargain for fractional staffing plans over a bounded number of rounds. That may be an interesting optimization or bargaining problem. But it no longer mirrors the paper’s named result: individual contestability has become bloc contestability, indivisible assignments have become flows, the fixed-order negotiation tree has become a newly specified aggregate protocol, and the paper’s finite existence proof has been replaced by new equilibrium and compactness assumptions. The resulting research question would be motivated by task allocation generally, not by a computational result established in this paper.
The human-study findings cannot rescue the case. “Fair to a majority,” “convincing,” and “understandable” are empirical judgments, not computational results over which a continuous-population complexity question can be posed. Thus the proponent’s own concession is fatal under ChoCo’s screening rule: there is a plausible continuous staffing reinterpretation, but no worthwhile continuous mirror of a qualifying computational result from this paper.
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.