| paper | Mechanism Design for Team Formation |
| authors | Mason Wright, Yevgeniy Vorobeychik |
| venue | AAAI 2015 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Neither anchored proposition has the required computational character: Proposition 1 is a finite-instance impossibility result, while Proposition 6 is a strategic and fairness theorem. The anonymous high-multiplicity team-market questions are coherent extensions, but they are new computational problems rather than continuous analogues of computational results in this paper. Therefore bit (a) fails and the mirror is red.
fails bit a — no named computational result to mirror
The proposed mirror covers anonymous high-multiplicity team-pattern feasibility, one-teammate envy, welfare, and the A-CEEI-TF price-taking setting; it leaves the draft mechanisms and empirical claims untouched.
The strongest honest positive case is a narrow yes: this paper supports a high-multiplicity mirror of its team-formation and fairness problem. It does not, however, contain a named NP-hardness, polynomial-time, W[1]-hardness, or FPT result. The anchors below are therefore mechanism-theoretic propositions, not complexity anchors.
The natural regime is a large organisation forming many project teams from recurring cohorts. Suppose there are \(n\) students or employees, with \(n\gg \tau\), where each agent belongs to one of finitely many complete types: role, seniority, location, skills, and the entire vector of values assigned to teammate types. Two agents of the same type are interchangeable for the model. A plausible example is a university repeatedly forming thousands of three-person teams from a fixed collection of degree and skill profiles. Preferences need not be uniform across all agents; they need only be identical within a type.
My lead anchor is Proposition 1, proved in this paper. It states that there may be no partition whose envy is bounded by a single teammate. The paper’s witness has six agents \(A,\ldots,F\), exactly two teams of size \(3\), and additive values
\[ \begin{array}{c|rrrrrr} &A&B&C&D&E&F\\ \hline A&-&0&1&2&4&8\\ B&8&-&4&2&1&0\\ C&8&0&-&4&2&1\\ D&8&1&0&-&4&2\\ E&8&2&1&0&-&4\\ F&8&4&2&1&0&- \end{array} \]
where row \(i\), column \(j\), is \(u_i(j)\). Proposition 1 concludes that no partition into two teams of size \(3\) gives every agent envy bounded by one teammate. The proof uses the fact that, apart from \(A\), every agent has a preferred partner cycle; three agents must be outside \(A\)’s team, and one of them misses both \(A\) and its second favourite.
The continuous mirror is:
Continuum Envy-Bounded Team Formation. An instance consists of a finite type set \(\Theta\), a population distribution \(\mu\in\Delta(\Theta)\), nonnegative type-level values \(v_{\theta\phi}\), and team-size bounds \(k,\bar k\). A feasible team pattern is a multiset \(S\) of types with \(k\le |S|\le\bar k\). Let \(\lambda_S\) be the mass of teams having pattern \(S\). The allocation must satisfy
\[ \sum_S n_\phi(S)\lambda_S=\mu_\phi \qquad\text{for every }\phi\in\Theta, \]
where \(n_\phi(S)\) is the number of \(\phi\)-agents in \(S\).
For a type-\(\theta\) agent in a team \(S\), utility is
\[ U_\theta(S)= \sum_{\phi\in\Theta} \bigl(n_\phi(S)-\mathbf 1_{\phi=\theta}\bigr)v_{\theta\phi}. \]
The question is whether there exists a feasible \(\lambda\) such that, whenever \(\lambda_S>0\) and \(\lambda_{S'}>0\), every type-\(\theta\) agent assigned to \(S\) satisfies
\[ U_\theta(S)\ge U_\theta(S'\setminus\{\phi\}) \]
for some teammate type \(\phi\in S'\). If several such allocations exist, maximise social welfare
\[ \operatorname{SW}(\lambda) = \sum_S \lambda_S \sum_{\theta\in\Theta} n_\theta(S)U_\theta(S). \]
This preserves the paper’s underlying problem exactly: agents still receive integral teams of people, preferences are still additive over teammates, and the same envy notion is used. Only the population is continuized. Fractional \(\lambda_S\) means that a fraction of the population receives each integral team composition; it does not mean that an individual receives a fractional teammate.
I would expect the general exact problem to be continuum-specifically hard, rather than hardness transferred from the finite problem. The population multiplicity disappears, but the difficult combinatorics of selecting mutually compatible team-patterns and determining which patterns are present remain. For fixed team size, the welfare and marginal constraints form a configuration LP, so the optimisation part is tractable in restricted variants; the support-sensitive envy condition is the likely source of Class C behaviour. Further questions include whether Proposition 1’s impossibility survives for particular type distributions, whether it disappears after allowing mass splitting, and whether one can compute the maximum fraction of agents whose envy can be bounded by one teammate.
My second anchor is Proposition 6, also proved in this paper. It states that A-CEEI-TF is strategyproof-in-the-large. In addition, if A-CEEI-TF achieves exact market clearing and induces the same allocation at every stage of its price search, then it yields envy bounded by a single teammate. The paper’s proof explicitly replaces each agent by a measure-one continuum of replicas, so that an individual has zero measure and cannot affect equilibrium prices.
The corresponding computational mirror is:
Continuum A-CEEI Team Formation. Given \((\Theta,\mu,v,k,\bar k)\), a budget rule, and a tolerance \(\varepsilon\), compute prices \(p_\phi\) for teammate types and a team-pattern distribution \(\lambda\) such that:
The output is \((p,\lambda)\), together with a certificate of market clearing or approximate clearing. The associated mechanism-design question is whether changing the report of one zero-mass agent can improve that agent’s outcome while the aggregate report distribution is fixed.
This is not merely restating Proposition 6. The paper uses a continuum economy only as a limiting argument for incentive compatibility; it never formulates the society as \(\mu\), never represents team formation by a distribution over type-patterns, and never studies the computational problem of finding prices and a market-clearing team allocation. The mirror turns the paper’s continuum thought experiment into the central computational object.
For bounded team size and finitely many types, I would expect this second problem to be Class A: it is a configuration-market problem with linear mass constraints, and demand pricing can be handled by column generation or convex optimisation. The important boundary question is whether tractability survives variable team sizes, exact rather than approximate clearing, and the recursive “leaves a feasible subproblem” condition.
The mirror therefore covers the paper’s core team-formation problem, its fairness objective, and its A-CEEI-TF mechanism. It does not claim to continuize RSD, HBS, or OPOP: their random serial order and named-player choices do not have an automatic atomless analogue.
The weakest point is that team formation may genuinely depend on personal relationships rather than type-level substitutability. If every agent has idiosyncratic values for every named teammate, then the number of complete types is essentially the population size and the high-multiplicity regime loses force. The positive case therefore applies to recurring, role-based team markets—not to every finite hedonic game. The paper’s own Proposition 6 nevertheless makes this a credible mirror: its strategyproofness-in-the-large argument already recognises the atomless, price-taking regime; what is missing is the explicit type-distribution model and its computational classification.
The strongest negative case is about what this paper actually contributes. It contains no numbered computational result: no complexity theorem, algorithm, approximation guarantee, or parameterized classification for team formation, welfare maximization, equilibrium computation, or manipulation. Proposition 1 is an impossibility result for one finite allocation instance; Proposition 6 is a strategic property of a mechanism. The proposed continuous problems are therefore new computational market-design problems, not high-multiplicity continuations of computational results in the paper.
Proposition 1 is especially weak as an anchor. Its witness depends on a six-agent identity graph: one distinguished agent \(A\), a directed cycle of second choices, and a finite pigeonhole argument. Replicating the agents can produce a legitimate type-pattern model, but the result then becomes a new configuration-feasibility problem over anonymous teammate types. Adding maximum welfare makes it still more clearly a new optimization problem; Proposition 1 itself says nothing computational about either question.
There is also a genuine modelling fork. If one preserves the paper’s arbitrary values \(u_i(j)\), agents are identified by their relations to named individuals, so almost every agent is its own complete type and the high-multiplicity regime disappears. If one replaces \(u_i(j)\) by \(v_{\theta\phi}\), one has imposed anonymity by role or cohort and removed the identity-specific relation network that makes the paper’s team-formation problem distinctive. A recurring cohort scenario may make that anonymous problem sensible, but it should be presented as a new type-based team-market model, not as a continuous mirror of Proposition 1.
Proposition 6 fares no better as an anchor. The paper already performs the relevant continuization: it replaces each agent by a measure-one continuum of replicas and proves that an individual cannot affect equilibrium prices. That is precisely the continuum strategic argument. Writing the population as \(\mu\) and the allocation as \(\lambda\) does not uncover a missing continuous theorem; it repackages the theorem’s limiting economy.
Moreover, the sequential A-CEEI-TF mechanism itself has no straightforward atomless version. “The next unmatched agent,” random serial order, removal of agents, and the residual feasibility test are finite-population operations. The budget interval is also tied to \(1/|N|\), so it collapses as the population grows. Dropping those features yields a static approximate competitive-equilibrium problem, not A-CEEI-TF; retaining them requires adding an ordering or identity structure that defeats the proposed type-only formulation. That equilibrium-computation problem may be worthwhile, but it is a new project rather than a mirror of Proposition 6.
The honest limitation is that the universal negative is not airtight. Large recurring cohorts with role-based teammate values do support a coherent high-multiplicity team-formation model. The best case against is therefore narrower: this paper supplies no computational result whose continuous counterpart needs charting, while its first proposed mirror changes the identity model and its second has already used the continuum argument it purports to discover. It may motivate a new paper on anonymous team markets, but it does not make a compelling continuization target for this programme.
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.