| paper | Differentially Private Fair Division |
| authors | — |
| venue | AAAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | unclear |
Theorems 4.7 and 4.1 are genuine named algorithmic results, and repeated utility profiles make a high-multiplicity regime plausible. However, with finite N, real mass variables assign each indivisible item to positive population mass, while sending N to infinity undermines the paper's individual privacy and proportionality semantics. The proposed mirror is therefore concrete but its central population-versus-outcome interpretation remains undecided, preventing green without justifying red.
fails bit none — no continuous question survives
With real x, each item is allocated to mass 1/N rather than one individual, and the proponent's rational-instance claim does not establish a finite lift without replicating items; taking N to infinity also loses individual-level semantics.
fatal: False
It is undecided whether a real mass assignment with item capacity 1/N preserves indivisible-item allocation, rather than representing cohort sharing or a lottery over allocations. A formal lift or rounding theorem preserving per-agent EF/PROP and agent-item DP, or an explicit acceptance of cohort semantics, would settle the issue.
The proposed mirrors cover Theorems 4.7 and 4.1, while leaving Theorems 3.1, 3.2, 4.8, and 4.10 unaddressed.
The strongest honest case is a high-multiplicity version of the paper’s ordered-facility-slot setting. My lead anchor is Theorem 4.7; Theorem 4.1 is a worthwhile secondary anchor. These are algorithmic theorems proved by the authors here—Theorem 4.7’s detailed proof is deferred to their full version—not P/NP classifications. The paper contains no named NP-hardness or membership-in-P theorem.
Consider a large organization allocating \(m\) ordered, indivisible facility slots—say appointments in a calendar, shifts in a roster, or offices along a corridor—to a population of \(N\) agents. There are only \(\tau\) distinct utility types, with \(N\gg\tau\). A type \(t\) is the agent’s complete utility function \(u_t\): for Theorem 4.7, an additive vector \(u_t(1),\ldots,u_t(m)\); for Theorem 4.1, an arbitrary monotone set function. The society is the distribution \(\mu\in\Delta(T)\), where \(\mu_t\) is the fraction of agents of type \(t\). A plausible regime has \(m\) and \(N\) growing together, with \(m/N\) bounded, while the number of standardized availability or job-role types remains fixed or grows slowly.
The type assumption is credible in this setting. An organization may have thousands of employees but only a modest number of recurring schedules, accessibility profiles, shift preferences, or role-specific valuations. This is much stronger than claiming that named individuals have interchangeable preferences: a type is the complete utility function used by the problem. Individual idiosyncrasies simply create additional types.
The continuous allocation variable is a mass allocation over whole interval bundles. Let \(\mathcal I_m\) be the empty interval and all intervals \([a,b]\subseteq[m]\). Let \(x_{t,I}\) be the fraction of type \(t\) receiving the indivisible bundle \(I\). Thus
\[ \sum_{I\in\mathcal I_m}x_{t,I}=\mu_t \]
and, after normalizing the population to mass one,
\[ \sum_{t,I:j\in I}x_{t,I}=1/N \]
for every item \(j\): each slot is assigned to one agent. At rational points \(\mu_t=N_t/N\), this is exactly the normalized count representation of \(N_t\) agents of type \(t\). Allowing real \(x\) is the high-multiplicity relaxation. The bundles themselves remain indivisible intervals; only the number of same-type agents assigned to each whole bundle becomes continuous.
For a mass allocation \(x\), define \(EF_c(x)\) to mean that whenever \(x_{t,I}>0\) and \(x_{t',J}>0\), there is a set \(S\subseteq J\), \(|S|\le c\), such that
\[ u_t(I)\ge u_t(J\setminus S). \]
Likewise \(PROP_c(x)\) means that for every supported pair \((t,I)\), there is \(S\subseteq[m]\setminus I\), \(|S|\le c\), with
\[ u_t(I)\ge u_t([m])/N-u_t(S). \]
This preserves the paper’s fairness notions rather than replacing them by average welfare.
Privacy also has to be retained. Let the privacy resolution be \(1/N\), corresponding to one agent. Two societies are agent-item adjacent if
\[ \mu'=\mu+\frac1N(e_{t'}-e_t), \]
where \(t\) and \(t'\) agree on every set of items not containing one item \(j\), exactly matching Definition 2.4. A randomized continuous allocation rule \(\mathcal M\) must satisfy
\[ \Pr[\mathcal M(\mu)\in B] \le e^\varepsilon\Pr[\mathcal M(\mu')\in B] \]
for every measurable set of outputs \(B\). The continuous problem is therefore to construct a private randomized mass-allocation rule that outputs an \(EF_c\) or \(PROP_c\) allocation with probability at least \(1-\beta\), while minimizing \(c\). In a compressed computational formulation, the input is the type library, \(\mu\), and rational utilities—not the \(N\) individual records—and the goal is a polynomial-time sampler or optimization procedure in the type-level representation.
My lead problem is:
*Private-Continuum Connected PROP*: given \(m,N,T,(u_t)_{t\in T},\mu,\varepsilon,\beta\), construct an agent-item-level \(\varepsilon\)-DP randomized rule over connected mass allocations whose output is \(PROP_c\) with probability at least \(1-\beta\), minimizing \(c\).
This mirrors Theorem 4.7, which states that for additive utilities there is an agent-item-level \(\varepsilon\)-DP algorithm producing a connected \(PROP_c\) allocation with
\[ c=O\!\left(\log n+\frac{\log(mn/\beta)}{\varepsilon}\right). \]
The theorem is proved by the authors here, with the detailed proof deferred to their full version. The match is unusually direct: additive utilities, ordered items, connected bundles, proportionality up to \(c\) items, and precisely the single-agent/single-item privacy notion are all retained.
I would expect this continuous problem to be a Class A candidate, at least for fixed or moderate \(\tau\). The paper’s moving-knife idea becomes a type-level procedure using prefix sums: instead of querying every named agent at every cut, it aggregates the contribution of each utility type. The sparse-vector mechanism then operates on a finite collection of type-level threshold functions. The resulting allocation can be represented by interval configurations and mass variables, suggesting configuration LPs, separation over interval endpoints, and rounding from the high-multiplicity solution.
I would not claim that Theorem 4.7 already proves a bound with \(N\) replaced by \(\tau\). That is exactly the interesting continuous question. The discrete theorem’s \(\log n\) dependence may reflect the number of agents, while the compressed problem may admit dependence on the number of types, the population density \(m/N\), or both. Establishing such a dependence would be a substantive continuization result rather than a restatement.
My secondary anchor is Theorem 4.1. The corresponding problem is:
*Private-Continuum Connected EF*: given the same type-distribution instance, now with arbitrary monotone type utilities, construct an agent-item-level \(\varepsilon\)-DP randomized rule over connected mass allocations whose output is \(EF_c\) with probability at least \(1-\beta\), minimizing \(c\).
Theorem 4.1, proved in the paper, gives
\[ c=O\!\left( 1+\frac{n\log(mn)+\log(1/\beta)}{\varepsilon} \right). \]
Its proof uses the modified utilities \(u^{-k}\), a low-sensitivity score, and the exponential mechanism over connected allocations. That structure is well suited to a type distribution. The input dependence on named agents can potentially be replaced by dependence on the finite type library, while the score itself is evaluated from type-level utilities and masses. The pricing problem is over intervals and bundle-removal choices rather than arbitrary individual assignments, making it a plausible configuration-LP or dynamic-programming problem.
This second mirror is not merely the first one with a different fairness label. It covers arbitrary monotone utilities rather than additive ones and tests whether the continuization can preserve envy comparisons between different cohorts, not just each type’s proportional share. I would again classify it as a conditional Class A candidate when \(\tau\) is moderate. If exact private mechanism synthesis turns out to be hard, the source of hardness would be the type-level allocation or privacy mechanism itself, not the mere number of named agents.
The authors should recognize both mirrors as their problem. The paper itself motivates applications involving facility time slots and office space, and connected allocations are specifically designed for spatial or temporal order. The only major change is replacing a long list of agents with the distribution of recurring utility profiles. The model does not turn the slots into divisible goods, lotteries over bundles, or a continuous outcome space. It continuizes the population and retains indivisible interval bundles, approximate envy-freeness or proportionality, and differential privacy.
The natural follow-up questions are whether the dependence on \(N\) can be replaced by dependence on \(\tau\), whether a continuous solution can be rounded with only additive loss in \(c\), whether the results extend to arbitrary rather than connected allocations, and whether approximate \((\varepsilon,\delta)\)-DP changes the type-level complexity. Theorem 4.8 and Theorem 4.10 could later supply boundary tests: do their connected-allocation lower bounds survive in the mass model, or does high multiplicity remove the packing obstruction?
My weakest point is that differential privacy is fundamentally phrased at the level of an individual record, whereas a literal nonatomic population has no individual of positive mass. The \(1/N\) privacy atom is therefore essential. If one insists on an \(N=\infty\) model with no finite privacy resolution, the paper’s privacy notion does not transfer cleanly. A second vulnerability is that the mass variables \(x_{t,I}\) can look like divisible allocation. The defense is that every configuration \(I\) remains a whole indivisible bundle and rational instances lift to ordinary finite allocations; nevertheless, a referee could reasonably demand a formal rounding or finite-lift theorem. Subject to those qualifications, this is a genuine population continuization of the paper’s problem, and Theorems 4.7 and 4.1 provide credible algorithmic anchors for a Class A programme.
The proponent has found a plausible high-multiplicity *finite* application, but not a continuous mirror of either theorem. The obstruction is that this paper’s essential objects are individual privacy records and indivisible item assignments; both disappear under a genuinely nonatomic population.
In the proposed mass allocation, each item has population-mass capacity \(1/N\). If \(N\) remains finite, the variables \(x_{t,I}\) must lie on the \(1/N\)-lattice to represent an actual allocation. That is merely a compressed representation of a finite allocation. If arbitrary real \(x_{t,I}\) are allowed, a positive fraction of an infinitesimal population is effectively receiving the same indivisible item, or \(x\) is being interpreted as a lottery over discrete allocations. The former violates indivisibility; the latter continuizes the outcome space, which is outside ChoCo’s scope. In a true \(N\to\infty\) limit with finitely many items, every item is assigned to a measure-zero set and almost the entire population receives nothing.
Theorem 4.7 has an additional degeneracy. PROP is defined using each agent’s entitlement \(u_i(M)/n\). A \(\mu\)-only society contains no \(n\), while retaining \(N\) leaves us with the finite problem above. Sending \(N\) to infinity makes the entitlement vanish. Indeed, for additive utilities, once \(N\ge m\), every empty bundle is PROP1: the most valuable item is worth at least \(u_i(M)/m\ge u_i(M)/N\). A fixed, data-independent allocation therefore already gives a privacy-preserving constant guarantee. This is not merely the observation that “continuity helps”; the individual proportionality requirement has ceased to express a meaningful fairness constraint. Renormalizing proportionality by type mass or by cohort size would be a new fairness notion, not a mirror of Theorem 4.7.
Theorem 4.1 avoids that particular denominator, but not the more fundamental problem. EF is required for every individual, including a type represented by a single agent. In the continuum, such an agent has measure zero. If it is ignored, the resulting almost-everywhere EF notion is weaker than the theorem’s notion. If it is retained through the support of \(\mu\), feasibility becomes discontinuous: adding an arbitrarily small mass of a new type can impose all of that type’s envy constraints. Thus there is no stable population-measure object corresponding to “every agent is envy-free.” The finite-\(N\) version remains well-defined, but then \(N\) and the indivisible allocation atoms have not disappeared.
Privacy makes the type compression still less faithful. Agent-item adjacency changes one coordinate of one individual’s utility function. For binary additive utilities, preserving the paper’s full input domain requires the type space to contain the entire \(m\)-dimensional Boolean hypercube: repeated one-item changes connect \(2^m\) utility types. For arbitrary additive values, the closure is uncountable. A fixed or moderate type library can avoid this explosion only by restricting adjacency to a special domain, silently weakening the paper’s privacy guarantee. Replacing individual adjacency by a positive-mass or type-level change would protect a cohort rather than an individual and would be a different DP problem.
Nor do the proofs transfer simply at the computational level. Theorem 4.7’s moving-knife procedure counts named agents because proportionality is per agent. Theorem 4.1’s exponential mechanism ranges over finite allocations, each assigning one interval to each named agent. A real-valued distribution over type–interval pairs is neither that candidate set nor an actual connected allocation unless one reinstates integrality or interprets the output as a lottery. The suggested configuration-LP formulation therefore changes the allocation problem before it changes the population model.
The honest concession is that repeated utility profiles in an ordered facility-slot application are a sensible high-multiplicity regime. What fails is the claim that this yields a worthwhile *continuous-population* mirror of these theorems. Keeping \(N\) gives a compressed finite fair-division problem; removing \(N\) destroys individual privacy, individual fairness, or item indivisibility; repairing any one of those by changing the fairness, privacy, or resource semantics produces a new problem rather than a continuization of Theorems 4.7 or 4.1.
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.