| paper | d4-conf-ijcai-2007-0307 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given a finite set of worker types \(T\) with rational population masses \(\mu_t\), a finite-state network of legal integral rosters \(a\) for each type, each roster's utility \(u_t(a)\) and resource use \(r_t(a)\), and per-capita resource constraints, compute a feasible allocation \(x_{t,a}\ge 0\) with \(\sum_a x_{t,a}=\mu_t\) that lexicographically minimizes \((p_{q_1},\ldots,p_{q_k})\), where \(q_1<\cdots<q_k\) are the attainable utility levels and \(p_q=\sum_{t,a:u_t(a)=q}x_{t,a}\); report infeasibility if no such allocation exists.
A continuous population has types \(t\in T\) with masses \(\mu_t\). Each person receives a complete integral roster, while \(x_{t,a}\) records the population mass of type \(t\) assigned roster \(a\). Type masses must be preserved and aggregate resource use must meet the per-capita constraints. The objective is to lexicographically minimize the mass at each utility level in increasing order, the distributional counterpart of maximizing the sorted individual utility vector.
The mirror carries Proposition 1's leximin objective and successive utility-level optimization into a roster-allocation family. It does not extend the result to every arbitrary constraint network or mirror the paper's experimental comparison of algorithms.
I would anchor on Proposition 1, proved in this paper. It says that if the generic procedures solve and maximize are correct and halt, Algorithm 1 halts and returns a leximin-optimal solution to MaxLeximinCSP, or reports inconsistency if there is no feasible solution. Algorithm 1 does this by successively maximizing the \(i\)th ordered utility level: at step \(i\), it requires at least \(n-i+1\) agents to have utility at least \(Y_i\), then fixes the best value found before moving to the next level. This is a correctness result, not a polynomial-time guarantee: the procedures it calls may themselves be expensive. The paper gives no numbered hardness result to anchor on; its statement that CSP is NP-complete is background.
A plausible high-multiplicity regime is a large emergency-service workforce with many workers sharing a modest number of complete qualification, contract, availability, and utility profiles. Each worker receives an integral weekly roster, while shift coverage and other supplies scale with workforce size. The “type” must include every feature used by feasibility and utility, so workers in one type really are interchangeable. Here \(n\) may be in the thousands while \(\tau\), the number of distinct profiles, is much smaller. This is close to the paper’s own rostering motivation and retains its central question: choose feasible individual assignments to maximize fairness across agents.
I would call the mirror Type-Leximin Roster\(_\infty\). Its input is a finite set of types \(T\), rational masses \(\mu_t\) summing to \(1\), and for each type a finite-state network whose source-to-sink paths encode that type’s legal integral rosters. Each roster \(a\) has a common-scale integer utility \(u_t(a)\) and a vector \(r_t(a)\) of consumed shift resources. The instance also gives per-capita resource limits; coverage requirements can be written as linear aggregate constraints.
The decision variable \(x_{t,a}\ge 0\) is the fraction of the whole population of type \(t\) assigned roster \(a\). Require \(\sum_a x_{t,a}=\mu_t\) for every type, and require the aggregate resource use \(\sum_{t,a}x_{t,a}r_t(a)\) to satisfy the stated per-capita constraints. Each person still receives a complete roster; only the mass of a type is split among rosters.
Let \(Q\) be the finite set of utility values attainable by these rosters, ordered increasingly. For each \(q\in Q\), set \(p_q=\sum_{t,a:u_t(a)=q}x_{t,a}\). The task is to return a feasible \(x\) whose vector \((p_q)_{q\in Q}\) is lexicographically minimal. This is the mass-distribution form of leximin: first reduce the mass at the lowest utility level; if tied, reduce the mass at the next level, and so on. For a discrete workforce, setting \(x_{t,a}\) to the number of workers assigned \(a\), divided by \(n\), gives exactly the original leximin comparison. Arbitrary continuous solutions relax the requirement that these masses lie on a \(1/n\) grid.
I expect this roster version to be Class A when the schedule networks have tractable pricing. The model is a lexicographic sequence of linear programs over roster columns. Although there may be exponentially many paths, for bounded or explicitly listed utility levels and additive roster features, a dynamic program on the finite-state network can price paths of each utility level; separation-based LP methods can then optimize each \(p_q\) in turn. The meaningful algorithmic question is whether this works in polynomial time in the network description, \(\tau\), the number of resource constraints, \(|Q|\), and the input bit length. This is a concrete extension of Proposition 1’s objective and ordered-level computation, rather than a claim that Proposition 1 itself establishes tractability.
The paper’s authors should recognize this as their problem: it preserves the leximin criterion, individual integral assignments, and combinatorial feasibility, while aggregating identical agents and scaling shared supplies with the population. The mirror covers Proposition 1’s MaxLeximinCSP result on this resource-allocation and roster family; it does not claim to continuize every arbitrary constraint network in the paper.
The further questions are whether natural roster constraints admit the needed pricing algorithm, how closely the continuous optimum can be rounded to a finite workforce without losing coverage or much fairness, and whether hard pricing or a large integrality gap gives a boundary to the tractable regime. The soft spot is substantial: the paper’s generic CP formulation allows hard maximize calls, and its experiments involve only 4 to 20 agents. So this is a credible Class A research question motivated by the paper, not a result the paper has already supplied.
The proponent’s anchor is weaker than the roster example makes it sound. Proposition 1 is a conditional correctness statement: if solve and maximize are correct and halt, Algorithm 1 returns a leximin solution. It gives no running-time bound or structural result about when those procedures are efficient. Its proof works for any finite constraint network, regardless of whether the objective variables describe a population. So the proposed mass formulation does not continue a computational guarantee from Proposition 1; it poses a new optimization problem with a different feasible set.
There is a real modeling fork here. To represent the paper’s generic constraint networks faithfully, the mirror must preserve arbitrary links among particular variables. Those links may distinguish agents or prevent feasibility from being described by type-level roster choices plus aggregate resource constraints. Encoding them can make the type support grow with the workforce, removing the high-multiplicity regime. If instead the mirror uses interchangeable roster types and aggregate staffing constraints, it has narrowed the paper to a useful but specific allocation family. Its pricing problem then comes from that family’s schedule structure, not from a result established by Proposition 1.
That is the strongest objection I can make to the anchor, but it does not defeat the better mirror. The paper itself motivates worker rostering and resource allocation, and a large workforce with repeated qualification, contract, availability, and utility profiles is plausible. With integral rosters for each worker and per-capita supplies, minimizing the mass at each attainable utility level in ascending order is a natural continuum extension of leximin. It preserves fairness across individuals while representing how much of each type receives each utility. Whether its roster columns admit efficient pricing is a genuine computational question.
So the case against is weak at its crucial step. Proposition 1 should not be presented as a complexity result, and the generic network formulation may resist compression. But the paper’s allocation and rostering settings supply a credible high-multiplicity regime, and the natural mirror survives those objections. I cannot honestly support the universal claim 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.