arxiv: 2604.25301 · v1 · submitted 2026-04-28 · 💻 cs.GT

Recognition: unknown

Job-Scheduling Games with Time-Dependent Processing Times

Ido Borenstein , Tami Tamir

Authors on Pith no claims yet

Pith reviewed 2026-05-07 14:22 UTC · model grok-4.3

classification 💻 cs.GT

keywords job scheduling gamestime-dependent processing timesdelay-averse agentsNash equilibriumprice of anarchycoordination mechanismsNP-completeness

0 comments

The pith

Delay-averse agents make pure Nash equilibria exist and easy to compute in job-scheduling games where processing times grow or shrink with start time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies job-scheduling games in which each job's length is a linear function of its start time, either increasing or decreasing as the schedule progresses. It introduces delay-averse agents, who always prefer an earlier start to avoid longer processing, as a way to separate cases where the game behaves like classical scheduling from cases where it does not. When every agent is delay-averse the games remain stable and pure Nash equilibria can be found efficiently. When agents are not delay-averse, pure equilibria may fail to exist and deciding whether one exists is NP-complete even when all machines are identical. The work also shows that selfish behavior can produce much higher total completion time than in fixed-length settings and offers three priority rules that restore constant-factor bounds on the resulting inefficiency.

Core claim

The central claim is that delay-averse agents supply a unifying framework for equilibrium existence in time-dependent scheduling games. For delay-averse jobs, stability is maintained and pure Nash equilibria can be computed efficiently. For non-delay-averse jobs, a pure Nash equilibrium may not exist and deciding its existence is NP-complete even on identical machines. The Price of Anarchy is larger than in fixed-processing-time games, but the SBPT rule reduces it to a constant under positive deterioration while SDR and LBDR achieve tight constants of 2 and max{e/(e-1), 2-1/m} under negative deterioration.

What carries the argument

The classification of jobs as delay-averse or non-delay-averse, which separates the cases in which pure Nash equilibria always exist and are efficiently computable from the cases in which existence is not guaranteed and is NP-complete to decide.

If this is right

Pure Nash equilibria exist and can be computed efficiently whenever all jobs are delay-averse.
Existence of a pure Nash equilibrium is not guaranteed for non-delay-averse jobs, and deciding existence is NP-complete even on identical machines.
The Price of Anarchy is strictly larger than the bound known for fixed processing times.
The SBPT coordination rule bounds the Price of Anarchy by a constant under positive deterioration.
The SDR and LBDR rules bound the Price of Anarchy by 2 and by max{e/(e-1), 2-1/m} respectively under negative deterioration.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same delay-averse distinction may separate tractable from intractable equilibrium problems in other decentralized systems whose costs rise with waiting time.
Instances containing a mixture of delay-averse and non-delay-averse jobs can be handled by first checking whether the non-delay-averse subset already prevents equilibrium.
The NP-completeness result indicates that real systems containing non-delay-averse tasks will require heuristic or approximate equilibrium finding rather than exact computation.
The constant PoA bounds achieved by the three priority rules suggest that similar ordering policies could control inefficiency in related time-dependent resource games such as packet scheduling or cloud-task allocation.

Load-bearing premise

Every job's processing time changes exactly linearly with its start time and each agent is either fully delay-averse or not at all.

What would settle it

A polynomial-time algorithm that decides existence of a pure Nash equilibrium for arbitrary non-delay-averse jobs on identical machines would falsify the NP-completeness claim.

Figures

Figures reproduced from arXiv: 2604.25301 by Ido Borenstein, Tami Tamir.

**Figure 1.** Figure 1: The possible profiles of the GnoNE3. No profile is a NE. Thus, the game GnoNE3 has no pure Nash equilibrium. 3.1 Nash Equilibrium Existence - Computational Complexity In this section we study the computational complexity of the following problem: Given a game instance, does it have a Nash Equilibrium profile?. Clearly, this problem is only relevant for games in classes in which a NE is not guaranteed to ex… view at source ↗

**Figure 2.** Figure 2: (i) Let T = {(x1, y1, z1),(x2, y2, z2),(x1, y2, z2)}. A matching of size 2 exists, and job u is assigned on M3, resulting in a NE. (b) Let T = {(x1, y1, z1),(x2, y2, z1),(x1, y2, z2)}. A matching of size 2 does not exist, job u is assigned on one of the first two machines, and GnoNE3 is induced. 16 view at source ↗

