| paper | Fair Division with Two-Sided Preferences |
| authors | Ayumi Igarashi, Yasushi Kawase, Warut Suksompong, Hanna Sumita |
| venue | IJCAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.1
statement extracted from the paper’s text layer
Given two teams, a finite set of complete types \(T\), rational masses \(\lambda_t\ge0\), type preferences \(\succeq_t\), rational nonnegative values satisfying \(v_1(t)=v_2(t)\), and a rational allocation \(x=(x_{it})\) with \(\sum_i x_{it}=\lambda_t\) and \(\left|\sum_t x_{1t}-\sum_t x_{2t}\right|\le1\), decide whether \(x\) is Pareto optimal under divisible type-mass transport: does there exist \(z_{i,j,t}\ge0\) and \(y_{jt}=\sum_i z_{i,j,t}\) such that \(\sum_j z_{i,j,t}=x_{it}\), \(z_{i,j,t}=0\) whenever \(j\not\succeq_t i\), \(V_i(y)\ge V_i(x)\) for both teams, and either \(V_i(y)>V_i(x)\) for some team or positive mass moves along a strict preference \(j\succ_t i\)?
A two-team high-multiplicity assignment market in which complete types \(t\) encode preferences \(\succeq_t\) and common team values \(v_1(t)=v_2(t)\); rational mass \(\lambda_t\) is split by \(x_{it}\), and Pareto improvements are transports \(z_{i,j,t}\) along weak-preference arcs, evaluated by additive utilities \(V_i(x)=\sum_t v_i(t)x_{it}\).
The continuous Pareto predicate may collapse to a simple flow or opposing-mass test, losing much of the discrete theorem's combinatorial content; this limits substantive payoff but does not make the mirror noncomputational or unrecognizable.
fatal: False
The mirror covers Theorem 4.1 through continuous Pareto optimality over type masses. It leaves the swap-stability results, most existence and algorithmic results for EF1 plus PO, and the justified-envy results untouched; the proposed Theorem 4.3 mirror is rejected because its EF1 analogue is not canonical.
The strongest mirror is a high-volume branch-assignment or sports-draft market. There are two teams or branches and a very large pool of players, applicants, or tasks. A type \(t\) is the complete tuple consisting of the player’s weak preference order over teams and the vector \((v_1(t),\ldots,v_n(t))\) of values that teams assign to that player. Thus two players are the same type only when they are indistinguishable for every condition in the paper. Cohorts from standardized training programmes, recruitment pipelines, or youth-league categories make this a credible high-multiplicity regime: \(N\) may be in the hundreds of thousands while \(\tau\) is in the tens or hundreds.
Let \(\lambda_t\in\mathbb{Q}_{\ge0}\) be the mass of type \(t\), with \(\Lambda=\sum_t\lambda_t\), and let \(x_{it}\) be the mass of type \(t\) assigned to team \(i\). Team \(i\)’s utility is \(V_i(x)=\sum_t v_i(t)x_{it}\). The finite population with \(N_t\) identical clones of type \(t\) is recovered by taking \(\lambda_t=N_t\) and restricting \(x_{it}\) to integer values; the continuous mirror permits real mass assignments. In normalized form, \(\mu_t=\lambda_t/\Lambda\).
My lead anchor is Theorem 4.1, proved in this paper: deciding whether an allocation is Pareto optimal is coNP-complete, even with two teams, identical valuations, nonnegative-value players, and a balanced allocation.
The corresponding problem is Mass-PO-Certificate. An instance consists of two teams, finitely many complete player types, rational masses \(\lambda_t\), rational nonnegative valuations satisfying \(v_1(t)=v_2(t)\), and a candidate allocation \(x\) satisfying \(\left|\sum_t x_{1t}-\sum_t x_{2t}\right|\le 1\). The question is whether \(x\) is Pareto optimal in the following measure-theoretic sense.
A reallocation \(y\) is a Pareto improvement if there are transport variables \(z_{i,j,t}\ge0\), where \(z_{i,j,t}\) is mass of type \(t\) moved from team \(i\) to team \(j\), such that
\[ \sum_j z_{i,j,t}=x_{it},\qquad y_{jt}=\sum_i z_{i,j,t}, \]
\(z_{i,j,t}=0\) whenever \(j\not\succeq_t i\), and \(V_i(y)\ge V_i(x)\) for every team. At least one team must be strictly better off, or a positive mass of some type must move to a strictly preferred team. The solution is “yes” if no such \(y,z\) exist; otherwise the transport plan is a certificate of non-optimality.
I expect Mass-PO-Certificate to be in \(\mathrm{P}\), hence a Class A mirror. Given \(x\), the existence of an improvement is a rational linear-programming question with \(O(n^2\tau)\) transport variables. Strict improvement can be detected by maximizing the sum of team-utility gains and the mass moved along strict-preference arcs. In the paper’s hard instance, the difficult object is an indivisible reassignment of individually named players. Once repeated player types become mass and reassignment becomes a flow, the relevant feasible region is a transportation polytope. The coNP-hardness is therefore exactly the kind of population-integrality obstruction continuization may dissolve.
This is not merely saying that the outcome is fractional. The continuous object is the player population: the input is a distribution over complete two-sided player types, and the decision variable is a type-mass allocation. Player preferences and team valuations remain part of the computational predicate. The model also avoids atomless-voter vacuity: a strict improvement is witnessed by a positive mass of players, not by a zero-measure individual.
A second, constructive anchor is Theorem 4.3, also proved here. It states that for two teams, an EF1, Pareto-optimal, and team-Pareto-optimal allocation can be computed in \(O(m^2)\) time.
The corresponding problem is Two-Team Mass-EF1-PO-TeamPO. Its instance consists of two teams, type masses \(\lambda_t\), arbitrary rational team values \(v_i(t)\), player preference orders \(\succeq_t\), and a designated player-packet mass \(\rho\). An allocation is \(x_t=x_{1t}\), with team \(2\) receiving \(\lambda_t-x_t\). For each ordered pair of teams \(i,j\), mass-EF1 requires that either team \(i\) does not envy team \(j\), or its envy can be removed by deleting at most \(\rho\) mass of one type from one of the two bundles:
\[ V_i(x_i-r e_t)\ge V_i(x_j) \]
or
\[ V_i(x_i)\ge V_i(x_j-r e_t), \]
for some type \(t\) and \(0\le r\le \rho\). When \(\rho=1\), masses are integral, and \(r\) is restricted to one whole player, this is exactly the paper’s EF1 condition. The allocation must also be PO and team-PO under the transport definitions above, with team-PO dropping the player-preference restriction.
The question is to find such an \(x\), optionally minimizing total player dissatisfaction \(\sum_{i,t}x_{it}\operatorname{rank}_t(i)\) among feasible solutions. I expect this mirror to be Class A. With two teams, the generalized adjusted-winner procedure underlying Theorem 4.3 becomes a threshold calculation over type masses: types can be sorted by the relevant value ratios, and each threshold interval gives a linear feasibility problem. The EF1 conditions have only two envy directions, so the possible type removed from each side can be enumerated. PO and team-PO can be checked using the associated two-team transport and utility-frontier calculations. The natural running time should depend polynomially on \(\tau\), the bit length of the masses and values, and the number of teams, rather than on the total number of players.
Theorem 4.3 is particularly recognizable to the authors because the mirror retains all of the paper’s substantive ingredients: two-sided preferences, additive team valuations, EF1, PO, and team-PO. Only the repeated-player population is compressed into type mass. The continuous question is not claiming that arbitrary fair division becomes easy; it isolates the paper’s especially tractable two-team branch.
I would not use Theorem 5.2 as a primary anchor without a new proof. That theorem proves NP-completeness for deciding whether an EF1 and justified-EF allocation exists. Its justified-envy condition is pairwise and could plausibly retain hardness through a forbidden-support graph even after type compression. But fractional splitting of one type across teams may also destroy the reduction’s gadget, which forces discrete numbers of vertex players. A valid continuous version would need an explicit no-splitting or gap lemma. This is a useful boundary question, not evidence that the mirror automatically inherits the theorem.
The weakest point is the treatment of EF1. In an atomless limit, “remove one player” has vanishing mass and EF1 tends toward exact envy-freeness. My second mirror therefore has an explicit packet parameter \(\rho\); it is a continuous high-multiplicity relaxation with a retained player-scale, not a literal atomless limit of indivisible allocations. If that distinction is rejected, Mass-EF1-PO-TeamPO should be downgraded. The lead Mass-PO-Certificate is less vulnerable: its transport definition is the natural Pareto notion for a distribution of exchangeable player types, and its LP formulation remains a genuine population-continuization of Theorem 4.1.
The main follow-up questions are whether the \(\rho\to0\) limit yields exact EF plus PO and team-PO, whether continuous solutions can be rounded to finite clone allocations with bounded loss, and whether the two-team Class A picture survives for three or more teams. This case deliberately covers only Theorems 4.1 and 4.3; it does not claim to continuize the paper’s entire fair-division programme.
The strongest case against the proposed mirror is that both anchors depend on the one-player atom, and the continuous replacement removes that atom in two incompatible ways.
For Theorem 4.1, the collapse is especially clear. Under its hard restriction, there are two teams with identical valuations, so write \(v(t)=v_1(t)=v_2(t)\). For a mass allocation \(x\), let
\[ A=\sum_{t:\,1\succ_t2}v(t)x_{2t} \quad\text{and}\quad B=\sum_{t:\,2\succ_t1}v(t)x_{1t}. \]
Mass \(A\) can move toward team \(1\), and mass \(B\) can move toward team \(2\). Because mass is divisible, every utility amount in \([0,A]\) and \([0,B]\) is attainable. If \(A,B>0\), choose the same small positive utility amount in both directions. Both teams’ utilities remain unchanged, while a positive mass of players strictly improves. Thus the candidate is not Pareto optimal. Apart from zero-valued types, Pareto optimality reduces essentially to the absence of opposing strictly preferred mass.
The discrete theorem is asking whether whole player values can be balanced exactly by a subset of indivisible players. The mass version replaces those attainable values by connected intervals. This is not merely an encouraging polynomial answer: the global Pareto predicate that made Theorem 4.1 interesting has disappeared. To preserve it, one must prohibit splitting, which restores an integer allocation; alternatively, one can retain distinct weights, but then every weight becomes its own type and the supposed high-multiplicity compression vanishes.
The proposed balancedness condition also has no scale-free meaning. On normalized mass, a difference bounded by \(1\) is vacuous; on unnormalized mass, it depends on the arbitrary unit in which population is measured. Exact equality, or a tolerance of \(1/\Lambda\), is a reasonable repair, but it confirms that the discrete “one-player” scale is external to the continuous society.
Theorem 4.3 has the same problem more directly. EF1 is defined by deleting one indivisible player. If total population is \(\Lambda\), the natural clone interpretation makes the normalized deletion size \(1/\Lambda\), so the limit is exact envy-freeness. A fixed normalized \(\rho\) instead gives a different notion—envy up to a prescribed fraction of the population. A fixed unnormalized \(\rho\) changes when the same society is rescaled. And if one deletes a whole packet rather than arbitrary mass, the model has reintroduced indivisible units.
The proponent’s formula with \(0\le r\le\rho\) therefore does not recover EF1: it permits shaving an arbitrarily chosen fraction of a type. Restricting \(r\) to one whole clone recovers the paper’s predicate only by abandoning the continuous assignment. Exact EF plus PO and team-PO may be a legitimate fractional fair-division problem, but it is a new problem whose central compatibility phenomenon is no longer EF1’s compatibility with efficiency.
Theorem 5.2 does not repair this. Its reduction relies on whole vertex players and pairwise comparisons between named players. A support-based mass version becomes a type-level stability condition; fractional mass can split the role of a selected vertex across teams. Preventing that requires indivisible packets, while a positive-mass threshold introduces the same arbitrary scale parameter.
The cohort scenario is not implausible, so this is not a proof that no publishable fractional assignment model exists. Mass-PO is well-defined, and a paper could study it as a baseline or develop rounding results. But as evidence for a worthwhile ChoCo mirror, the two anchors are weak: Theorem 4.1 degenerates into a local flow condition, while Theorem 4.3 has no canonical continuous EF1 analogue. The negative case is therefore a strong objection to these mirrors, though not an airtight universal impossibility claim.
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.