pith. sign in

arxiv: 1907.05926 · v1 · pith:ZUF24EDQnew · submitted 2019-07-12 · 💻 cs.GT

On the Price of Anarchy of Cost-Sharing in Real-Time Scheduling Systems

Eirini Georgoulaki , Kostas Kollias This is my paper

Pith reviewed 2026-05-24 21:55 UTC · model grok-4.3

classification 💻 cs.GT
keywords price of anarchycost-sharing gamesreal-time schedulingcoordination mechanismmonomial costsexternalitiesNash equilibriascheduling systems
0
0 comments X

The pith

A coordination mechanism without instance knowledge reduces the price of anarchy to 2 for unit-cost real-time scheduling games.

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

The paper studies cost-sharing games in real-time scheduling systems where server activation costs are monomial functions of load. For monomials with degree less than one, which induce positive externalities, the price of anarchy grows polynomially with the number of jobs. For degrees greater than one, inducing negative externalities, existing results already give constant bounds. The central result introduces a simple coordination mechanism that operates without any instance-specific information and improves the price of anarchy for n jobs with unit activation costs from Theta of square root n down to 2. The same mechanism yields comparable gains on restricted monomial instances but leaves the price of anarchy super-constant on unrestricted monomial instances.

Core claim

In cost-sharing games for real-time scheduling with monomial activation costs, a coordination mechanism that requires no knowledge of the instance achieves a price of anarchy of 2 for games with any number n of jobs and unit activation costs, improving on the previous Theta(sqrt(n)) bound; the mechanism yields analogous constant bounds on a restricted class of monomial instances but the price of anarchy remains super-constant for general monomial instances.

What carries the argument

The coordination mechanism, a simple rule that assigns jobs to time slots without using instance-specific information, which enforces bounded inefficiency in the resulting Nash equilibria.

If this is right

  • For unit activation costs the price of anarchy is at most 2 under the mechanism.
  • For a restricted class of monomial activation costs the price of anarchy remains constant.
  • For general monomial activation costs the price of anarchy stays super-constant even after applying the mechanism.
  • Without the mechanism, games with positive-externality monomials exhibit polynomially growing price of anarchy.

Where Pith is reading between the lines

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

  • The mechanism may stabilize large-scale scheduling problems whenever activation costs are close to linear.
  • Similar coordination rules could be tested in other resource-allocation games that exhibit load-dependent costs.
  • Empirical evaluation on realistic job-arrival traces would reveal whether the constant bound translates to measurable cost savings.

Load-bearing premise

The analysis assumes that activation costs are exactly monomial functions of load and that the coordination mechanism operates without any instance-specific information.

What would settle it

Construct a concrete scheduling instance with 100 jobs and unit activation costs, apply the coordination mechanism, compute the worst-case ratio of equilibrium social cost to optimal social cost, and check whether the ratio exceeds 2.

read the original abstract

We study cost-sharing games in real-time scheduling systems where the activation cost of the server at any given time is a function of its load. We focus on monomial cost functions and consider both the case when the degree is less than one (inducing positive externalities for the jobs) and when it is greater than one (inducing negative externalities for the jobs). For the former case, we provide tight price of anarchy bounds which show that the price of anarchy grows to infinity as a polynomial of the number of jobs in the game. For the latter, we observe that existing results provide constant and tight (asymptotically in the degree of the monomial) bounds on the price of anarchy. We then switch our attention to improving the price of anarchy by means of a simple coordination mechanism that has no knowledge of the instance. We show that our mechanism reduces the price of anarchy of games with $n$ jobs and unit activation costs from $\Theta(\sqrt{n})$ to $2$. We also show that for a restricted class of instances a similar improvement is achieved for monomial activation costs. This is not the case, however, for unrestricted instances of monomial costs for which we prove that the price of anarchy remains super-constant for our mechanism.

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.

Referee Report

2 major / 1 minor

Summary. The manuscript studies cost-sharing games in real-time scheduling systems where server activation costs are monomial functions of load. For monomials of degree less than 1 it derives tight PoA bounds that grow polynomially with the number of jobs n; for degrees greater than 1 it invokes existing constant (degree-tight) bounds. It then introduces an instance-agnostic coordination mechanism that reduces PoA from Θ(√n) to 2 for unit activation costs, obtains analogous improvement on a restricted subclass of monomial instances, and proves that the PoA remains super-constant for the same mechanism on unrestricted monomial instances.

Significance. If the stated bounds and mechanism analysis hold, the work clarifies how the sign of externalities (determined by monomial degree) governs PoA growth and demonstrates both the reach and the intrinsic limits of information-free coordination mechanisms. The explicit negative result for general monomials is a useful boundary marker for the literature on PoA in scheduling games.