**Figure 3.** Figure 3: A game corresponding to n = 7, with w = 24 = 16. The global priority list is π = (y0, y1, x0, x1, x2, x3, y2). σ ∗ is an optimal schedule with makespan 3w −3 = 45; σ is a NE schedule with makespan 2w √ w + w − 3 = 141. Next, we generalize Theorem 4.3, to show that for any number of machines, m, number of jobs, n, and fixed deterioration rate a, there is game G for which P oA(G) = Ω((1 + a) n m ). Theorem 4… view at source ↗

**Figure 4.** Figure 4: A game on 3 identical machines, with P oA 3 − 1/3 − ϵ. (i) an optimal schedule with makespan 1, (ii) a NE schedule with makespan 3 − 1/3 − ϵ. Observation 4.11 Let G ∈ G−DA P Global be a game with π = (1, 2, . . . , n) and processing time functions (p1(t), . . . , pn(t)). Assume that in a run of LS (Algorithm 3), the starting time of job u is tu. Consider a game G′ with the same priority list and processing… view at source ↗

**Figure 5.** Figure 5: A game with a global priority list π = (u1, u2, u3, v1, v2, v3, u4, u5, u6, a) and 3 machines. (i) an optimal schedule with makespan 1 + O(ϵ), (ii) a NE schedule with makespan (3 − 2 m − O(ϵ)). 28 view at source ↗

**Figure 6.** Figure 6: (i) An optimal profile with makespan ≈ 1111.(ii) A NE profile with makespan ≈ 1101.1 + 1110. 5.1.2 LBDR Scheduling Policy In this section we suggest and analyze another efficient policy for games G −DA P Global. The policy largest basic-deterioration ratio (LBDR), prioritize the jobs in non-increasing order of bi ai . We assume w.l.o.g. that for all i, ai > 0. If a job has ai = 0, then we set ai = ϵ for a … view at source ↗

**Figure 7.** Figure 7: (i) An optimal profile with makespan 3.(ii) A NE profile with makespan 5. 39 view at source ↗

read the original abstract

Job-scheduling games have traditionally assumed fixed processing times. However, in many realistic environments, ranging from cyber-security response to high-frequency trading, a task's duration depends on its starting time. We study job-scheduling games with time-dependent processing times, where job lengths are linear functions of their start times, exhibiting either positive deterioration (increasing length) or negative deterioration (decreasing length). We analyze these games under various coordination mechanisms and priority policies. By introducing the concept of delay-averse agents, we provide a unifying framework to characterize equilibrium existence. For delay-averse jobs, we show that stability is maintained and pure Nash equilibria (NE) can be computed efficiently. In contrast, for non-delay-averse jobs, we demonstrate that a NE may not exist, and prove that deciding its existence is NP-complete, even on identical machines - a fundamental departure from classical coordination mechanisms. Regarding equilibrium inefficiency, we show that the Price of Anarchy (PoA) can be significantly higher than in environments with fixed processing times. To mitigate this, we propose and analyze three coordination mechanisms: SBPT (Shortest Basic Processing Time), which reduces the PoA in games with positive deterioration to a constant, and SDR (Smallest Deterioration Rate) and LBDR (Largest Basic-Deterioration Ratio) for negative deterioration, which achieve tight constant PoA bounds of $2$ and $\max\{\frac{e}{e-1}, 2-\frac{1}{m}\}$, respectively. Our results bridge the gap between centralized time-dependent scheduling and decentralized game-theoretic analysis.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Delay-aversion splits equilibria existence cleanly in linear time-dependent scheduling games and yields three explicit constant-PoA policies, though the model is narrow.

read the letter

The main thing to know is that splitting agents into delay-averse and non-delay-averse produces a sharp separation: pure Nash equilibria always exist and can be found in polynomial time for the first group, while existence is NP-complete even on identical machines for the second. The paper also supplies three priority rules that restore constant price of anarchy despite the start-time dependence. SBPT works for positive deterioration; SDR and LBDR handle negative deterioration with bounds of 2 and max(e/(e-1), 2-1/m). These are concrete enough to be useful for system design. The work is new in its use of the delay-averse notion to unify the existence results and in the explicit mechanisms that go beyond the fixed-time literature. The linear deterioration model (both positive and negative) is handled consistently, and the departure from classical results on identical machines is stated clearly. The soft spots are limited but real. Everything rests on exactly linear processing-time growth or decay and on the binary agent classification; nonlinear deterioration or mixed preferences would likely collapse the dichotomy and the complexity claims. The NP-completeness reduction on identical machines is the strongest statement and needs careful checking for edge cases in the deterioration rates. The PoA bounds are given explicitly, which is good, but their tightness depends on the worst-case instances constructed in the proofs. This paper is aimed at researchers in algorithmic game theory and mechanism design who already work on scheduling. A reader looking for coordination mechanisms in time-sensitive decentralized settings would get direct value from the policies and bounds. It deserves a serious referee. The core separation and the new rules are stated precisely enough that review can focus on verifying the reduction and the PoA derivations rather than rethinking the direction. I would send it out for peer review.

