EFX Feasible Scheduling for Time-dependent Resources

The strongest positive case is a large-market version of the paper’s binary, unit-job result. The continuous object is the population of machines or workers, not the jobs themselves.

Consider a large student-employment platform or cloud-scheduling system. There are \(N\) machines, but only a small number of machine types. A type \(t\) records everything relevant to the problem: the machine’s valuation \(v_t(k)\in\{0,1\}\) for each job type \(k\), together with any availability parameters. There are also repeated job templates \(k\), each with a release window \([r_k,d_k]\), unit processing time, and normalized supply \(\lambda_k\). The population is represented by masses \(\mu_t\), where \(\sum_t\mu_t=1\). Thus \(N\mu_t\) machines have type \(t\), while \(N\lambda_k\) copies of job template \(k\) exist. The intended regime is \(N\) very large relative to the number of distinct machine and job types.

This is a credible high-multiplicity interpretation of the paper’s setting: large cohorts of interchangeable students, workers, or machines repeatedly receiving the same kinds of shifts or tasks. The type is complete in the programme’s sense: two machines of type \(t\) have the same valuations, calendars, and scheduling constraints.

The continuous allocation should not fractionalize an individual job. Let \(\mathcal S\) be the set of feasible integral schedules for one machine. A schedule \(\sigma\in\mathcal S\) specifies which job copies are assigned to which time slots. Let \(a_{\sigma k}\) be the number of jobs of type \(k\) used by \(\sigma\). The decision variable is

\[ x_{t,\sigma}\ge 0, \]

the mass of machines of type \(t\) receiving schedule \(\sigma\). It must satisfy

\[ \sum_{\sigma\in\mathcal S}x_{t,\sigma}=\mu_t \]

for every \(t\), and

\[ \sum_{t,\sigma}a_{\sigma k}x_{t,\sigma}\le \lambda_k \]

for every job type \(k\). Thus \(x\) is a distribution of actual integral schedules across a nonatomic population, not a lottery over outcomes for one agent.

The utility of type \(t\) receiving \(\sigma\) is

\[ u_t(\sigma)=\sum_k v_t(k)a_{\sigma k}. \]

The unassigned jobs form a charity pool with residual supply

\[ \lambda_k^0=\lambda_k-\sum_{t,\sigma}a_{\sigma k}x_{t,\sigma}. \]

For an agent type \(t\), \(u_t(X_0)\) means the maximum utility obtainable by scheduling a feasible subset of that residual pool on one machine, exactly as in the paper.

My lead continuous problem is:

HM-Binary-Unit-EFX-MaxNSW-PO. Given rational masses \(\mu_t\), rational job supplies \(\lambda_k\), binary valuations, and unit-job windows, find a continuum schedule \(x\) that is simultaneously:

\[ \max \ \exp\!\left(\sum_{t,\sigma}x_{t,\sigma}\log u_t(\sigma)\right), \]

EFX, meaning that for every pair of schedules \(\sigma,\rho\) used by positive mass and every job occurrence \(e\) in \(\rho\),

\[ u_t(\sigma)\ge u_t(\rho\setminus\{e\}), \]

and Pareto optimal, meaning that no measure-preserving reassignment of the same machine population can weakly improve every machine’s utility and strictly improve a positive-mass set.

The named anchor is Theorem 5, proved in this paper: for arbitrary FISP with \(\langle\mathrm{Binary},\mathrm{Unit}\rangle\), a non-wasteful MaxNSW schedule that is both EFX and PO can be found in polynomial time. The structural companion is Theorem 4, also proved here, which establishes the EFX and PO guarantee for MaxNSW schedules. I regard this pair as one anchor because Theorem 4 states the property and Theorem 5 supplies the algorithm.

I would expect the continuous problem to be Class A. In the unit-job case, a machine schedule is a matching between job occurrences and eligible time slots. At the aggregate level, the feasibility constraints become a transportation or configuration LP. The pricing problem for a configuration is a matching problem rather than the paper’s difficult nonpreemptive interval-selection problem. The Nash objective becomes the concave objective

\[ \sum_{t,\sigma}x_{t,\sigma}\log u_t(\sigma), \]

and the paper’s exchange argument for eliminating EFX envy has an especially natural mass-transfer interpretation. The large-market formulation should therefore expose precisely the flow, matching, and convex-optimization structure that is obscured by individual machine names.

The bridge to the discrete problem is also clean. If all masses have denominator \(N\), then \(Nx_{t,\sigma}\) is an integer schedule histogram for \(N\) machines and \(N\lambda_k\) job copies. Conversely, any sufficiently homogeneous finite instance maps to such an \(x\). This would give the programme’s desired two-way dictionary, together with questions about rounding a continuum solution back to finite EFX and PO schedules.

The mirror deliberately covers only the paper’s binary-unit specialization. It does not claim to continuize arbitrary valuations, flexible processing times, or the WIO result. The paper’s Theorem 11, which proves that computing a WIO schedule is NP-hard, is a warning that continuity will not automatically make every scheduling subproblem tractable: its hardness comes from finding a high-value feasible subset of time-dependent jobs, not from distinguishing machine identities. I would not claim that hardness transfer without separately proving a replication lemma for the chosen job-supply convention.

The weakest point is exact EFX. A naive continuous LP using only average utilities would be invalid: EFX is a condition on every individual schedule in the support. The proposed model avoids that mistake by retaining integral schedules and making \(x\) a measure over them, but it leaves an important technical question: can the support-wise EFX constraints be separated efficiently while preserving exact MaxNSW and PO? If the answer is yes, this is a strong Class A mirror of Theorems 4–5. If not, the mirror may remain conceptually faithful but lose the computational advantage that makes continuization worthwhile.