| paper | Optimal Seat Arrangement: What Are the Hard and Easy Cases? |
| authors | Esra Ceylan, Jiehua Chen, Sanjukta Roy |
| venue | IJCAI 2023 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 10
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_a\) with \(\sum_a\mu_a=1\), rational compatibilities \(w_{ab}\), and \(\rho\in[0,1]\), decide whether there exist \(x_{ab}\ge0\) for two-seat offices and \(z_a\ge0\) for isolated desks satisfying \(\sum_{a\le b}x_{ab}=\rho/2\), \(\sum_a z_a=1-\rho\), and \(2x_{aa}+\sum_{b\ne a}x_{\min(a,b),\max(a,b)}+z_a=\mu_a\), such that every type occupying positive paired mass weakly prefers its assigned partner to every occupied partner type and every type with \(z_a>0\) weakly prefers isolation to every occupied partner type.
An atomless population of role types \(T\) with masses \(\mu\), common compatibility values \(w_{ab}\), a fraction \(\rho\) of two-seat offices, and mass variables \(x_{ab}\) and \(z_a\); the computational task is envy-free feasibility.
The pointwise envy requirement has no uniquely canonical atomless limit when vanishing-mass exceptional types can impose constraints on the whole arrangement.
fatal: False
The mirror covers EFA on matching seat graphs with isolated desks and type-homogeneous compatibilities; it leaves MWA, MUA, ESA, other seat-graph classes, and the paper’s exact parameterized bounds untouched.
The strongest positive case is a high-multiplicity mirror of envy-free arrangement on repeated two-seat offices. My lead anchor is Theorem 10, proved by Ceylan, Chen, and Roy in this paper (with the proof deferred to their technical report): for every considered seat-graph class, EFA is W[1]-hard with respect to \(k\), even for binary or strict preferences. I use its binary-preference clause for matching-graphs.
Consider a large organization with many identical two-person offices and some single desks. Employees belong to finitely many role types \(T\), where type \(a\) has mass \(\mu_a\), and every type-\(a\) employee assigns the same cardinal value \(w_{ab}\) to sharing an office with a type-\(b\) employee. This is a genuine high-multiplicity regime: the number of employees and desk components can be enormous, while \(\tau=|T|\) remains moderate. The type includes the complete compatibility vector \(w_{a,\cdot}\), so no information relevant to EFA is discarded.
Call the resulting problem Continuous Matching-Seat EFA. An instance consists of rational masses \(\mu_a\), rational compatibility values \(w_{ab}\), and a rational \(\rho\in[0,1]\), the fraction of seats lying in two-seat offices. A solution chooses \(x_{ab}\ge 0\), the mass of two-seat offices containing types \(a\) and \(b\), and \(z_a\ge0\), the mass of type \(a\) assigned to isolated desks. Thus \(\sum_{a\le b}x_{ab}=\rho/2\), \(\sum_a z_a=1-\rho\), and \(2x_{aa}+\sum_{b\ne a}x_{\min(a,b),\max(a,b)}+z_a=\mu_a\) for every \(a\).
Let \(A(x)\) be the types occupying positive mass in two-seat offices. A pair \(ab\) with \(x_{ab}>0\) is envy-free precisely when type \(a\) weakly prefers \(b\) to the partner type of every occupied office, and likewise for type \(b\): \(w_{ab}\ge w_{ac}\) and \(w_{ba}\ge w_{bc}\) for every \(c\in A(x)\), with the additional requirement \(w_{ab},w_{ba}\ge0\) if isolated desks exist. Any type with \(z_a>0\) must satisfy \(w_{ac}\le0\) for every \(c\in A(x)\), since an isolated employee must not envy an occupied office. The question is whether such \(x\) and \(z\) exist.
This is exactly the paper’s EFA condition in the atomless limit. An employee’s utility is still determined by the agents adjacent to their seat; swapping with another employee still means moving into that employee’s seat. The only change is that repeated role classes are represented by masses, and pair assignments by a fractional matching. Finite instances with \(M\mu_a\) employees of type \(a\) and \(M\)-scaled seat capacities converge directly to this formulation.
I expect the unrestricted continuous problem to be Class B: hardness should transfer. The continuous variables are fractional, but the decisive object is the support \(A(x)\): assigning even a tiny positive mass of a type to a paired seat changes the envy constraints for every type. Thus the choice of which role blocks are active remains discrete. The clique-style combinatorics in Theorem 10 can plausibly live in the type-compatibility structure rather than in the number of named employees.
There is also a useful tractable boundary. If \(\rho=1\), every type is active, so the allowed pairs are simply the mutually top-ranked type pairs. Feasibility becomes a fractional perfect matching problem with vertex masses \(\mu_a\), hence a polynomial linear program. The hard part is therefore the support selection created by isolated seats, not continuity itself. Further questions are whether the W[1]-hardness reduction survives complete type compression, and which restrictions on \(\rho\), \(\tau\), or the number of active types yield an FPT or LP formulation.
The weakest point is that Theorem 10’s parameter \(k\) counts individual non-isolated seats, whereas the mirror replaces it by the active seat fraction \(\rho\); moreover, gadgets relying on individually named agents may collapse when those agents are grouped into types. I am therefore not claiming that the theorem’s exact W[1] lower bound transfers unchanged. The positive case is narrower: the paper’s EFA question has a natural, realistic high-multiplicity form, and its main combinatorial difficulty can survive as a support-selection problem over role types.
The strongest negative case attacks the proponent’s claimed inheritance from Theorem 10, but it does not support the universal conclusion.
The theorem’s parameter \(k\) counts individually non-isolated seats. If a matching graph is blown up by a factor \(M\), then \(k=\rho M\); it does not become the continuous parameter \(\rho\). Thus the theorem’s W[1]-hardness statement has no direct high-multiplicity interpretation. Moreover, its binary preference graph can distinguish every named agent. Grouping agents into role types replaces that arbitrary graph by a \(\tau\times\tau\) compatibility matrix and removes precisely the individual gadget identities used by the reduction.
For the proposed matching-office model, once the active type set \(A\) is fixed, envy-freeness is essentially a finite collection of fractional matching feasibility problems. A type \(a\) paired with \(b\) must have \(w_{ab}\) at least as large as its value for every occupied partner type; an isolated \(a\)-agent must have \(w_{ac}\le 0\) for every occupied partner type \(c\). In the no-isolated-seat case, \(A\) is fixed and the problem is simply a fractional perfect matching over mutually top-ranked type pairs. The only remaining difficulty is selecting \(A\), a type-level support problem rather than a population-level analogue of Theorem 10.
One can try to repair this by assigning every gadget agent its own type and duplicating each type \(M\) times. But then \(\tau\) grows with the original instance and the “continuum” is merely a weighted blow-up of the original preference graph; the added multiplicity contributes no modelling or algorithmic content. If instead one insists on a genuinely compressed role space, fractional pairings can mix copies in ways unavailable to the original matching instance, so the reduction is no longer preserved.
There is also a genuine limiting pathology. Envy-freeness is pointwise: a single exceptional agent can create a constraint affecting every other agent, although that agent has vanishing mass as \(M\to\infty\). A continuous model must therefore choose between an almost-everywhere notion of envy and the exact finite notion; neither is a completely canonical limit of the paper’s problem.
These objections show that Theorem 10 itself is a poor foundation for the claimed mirror. They do not, however, defeat the better role-type model. Repeated two-person offices, repeated isolated desks, and employees with common role-based compatibilities are a sensible high-multiplicity regime, and the proposed \(x_{ab}\) formulation is a legitimate continuous EFA question. Its support-selection problem may well be worthwhile even though the theorem’s parameterized hardness does not transfer.
So the honest negative verdict is weak: the paper does not justify the proponent’s specific complexity analogy, but it cannot establish that no worthwhile continuous mirror exists.
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.