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.
The Bayesian approach is often used in the game theoretic literature to model the uncertainty a player experiences regarding the actions taken by the other players. Roughgarden @cite_2 studies a (among other things) in which the players share (equally) the cost of the edges they use and proposes a theoretical tool called to analyze the of this game in a Bayesian setting, defined as @math , where @math denotes the set of . In particular, he proves that with the cost function @math , the PoA is bounded by @math . We employ the smoothness toolbox in our algorithmic construction, as further described in (see also the overview in ).
@cite_2
2136124238
We define smooth games of incomplete information. We prove an "extension theorem" for such games: price of anarchy bounds for pure Nash equilibria for all induced full-information games extend automatically, without quantitative degradation, to all mixed-strategy Bayes-Nash equilibria with respect to a product prior distribution over players' preferences. We also note that, for Bayes-Nash equilibria in games with correlated player preferences, there is no general extension theorem for smooth games. We give several applications of our definition and extension theorem. First, we show that many games of incomplete information for which the price of anarchy has been studied are smooth in our sense. Thus our extension theorem unifies much of the known work on the price of anarchy in games of incomplete information. Second, we use our extension theorem to prove new bounds on the price of anarchy of Bayes-Nash equilibria in congestion games with incomplete information.