We study network coordination problems, as captured by the setting of generalized network design (, 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 's Bayesian ignorance framework (TCS 2012). While the approach of 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.
Our work differs from @cite_14 in following four aspects. First, in the stochastic online optimization problem studied in @cite_14 , when each request @math arrives, the previous requests @math have been realized, and the realization is known. By contrast, in the BGND problem, every agent @math needs to be served without knowing the actual realization of the other agents. Second, the cost function studied in @cite_14 maps each resource @math to a fixed toll, which is subaddtive in the number of requests using @math , while our cost function is superaddtive. Third, in the BGND problem with the set connectivity requests, for each agent @math , each type @math is a set of terminals rather than a single terminal, and each action in @math is a Steiner tree spanning over the set of terminals corresponding to @math . Fourth, in the BGND problem, each prior distribution @math is over the types of agent @math , while there is no distribution over the agents.
@cite_14
2064147138
In this paper, we study online algorithms when the input is not chosen adversarially, but consists of draws from some given probability distribution. While this model has been studied for online problems like paging and k-server, it is not known how to beat the Φ(log n) bound for online Steiner tree if at each time instant, the demand vertex is a uniformly random vertex from the graph. For the online Steiner tree problem, we show that if each demand vertex is an independent draw from some probability distribution π: V → [0, 1], a variant of the natural greedy algorithm achieves Eω[A(ω)] Eω[OPT (ω)] = O(1); moreover, this result can be extended to some other subadditive problems. Both assumptions that the input sequence consists of independent draws from π, and that π is known to the algorithm are both essential; we show (almost) logarithmic lower bounds if either assumption is violated. Moreover, we give preliminary results on extending the Steiner tree results above to the related "expected ratio" measure Eω[ω(ω) OPT (ω)]. Finally, we use these ideas to give an average-case analysis of the Universal TSP problem.