major comments (2)
  1. [Abstract] Abstract (final paragraph): the headline claim that the mechanism reduces PoA to 2 is load-bearing and is stated only for unit (constant) activation costs; the subsequent proof that the identical mechanism yields super-constant PoA for general monomials must be examined to confirm that the positive bound does not inadvertently rely on instance-specific data or on the cost being exactly constant rather than any monomial of degree 0.
  2. [Mechanism definition and analysis sections] Mechanism definition and analysis sections: the restricted class of instances for which the mechanism achieves constant PoA with general monomials must be defined precisely (including any restrictions on job sizes, arrival times, or cost parameters) so that the scope of the positive result can be assessed; without an explicit characterization the claim remains difficult to evaluate.
minor comments (1)
  1. [Abstract] Abstract: the sentence 'a similar improvement is achieved for monomial activation costs' should be rephrased to 'for a restricted class of monomial instances' to prevent readers from overlooking the limitation already stated two sentences later.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful comments, which help improve the clarity of our results on the price of anarchy and coordination mechanisms in scheduling games. We address each major comment below and will incorporate the requested clarifications in the revised version.

read point-by-point responses

  1. Referee: [Abstract] Abstract (final paragraph): the headline claim that the mechanism reduces PoA to 2 is load-bearing and is stated only for unit (constant) activation costs; the subsequent proof that the identical mechanism yields super-constant PoA for general monomials must be examined to confirm that the positive bound does not inadvertently rely on instance-specific data or on the cost being exactly constant rather than any monomial of degree 0.

    Authors: The positive bound of 2 applies exclusively to unit (constant) activation costs and is achieved by an instance-agnostic mechanism; the analysis does not use instance-specific data. The super-constant negative result for general monomials is proven separately and relies on the variability of the monomial degree. We will revise the abstract to explicitly note that the bound of 2 holds only for constant costs and add a clarifying sentence in the mechanism analysis section to separate the constant-cost case from the general-monomial negative result. revision: yes

  2. Referee: [Mechanism definition and analysis sections] Mechanism definition and analysis sections: the restricted class of instances for which the mechanism achieves constant PoA with general monomials must be defined precisely (including any restrictions on job sizes, arrival times, or cost parameters) so that the scope of the positive result can be assessed; without an explicit characterization the claim remains difficult to evaluate.

    Authors: We agree that an explicit characterization is needed for the restricted subclass where constant PoA is achieved with general monomials. In the revised manuscript we will add a formal definition of this class, specifying the precise restrictions on job sizes, arrival times, and cost parameters that enable the constant bound. revision: yes

Circularity Check

0 steps flagged

No circularity: standard PoA bounds derived from game-theoretic analysis without self-referential reductions.

full rationale

The paper derives PoA bounds analytically for monomial activation costs under an instance-agnostic coordination mechanism. It explicitly distinguishes the unit-cost case (PoA reduced to 2) from general monomials (remains super-constant) and from degree >1 cases (constant bounds from prior results). No self-citations are load-bearing for the central claims, no parameters are fitted then renamed as predictions, and no equations reduce to their inputs by definition. The derivation chain relies on standard equilibrium analysis and is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions from algorithmic game theory without introducing new free parameters or invented entities.

axioms (1)
  • standard math Standard definitions of Nash equilibrium, social cost, and price of anarchy in cost-sharing games
    Invoked throughout the analysis of equilibria and bounds.