Referee Report

0 major / 3 minor

Summary. The paper studies job-scheduling games in which processing times are linear functions of start times (positive or negative deterioration). It introduces the notion of delay-averse agents to give a unifying characterization of equilibrium existence: delay-averse jobs admit pure Nash equilibria that can be computed efficiently, while for non-delay-averse jobs existence is not guaranteed and deciding existence is NP-complete even on identical machines. The Price of Anarchy is shown to exceed the fixed-processing-time case; three coordination mechanisms (SBPT for positive deterioration, SDR and LBDR for negative deterioration) are proposed and proved to restore constant PoA bounds of 2 and max{e/(e-1), 2-1/m} respectively.

Significance. If the central claims hold, the work supplies a clean, model-based dichotomy that explains when stability is tractable in time-dependent scheduling games and supplies the first constant-PoA coordination mechanisms for this setting. The NP-completeness result on identical machines is a substantive departure from classical scheduling-game results and the tight PoA bounds are of both theoretical and practical interest for dynamic environments such as high-frequency trading and cyber-security response.

minor comments (3)

[§2] The definition of delay-averse agents (introduced in the abstract and presumably formalized in §2) should be accompanied by a short discussion of how the binary classification relates to mixed or partial delay aversion that may arise in practice.
[Theorem 3 / §4] The NP-completeness reduction for non-delay-averse jobs (even on identical machines) is a load-bearing claim; a high-level sketch of the reduction in the main text (with full details in the appendix) would improve readability.
[§5] The PoA analysis for the proposed mechanisms (SBPT, SDR, LBDR) cites specific constants; a brief table comparing these bounds to the classical fixed-time PoA would help readers gauge the improvement.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our work, as well as the recommendation for minor revision. The referee's assessment correctly identifies the key contributions, including the delay-averse dichotomy for equilibrium existence, the NP-completeness result on identical machines, and the constant-PoA coordination mechanisms. Since the report contains no specific major comments or requested changes, we have no revisions to propose at this stage.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines a new scheduling model with linear time-dependent processing times and introduces the delay-averse agent concept as an internal modeling choice. Equilibrium existence, efficient computation for delay-averse cases, and NP-completeness for non-delay-averse cases are established via direct proofs from these definitions and standard game-theoretic notions (Nash equilibria, Price of Anarchy). No load-bearing step reduces to a fitted parameter, self-citation chain, or tautological renaming; the results are self-contained against the stated model assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claims rest on the assumption that processing times are exactly linear in start time and on the binary classification of agents as delay-averse or not; these are domain assumptions rather than derived quantities.

axioms (2)

domain assumption Agents are rational and seek to minimize their individual completion times or costs.
Standard assumption in algorithmic game theory for scheduling games.
domain assumption Job processing times are linear functions of start times (positive or negative deterioration).
Core modeling choice that defines the time-dependent setting.

invented entities (1)

delay-averse agents no independent evidence
purpose: Unifying concept to guarantee existence and efficient computation of pure Nash equilibria across both positive and negative deterioration cases.
New classification introduced by the authors; no independent evidence outside the paper is provided.

pith-pipeline@v0.9.0 · 5584 in / 1627 out tokens · 65137 ms · 2026-05-07T14:22:22.638240+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

28 extracted references · 1 canonical work pages

[1]

Alidaee and N

B. Alidaee and N. K. Womer. Scheduling with time dependent processing times: Review and extensions.The Journal of the Operational Research Society, 50:711–720, 1999

1999
[2]

Anshelevich, A

E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation.SIAM Journal on Computing, 38(4):1602–1623, 2008

2008
[3]

Aspnes, Y

J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts. On-line load balancing with applications to machine scheduling and virtual circuit routing.Proceedings of the Twenty- Fifth Annual ACM Symposium on Theory of Computing,, (STOC), 1993

1993
[4]

Awerbuch, Y

B. Awerbuch, Y. Azar, Y. Richter, and D. Tsur. Tradeoffs in worst-case equilibria.Theo- retical Computer Science, 361(2):200–209, 2006

2006
[5]

Y. Azar, L. Fleischer, K. Jain, V. Mirrokni, and Z. Svitkina. Optimal coordination mech- anisms for unrelated machine scheduling.Operations Research, 63(3):489–500, 2015

