| paper | Strategic Behavior when Allocating Indivisible Goods Sequentially |
| authors | T. Kalinowski, Nina Narodytska, T. Walsh, Lirong Xia |
| venue | AAAI 2013 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
The paper's results concern unilateral strategic choices by named agents at policy positions. The cohort model changes those players into coordinated agents choosing divisible mass actions, while preserving individual agency would require changing the policy's temporal structure and solution concept. Thus the proposed problems are plausible new batch-allocation models, but no continuous-population mirror of the anchored results survives.
fails bit b-changes — the continuum limit changes the question
The cohort construction changes the strategic unit from an individual player to a coalition controlling mass, so its SPNE is not the high-multiplicity limit of the paper's individual-player SPNE.
fatal: True
The proposed mirror targets Theorems 3 and 5; it does not provide valid continuous-population counterparts for the remaining results.
The strongest positive case I believe is a cohort, or batch, mirror. A naive nonatomic version in which every individual is infinitesimal would erase the paper’s strategic effect: one student’s pick would not change the remaining supply. The right continuous object is therefore a population of large, exchangeable cohorts whose mass moves through the paper’s finite sequential policy.
Consider a large university draft. There are finitely many student types \(A\), where a type specifies a complete Borda ranking over course-seat types, cardinal utilities, and the cohort’s positions in the draft policy. Type \(a\) has population mass \(\mu_a\), with \(\sum_a\mu_a=1\). Course type \(g\) has per-capita supply \(\sigma_g\). Thus an \(N\)-person realization has \(N\mu_a\) exchangeable students of type \(a\) and \(N\sigma_g\) copies of course \(g\), with \(N\gg |A|\).
The policy is a finite sequence of cohort turns \(a_1,\ldots,a_R\). At turn \(r\), the active cohort assigns its turn-mass \(\rho_r\) to remaining course copies. Its action is a measurable map from an interval of mass \([0,\rho_r]\) to course types. If \(x^r_g\) is the mass assigned to \(g\), then \(\sum_g x^r_g=\rho_r\), and \(x^r_g\) cannot exceed the remaining supply. Every individual still receives an integral course seat; \(x^r\) is fractional only because it aggregates many individuals. Cohort \(a\)’s payoff is its average additive utility, \(\sum_{r:a_r=a}\sum_g u_a(g)x^r_g/\mu_a\). A solution is a complete subgame-perfect strategy profile, assigning a feasible mass action after every history and satisfying backward-induction optimality for every cohort.
This is genuinely a population continuization rather than outcome-space randomization. The goods remain indivisible, the policy remains finite and sequential, and the agents still make strategic picks. The continuous instance is the per-capita representation of the \(N\)-copy batch game.
My lead anchor is Theorem 3, proved in this paper. It states:
With an unbounded number of agents and Borda utilities, computing a subgame perfect Nash equilibrium is PSPACE-hard.
The proof reduces from QSAT. Variable agents choose between two items representing truth values; additional allocation gadgets copy those choices into clause tests and feed the result back to the quantifier agents. The construction has polynomial size, and the first agent’s utility crosses the threshold \(2m-5\) exactly when the quantified formula is true. Thus the hardness is about strategic sequential interaction and quantifier alternation, not about an encoding artifact.
The corresponding continuous problem is:
\(\textsc{Cohort-SPNE}_{\infty}\). Given rational cohort masses \(\mu_a\), rational per-capita supplies \(\sigma_g\), Borda rankings, a finite sequential policy, and a rational encoding of the mass-action histories, compute an exact subgame-perfect equilibrium of the resulting finite-stage mass allocation game, together with its induced aggregate allocation.
The authors should recognise this as their problem with repeated, exchangeable agents and repeated goods. It preserves the underlying strategic question: should a cohort take its currently best course, or sacrifice that pick to influence which course remains for its later turn? The only new feature is that a cohort can divide its mass among integral course assignments.
My expectation is that the general problem remains hard, so this is likely a Class B mirror when the number of cohort types and policy roles are part of the input. The QSAT alternation lives in the policy and in the strategic roles, and those roles can each be represented by a positive-mass cohort repeated \(N\) times. However, hardness does not transfer automatically: the continuous action space permits fractional cohort assignments, so a proof would need to force optimal mass actions to be all-or-nothing. In a fixed-\(|A|\) regime, I would instead expect a possible Class A result based on piecewise-linear dynamic programming or continuous optimization. That contrast is itself a useful question: does high multiplicity remove the hardness, or does the policy’s strategic alternation survive it?
A second, independently useful anchor is Theorem 5, also proved here. It states:
For any number of agents, a subgame-perfect Nash equilibrium can be computed in \(O(k!m^{k+1})\) time, where \(k\) is the number of multi-valued items and \(m\) is the number of single-valued items.
Here an item is multi-valued if two agents assign it different utilities; otherwise it is single-valued. The algorithm exploits the structural fact that single-valued items can be permuted so that agents always receive the best remaining single-valued item unless they choose a multi-valued item. The result is polynomial when \(k\) is fixed, though it is not an FPT bound in the usual parameterized sense because the exponent depends on \(k\).
The continuous counterpart is:
\(\textsc{Sparse-Cohort-SPNE}_{\infty}(K)\). Use the same mass sequential-allocation model, but let course types rather than individual copies be the basic repeated goods. At most \(K\) course types are contested: their utility varies across cohorts. Every other course type has the same utility for every cohort. Given the rational masses, supplies, policy, and utilities, compute one exact subgame-perfect mass allocation.
This is natural for a large course draft with many generic seats and only a few genuinely cohort-specific courses or placements. I would expect a Class A result for fixed \(K\): common-valued mass should admit the continuous analogue of the paper’s greedy permutation argument, while the contested part could be handled by a \(K\)-dimensional dynamic program or LP-based procedure. The key follow-up is whether the dependence can be made polynomial in the number of cohorts, course types, and encoding length, with only \(K!\) or otherwise controlled dependence on \(K\).
The weakest point is the cohort coordination. If the referee insists that all continuum members are independent nonatomic agents, then an individual deviation has zero effect on future supply and the paper’s strategic phenomenon largely disappears. My mirror therefore uses a batch policy in which an exchangeable cohort is the strategic unit—plausible for program offices, student blocs, or institutional representatives, but a real co-modification of the mechanism. A second limitation is that Theorem 3’s reduction uses many specialised gadget agents, so its hardness should not be advertised as hardness for a fixed-small-type regime.
Still, the mirror covers the paper’s central computational result: sequential strategic allocation with additive utilities and backward induction, now posed over a high-multiplicity society with per-capita supplies and integral bundles. It does not claim to mirror every theorem in the paper, especially the two-agent and strategy-proofness results.
The negative case turns on the unit of strategic agency. In this paper, an agent is not merely a preference type. An agent is a named player occupying particular positions in the policy \(O\), with a particular continuation game after each of those positions. That makes identity and temporal position part of the computational object.
For Theorem 3, this is essential. The QSAT reduction uses one-off agents as quantified variables, clause testers, feedback devices, and the distinguished first player whose utility is compared with a threshold. Duplicating such agents does not produce a high-multiplicity version of the same game. If the copies act independently, there are now many Boolean choices rather than one choice per quantified variable, and the clause gadget receives an aggregate of inconsistent choices. If they are forced to act together, the “cohort” has become a coalition or a new player controlling many turns. Subgame-perfect Nash equilibrium in the paper permits unilateral deviations by individual agents; it does not permit treating a positive-mass group as a single coordinated decision maker.
The proposed cohort model therefore changes the central strategic object. Its mass action \(x^r\) is a divisible collective action, and its payoff is an average payoff for the cohort. That is a potentially interesting weighted sequential-allocation game, but it is not the high-multiplicity relaxation of the paper’s extensive-form game. The fact that the individual course seats remain integral does not repair this: the strategic choice has still been convexified from one agent selecting one item to a collective assigning mass across items.
There is also no clean way around the policy. Retaining individual agents requires repeating the policy \(N\) times, so the order of the \(N\) turns becomes part of the instance. A distribution over types does not retain that order. Retaining it explicitly leaves the problem essentially an ordered extensive-form game with \(N\)-dependent temporal structure; compressing it into cohort turns replaces individual play by batch play. Either route changes something fundamental. This is not an objection that the resulting answer might be easy. It is an objection that the nontrivial strategic question being computed is no longer the paper’s question.
The university-draft story does not quite solve this. Students may share preferences, but their priority positions in the draft are strategically relevant. Once position is included in the complete type, students occupying different positions are different types. If a whole cohort is assigned a block decision, then the strategic unit is the cohort or its representative, not the individual student. That may be a sensible new mechanism, but high multiplicity alone does not justify merging the players.
Theorem 5 has a separate problem. Its parameter \(k\) counts individual items whose utilities differ across agents. If supplies are scaled with population, every copy of a contested course remains multi-valued, so the paper’s \(k\) grows with the number of copies. Replacing \(k\) by the number \(K\) of contested course types is not a continuous reading of the theorem; it is a new parameter and a new model. Likewise, the proof’s permutation argument concerns a finite list of item identities and individual turn positions. With mass course types, those identities disappear, while the policy positions that determine strategic incentives remain.
One can certainly formulate a new problem with \(K\) contested good types, cohort players, per-capita supplies, and mass actions. But then the computational content comes from the newly introduced batch mechanism and its continuous action space, not from a high-multiplicity version of Theorem 5. The theorem supplies no genuine bridge to that model: its \(k!\,m^{k+1}\) structure is about finite item identities, not about a population distribution.
Thus both anchors face the same obstruction. The paper’s agents are structurally individuated by their roles in a sequential game. Keeping those roles preserves the original problem but leaves only finitely many strategically relevant agents; aggregating them into positive-mass cohorts produces a different game. I do not think this proves that a mean-field or batch version could never be worthwhile. It does show that the proposed mirrors are not continuizations of this paper in the programme’s high-multiplicity sense. The negative case is weakest precisely because a genuinely new cohort mechanism might deserve study, but that would be a new sequential-allocation model, not a continuous mirror of these results.
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.