pith. sign in

arxiv: 1907.00484 · v1 · pith:CUWL6773new · submitted 2019-06-30 · 💻 cs.GT · cs.DS

Bayesian Generalized Network Design

Yuval Emek , Shay Kutten , Ron Lavi , Yangguang Shi This is my paper

Pith reviewed 2026-05-25 11:51 UTC · model grok-4.3

classification 💻 cs.GT cs.DS
keywords networkbayesianuncertaintyalondesignfacegeneralizedaccount
0
0 comments X

The pith

Develops strongly polynomial time algorithms for local decision making under Bayesian uncertainty in generalized network design.

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

Network coordination problems require users to choose actions that together determine the quality of a shared network or facility. When users lack full information about what others will choose, the setting is modeled with Bayesian ignorance, where each user has a probability distribution over others' possible actions. The paper takes a prior combinatorial framework for such problems and adds the requirement that decisions must be made efficiently by local algorithms. The central technical result is a set of algorithms whose running time is polynomial in the input size and independent of the magnitude of numeric parameters. This shifts the focus from existence proofs to constructive, efficient procedures that can be implemented in distributed or centralized computational settings.

Core claim

Our main technical contribution is the development of (strongly) polynomial time algorithms for local decision making in the face of Bayesian uncertainty.

Load-bearing premise

That the Bayesian ignorance model from prior work can be combined with the generalized network design setting such that local decisions admit strongly polynomial time algorithms without requiring global knowledge or exponential enumeration.

read the original abstract

We study network coordination problems, as captured by the setting of generalized network design (Emek et al., STOC 2018), in the face of uncertainty resulting from partial information that the network users hold regarding the actions of their peers. This uncertainty is formalized using Alon et al.'s Bayesian ignorance framework (TCS 2012). While the approach of Alon et al. is purely combinatorial, the current paper takes into account computational considerations: Our main technical contribution is the development of (strongly) polynomial time algorithms for local decision making in the face of Bayesian uncertainty.

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

0 major / 1 minor

Summary. The paper studies generalized network design (Emek et al., STOC 2018) under Bayesian ignorance (Alon et al., TCS 2012). It asserts the existence of strongly polynomial-time algorithms for local decision making under this uncertainty model, shifting from the purely combinatorial treatment in prior work to one that accounts for computational efficiency.

Significance. If the claimed algorithms are correct, the result would usefully combine two existing frameworks while guaranteeing strong polynomial runtime for local decisions, which is a concrete strength in algorithmic game theory. No machine-checked proofs or reproducible code are mentioned.

minor comments (1)
  1. Abstract: the main claim is stated at a high level without any indication of the algorithmic technique, runtime analysis, or how the Bayesian model is integrated with the network design setting.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no information on free parameters, axioms, or invented entities used in the algorithms or proofs.