2015
[6]

Bachman and A

A. Bachman and A. Janiak. Scheduling jobs with decreasing processing times for the total completion time minimization.Operations Research Proceedings, 2000:353–358, 2000

2000
[7]

Browne and U

S. Browne and U. Yechiali. Scheduling detrirorating jobs on a single processor.Opns Res, 38:495–498, 1990

1990
[8]

Q. Chen, L. Lin, Z. Tan, and Y. Yan. Coordination mechanisms for scheduling games with proportional deterioration.European Journal of Operational Research, 263(2):380–389, 2017

2017
[9]

Christodoulou, E

G. Christodoulou, E. Koutsoupias, and A. Nanavati. Coordination mechanisms.Theor. Comput. Sci., 410(36):3327–3336, 2009

2009
[10]

Czumaj and B

A. Czumaj and B. Vöcking. Tight bounds for worst-case equilibria.ACM Trans. Algo- rithms, 3(1):4:1–4:17, 2007

2007
[11]

Feldman, Y

M. Feldman, Y. Snappir, and T. Tamir. The efficiency of best-response dynamics. InThe 10th International Symposium on Algorithmic Game Theory (SAGT), 2017

2017
[12]

Gairing, T

M. Gairing, T. Lücking, and M. Mavronicolas et al. Computing nash equilibria for schedul- ing on restricted parallel links.Theory of Computing Systems, 47(2):405–432, 2010

2010
[13]

R.L. Graham. Bounds for certain multiprocessing anomalies.Bell Systems Technical Journal, 45:1563–1581, 1966

1966
[14]

J. N. D. Gupta and S. K. Gupta. Single facility scheduling with nonlinear processing times. Computers ind. Engng, 14:387–393, 1987

1987
[15]

K. I-J. Ho, J. Y-T. Leung, and W-D. Wei. Complexity of scheduling tasks with time dependent execution times.Information Processing Letters, 48:315–320, 1993

1993
[16]

Immorlica, L

N. Immorlica, L. Li, V. S. Mirrokni, and A. S. Schulz. Coordination mechanisms for selfish scheduling.Theor. Comput. Sci., 410(17):1589–1598, 2009. 40

2009
[17]

Kang and C.T

L. Kang and C.T. Ng. A note on fully polynomial-time approximation scheme for parallel- machine scheduling with deteriorating jobs.Int. J. Production Economics, 109:180–184, 2007

2007
[18]

Koutsoupias and C

E. Koutsoupias and C. Papadimitriou. Worst-case equilibria.STACS’99: Proceedings of the 16th annual conference on Theoretical aspects of computer science, 1:404–413, 1999

1999
[19]

K. Li, C. Liu, and K. Li. An approximation algorithm based on game theory for scheduling simple linear deteriorating jobs.Theoretical Computer Science, 543:46–51, 2014

2014
[20]

Moesheiov

G. Moesheiov. V-shaped policies for scheduling deteriorating jobs.Operations Research, 39:979–991, 1991

1991
[21]

Mosheiov

G. Mosheiov. A note on scheduling deteriorating jobs.Mathematical and Computer Mod- eling, 41:883–886, 2005

2005
[22]

Nicosia, A

G. Nicosia, A. Pacifici, and U. Pferschy. Scheduling with time dependent utilities: Fairness and efficiency.arXiv.https://doi.org/10.48550/arXiv.2603.28800, 2026

work page doi:10.48550/arxiv.2603.28800 2026
[23]

Ravindran Vijayalakshmi, M

V. Ravindran Vijayalakshmi, M. Schröder, and T. Tamir. Scheduling games with machine- dependent priority lists.Theoretical Computer Science, 855:90–103, 2021

2021
[24]

R. W. Rosenthal. A class of games possessing pure-strategy nash equilibria.International Journal of Game Theory, 2:65–67, 1973

1973
[25]

V. Kann. Maximum bounded 3-dimensional matching is max snp-complete.Inf. Process. Lett, 37:27–35, 1991

1991
[26]

J. Wang. A note on single-machine scheduling with decreasing time-dependant job pro- cessing times.Applied Mathematical Modelling, 34:294–300, 2010

2010
[27]

Wang and Z

J. Wang and Z. Xia. Scheduling jobs under decrasing linear deterioration.Information Processing Letters, 94:63–69, 2005

2005
[28]

G. Yu. A coordination mechanism for scheduling game on parallel-batch machines with deterioration jobs.Mathematical Problems in Engineering, 2022. 41

2022