pith-pipeline@v0.9.0 · 5754 in / 1142 out tokens · 21464 ms · 2026-05-24T21:55:58.409735+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Aland, D

    S. Aland, D. Dumrauf, M. Gairing, B. Monien, and F. Schoppm ann. Exact price of anarchy for polynomial congestion games. SIAM J. Comput. , 40(5):1211–1233, 2011

    work page 2011

  2. [2]

    S. Albers. Energy-efficient algorithms. Commun. ACM , 53(5):86–96, 2010

    work page 2010

  3. [3]

    Anshelevich, A

    E. Anshelevich, A. Dasgupta, J. M. Kleinberg, É. Tardos, T . Wexler, and T. Rough- garden. The price of stability for network design with fair c ost allocation. SIAM J. Comput. , 38(4):1602–1623, 2008

    work page 2008

  4. [4]

    Awerbuch, Y

    B. Awerbuch, Y. Azar, and A. Epstein. The price of routing u nsplittable flow. In Proceedings of the 37th Annual ACM Symposium on Theory of Com puting, Baltimore, MD, USA, May 22-24, 2005 , pages 57–66, 2005

    work page 2005

  5. [5]

    Y. Azar, L. Fleischer, K. Jain, V. S. Mirrokni, and Z. Svitk ina. Optimal co- ordination mechanisms for unrelated machine scheduling. Operations Research, 63(3):489–500, 2015

    work page 2015

  6. [6]

    Bar-Noy, S

    A. Bar-Noy, S. Guha, J. Naor, and B. Schieber. Approximati ng the throughput of multiple machines in real-time scheduling. SIAM J. Comput. , 31(2):331–352, 2001

    work page 2001

  7. [7]

    Bhawalkar, M

    K. Bhawalkar, M. Gairing, and T. Roughgarden. Weighted co ngestion games: The price of anarchy, universal worst-case examples, and ti ghtness. ACM Trans. Economics and Comput. , 2(4):14:1–14:23, 2014

    work page 2014

  8. [8]

    Caragiannis

    I. Caragiannis. Efficient coordination mechanisms for unr elated machine schedul- ing. Algorithmica, 66(3):512–540, 2013

    work page 2013

  9. [9]

    Chang, H

    J. Chang, H. N. Gabow, and S. Khuller. A model for minimizin g active processor time. Algorithmica, 70(3):368–405, 2014. 13

    work page 2014

  10. [10]

    Christodoulou and E

    G. Christodoulou and E. Koutsoupias. The price of anarch y of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Com - puting, Baltimore, MD, USA, May 22-24, 2005 , pages 67–73, 2005

    work page 2005

  11. [11]

    Christodoulou, E

    G. Christodoulou, E. Koutsoupias, and A. Nanavati. Coor dination mechanisms. In Automata, Languages and Programming: 31st International C olloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings , pages 345–357, 2004

    work page 2004

  12. [12]

    R. Cole, J. R. Correa, V. Gkatzelis, V. S. Mirrokni, and N. Olver. Decentral- ized utilitarian mechanisms for scheduling games. Games and Economic Behavior , 92:306–326, 2015

    work page 2015

  13. [13]

    Gairing, K

    M. Gairing, K. Kollias, and G. Kotsialou. Tight bounds fo r cost-sharing in weighted congestion games. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proc eedings, Part II , pages 626–637, 2015

    work page 2015

  14. [14]

    Gkatzelis, K

    V. Gkatzelis, K. Kollias, and T. Roughgarden. Optimal co st-sharing in general resource selection games. Operations Research, 64(6):1230–1238, 2016

    work page 2016

  15. [15]

    M. X. Goemans, V. S. Mirrokni, and A. Vetta. Sink equilibr ia and convergence. In 46th Annual IEEE Symposium on Foundations of Computer Scien ce (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings , pages 142–154, 2005

    work page 2005

  16. [16]

    Gopalakrishnan, J

    R. Gopalakrishnan, J. R. Marden, and A. Wierman. Potenti al games are Necessary to ensure pure nash equilibria in cost sharing games. Math. Oper. Res., 39(4):1252– 1296, 2014

    work page 2014

  17. [17]

    Immorlica, L

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

    work page 2009

  18. [18]

    Irani and K

    S. Irani and K. Pruhs. Algorithmic problems in power mana gement. SIGACT News, 36(2):63–76, 2005

    work page 2005

  19. [19]

    Khandekar, B

    R. Khandekar, B. Schieber, H. Shachnai, and T. Tamir. Rea l-time scheduling to minimize machine busy times. J. Scheduling , 18(6):561–573, 2015

    work page 2015

  20. [20]

    Klimm and D

    M. Klimm and D. Schmand. Sharing non-anonymous costs of m ultiple resources optimally. In Algorithms and Complexity - 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings , pages 274–287, 2015

    work page 2015

  21. [21]

    Kollias and T

    K. Kollias and T. Roughgarden. Restoring pure equilibri a to weighted congestion games. ACM Trans. Economics and Comput. , 3(4):21:1–21:24, 2015

    work page 2015

  22. [22]

    Koutsoupias and C

    E. Koutsoupias and C. H. Papadimitriou. Worst-case equi libria. Computer Science Review, 3(2):65–69, 2009

    work page 2009

  23. [23]

    J. R. Marden and M. Philips. Optimizing the price of anarc hy in concave cost sharing games. In 2017 American Control Conference, ACC 2017, Seattle, W A, USA, May 24-26, 2017 , pages 5237–5242, 2017

    work page 2017

  24. [24]

    J. R. Marden and A. Wierman. Distributed welfare games. Operations Research, 61(1):155–168, 2013

    work page 2013

  25. [25]

    R. W. Rosenthal. A class of games possessing pure-strate gy nash equilibria. Int. J. Game Theory , 2(1):65–67, 1973

    work page 1973

  26. [26]

    Roughgarden

    T. Roughgarden. Intrinsic robustness of the price of ana rchy. J. ACM , 62(5):32:1– 32:42, 2015

    work page 2015

  27. [27]

    Roughgarden and O

    T. Roughgarden and O. Schrijvers. Network cost-sharing without anonymity. ACM Trans. Economics and Comput. , 4(2):8:1–8:24, 2016

    work page 2016

  28. [28]

    T. Tamir. Cost-sharing games in real-time scheduling sy stems. In Web and Internet Economics - 14th International Conference, WINE 2018, Oxfo rd, UK, December 15-17, 2018, Proceedings, pages 423–437, 2018

    work page 2018

  29. [29]

    von Falkenhausen and T

    P. von Falkenhausen and T. Harks. Optimal cost sharing fo r resource selection games. Math. Oper. Res. , 38(1):184–208, 2013. 14

    work page 2013