pith-pipeline@v0.9.0 · 5618 in / 1003 out tokens · 32896 ms · 2026-05-25T11:51:46.070963+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    Ajit Agrawal, Philip Klein, and R. Ravi. When trees colli de: An approximation algorithm for the generalized steiner problem on networks. SIAM Journal on Computing , 24(3):440– 456, 1995

    work page 1995

  2. [2]

    Exact price of anarchy for polynomial congesti on games

    Sebastian Aland, Dominic Dumrauf, Martin Gairing, Burk hard Monien, and Florian Schoppmann. Exact price of anarchy for polynomial congesti on games. In Annual Sympo- sium on Theoretical Aspects of Computer Science , pages 218–229. Springer, 2006

    work page 2006

  3. [3]

    Energy-efficient algorithms

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

    work page 2010

  4. [4]

    Bayesian ignorance

    Noga Alon, Yuval Emek, Michal Feldman, and Moshe Tennenh oltz. Bayesian ignorance. Theoretical Computer Science, 452:1–11, 2012. Preliminary version appears in Proceedin gs of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Dis tributed Computing, pp. 384-391. ACM, 2010

    work page 2012

  5. [5]

    Routing for power minimization in the speed scaling model

    Matthew Andrews, Antonio Fern´ andez Anta, Lisa Zhang, a nd Wenbo Zhao. Routing for power minimization in the speed scaling model. IEEE/ACM Transactions on Networking , 20(1):285 –294, feb. 2012

    work page 2012

  6. [6]

    The price of stability for network design with fair cost allocation

    Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, E va Tardos, Tom Wexler, and Tim Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing , 38(4):1602–1623, 2008. Preliminary version appears in Pr oceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004

    work page 2008

  7. [7]

    Energy efficient scheduling and routing via rand omized rounding

    Evripidis Bampis, Alexander Kononov, Dimitrios Letsio s, Giorgio Lucarelli, and Maxim Sviridenko. Energy efficient scheduling and routing via rand omized rounding. In 33nd International Conference on Foundations of Software Technol ogy and Theoretical Computer Science, page 449, 2013

    work page 2013

  8. [8]

    Speed scal ing to manage energy and tem- perature

    Nikhil Bansal, Tracy Kimbrel, and Kirk Pruhs. Speed scal ing to manage energy and tem- perature. J. ACM , 54(1):3:1–3:39, 2007

    work page 2007

  9. [9]

    Improved bounds on bell nu mbers and on moments of sums of random variables

    Daniel Berend and Tamir Tassa. Improved bounds on bell nu mbers and on moments of sums of random variables. Probability and Mathematical Statistics , 30(2):185–205, 2010

    work page 2010

  10. [10]

    Steiner tree approximation via iterative randomized rounding

    Jaros/suppress law Byrka, Fabrizio Grandoni, Thomas Rothvoss,and Laura Sanit` a. Steiner tree approximation via iterative randomized rounding. Journal of the ACM (JACM) , 60(1):6,

    work page

  11. [11]

    Preliminary version in STOC’10

    work page

  12. [12]

    Approximation algorithms for directed steiner problems

    Moses Charikar, Chandra Chekuri, To-yat Cheung, Zuo Da i, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed steiner problems. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 192–200, 1998

    work page 1998

  13. [13]

    Set connectivity problems in undirected graphs and the directed steiner network probl em

    Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Sege v. Set connectivity problems in undirected graphs and the directed steiner network probl em. ACM Trans. Algorithms , 7(2):18:1–18:17, 2011

    work page 2011

  14. [14]

    Ieee 802.3 az: the road to energy effi cient ethernet

    Ken Christensen, Pedro Reviriego, Bruce Nordman, Mich ael Bennett, Mehrgan Mostowfi, and Juan Antonio Maestro. Ieee 802.3 az: the road to energy effi cient ethernet. IEEE Communications Magazine , 48(11), 2010

    work page 2010

  15. [15]

    Progressive hedging-based metaheuristics for stoch astic network design

    Teodor Gabriel Crainic, Xiaorui Fu, Michel Gendreau, W alter Rei, and Stein W Wal- lace. Progressive hedging-based metaheuristics for stoch astic network design. Networks, 58(2):114–124, 2011. 23

    work page 2011

  16. [16]

    E. W. Dijkstra. A note on two problems in connexion with g raphs. Numer. Math., 1(1):269– 271, 1959

    work page 1959

  17. [17]

    Ap proximating generalized network design under (dis)economies of scale with applicat ions to energy efficiency

    Yuval Emek, Shay Kutten, Ron Lavi, and Yangguang Shi. Ap proximating generalized network design under (dis)economies of scale with applicat ions to energy efficiency. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Co mputing, STOC 2018, pages 598–606, New York, NY, USA, 2018. ACM

    work page 2018

  18. [18]

    Oblivious routing for the lp-norm

    Matthias Englert and Harald R¨ acke. Oblivious routing for the lp-norm. In Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’09, pages 32–40, Washington, DC, USA, 2009. IEEE Computer Socie ty

    work page 2009

  19. [19]

    Oblivious routing for the lp-norm

    Matthias Englert and Harald R¨ acke. Oblivious routing for the lp-norm. In Foundations of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposium on , pages 32–40. IEEE, 2009

    work page 2009

  20. [20]

    Fredman and Robert Endre Tarjan

    Michael L. Fredman and Robert Endre Tarjan. Fibonacci h eaps and their uses in improved network optimization algorithms. J. ACM , 34(3):596–615, 1987

    work page 1987

  21. [21]

    Stochastic analyses for online combinatorial optimization problems

    Naveen Garg, Anupam Gupta, Stefano Leonardi, and Piotr Sankowski. Stochastic analyses for online combinatorial optimization problems. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’08, pages 942–951. Society for Industrial and Applied Mathematics, 2008

    work page 2008

  22. [22]

    Oblivious network design

    Anupam Gupta, Mohammad T Hajiaghayi, and Harald R¨ acke . Oblivious network design. In Proceedings of the seventeenth annual ACM-SIAM symposium on D iscrete algorithm , pages 970–979. Society for Industrial and Applied Mathemat ics, 2006

    work page 2006

  23. [23]

    An edge in time s aves nine: Lp rounding approximation algorithms for stochastic network design

    Anupam Gupta, R Ravi, and Amitabh Sinha. An edge in time s aves nine: Lp rounding approximation algorithms for stochastic network design. I n FOCS, pages 218–227, 2004

    work page 2004

  24. [24]

    Hayes, Hariharan Narayanan , Harald R¨ acke, and Jaikumar Radhakrishnan

    Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan , Harald R¨ acke, and Jaikumar Radhakrishnan. Minimizing average latency in oblivious ro uting. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’08, pages 200– 207, Philadelphia, PA, USA, 2008. Society for Industrial an d Applied Mathematics

    work page 2008

  25. [25]

    Enhanced intel speedstep technology for the int el pentium m processor

    Intel. Enhanced intel speedstep technology for the int el pentium m processor. In Intel White Paper 301170-001 , 2004

    work page 2004

  26. [26]

    Sandy Irani and Kirk R. Pruhs. Algorithmic problems in p ower management. SIGACT News, 36(2):63–76, 2005

    work page 2005

  27. [27]

    J.L.W.V. Jensen. Sur les fonctions convexes et les in´ e galit´ es entre les valeurs moyennes. Acta Mathematica, 30(1):175–193, 1906

    work page 1906

  28. [28]

    Mixing times a nd ℓp bounds for oblivi- ous routing

    Gregory Lawler and Hariharan Narayanan. Mixing times a nd ℓp bounds for oblivi- ous routing. In Proceedings of the Meeting on Analytic Algorithmics and Comb inatorics, ANALCO ’09, pages 66–74, Philadelphia, PA, USA, 2009. Socie ty for Industrial and Ap- plied Mathematics

    work page 2009

  29. [29]

    Solving o ptimization problems with dis- economies of scale via decoupling

    Konstantin Makarychev and Maxim Sviridenko. Solving o ptimization problems with dis- economies of scale via decoupling. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS , 2014

    work page 2014

  30. [30]

    Potential games

    Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior , 14(1):124–143, 1996. 24

    work page 1996

  31. [31]

    Reducing network energy consumption via sleepi ng and rate-adaptation

    Sergiu Nedevschi, Lucian Popa, Gianluca Iannaccone, S ylvia Ratnasamy, and David Wetherall. Reducing network energy consumption via sleepi ng and rate-adaptation. In Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implemen- tation, NSDI’08, pages 323–336. USENIX Association, 2008

    work page 2008

  32. [32]

    Survey on oblivious routing strategies

    Harald R¨ acke. Survey on oblivious routing strategies . In Mathematical Theory and Com- putational Practice , volume 5635 of Lecture Notes in Computer Science , pages 419–429. Springer Berlin Heidelberg, 2009

    work page 2009

  33. [33]

    Accelerat- ing the benders decomposition method: Application to stoch astic network design problems

    Ragheb Rahmaniani, Teodor Gabriel Crainic, Michel Gen dreau, and Walter Rei. Accelerat- ing the benders decomposition method: Application to stoch astic network design problems. SIAM Journal on Optimization , 28(1):875–903, 2018

    work page 2018

  34. [34]

    The price of anarchy in games of incomp lete information

    Tim Roughgarden. The price of anarchy in games of incomp lete information. In Proceedings of the 13th ACM Conference on Electronic Commerce , pages 862–879. ACM, 2012

    work page 2012

  35. [35]

    Intrinsic robustness of the price of a narchy

    Tim Roughgarden. Intrinsic robustness of the price of a narchy. Journal of the ACM (JACM), 62(5):32, 2015. Preliminary version in STOC’09

    work page 2015

  36. [36]

    Probability inequalities of the tche bycheff type

    I Richard Savage. Probability inequalities of the tche bycheff type. Journal of Research of the National Bureau of Standards-B. Mathematics and Mathemati cal Physics B , 65(3):211–222, 1961

    work page 1961

  37. [37]

    Random ized oblivious integral routing for minimizing power cost

    Yangguang Shi, Fa Zhang, Jie Wu, and Zhiyong Liu. Random ized oblivious integral routing for minimizing power cost. Theoretical Computer Science , 607:221–246, 2015

    work page 2015

  38. [38]

    Power-awa re speed scaling in processor sharing systems

    Adam Wierman, Lachlan LH Andrew, and Ao Tang. Power-awa re speed scaling in processor sharing systems. In 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societ ies, INFOCOM , pages 2007 –2015, april 2009

    work page 2007

  39. [39]

    F. Yao, A. Demers, and S. Shenker. A scheduling model for reduced cpu energy. In Proceedings of IEEE 36th Annual Foundations of Computer Scien ce, pages 374–382, 1995. 25

    work page 1995