The power of mediators: Price of anarchy and stability in Bayesian games with submodular social welfare

Kaito Fujii · 2025

Read The power of mediators: Price of anarchy and stability in Bayesian games with submodular social welfare by Kaito Fujii (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-02655.txt.

Introduction

Kaito Fujii investigates how much mediators can improve outcomes in Bayesian games. A mediator communicates with players and can guide them toward equilibria of varying quality. Different communication protocols produce the family of equilibrium concepts known as Bayes correlated equilibria, and the question is what social welfare they can guarantee.

Fujii analyzes a general class of Bayesian games with submodular social welfare, extending utility game frameworks used for facility location, influence maximization, and resource allocation. He derives upper and lower bounds on the price of anarchy and the price of stability for a broad class of these equilibria. Central to the analysis is the strategy representability gap, the welfare lost when players cannot see each other's types. For monotone submodular welfare, that gap behaves very differently under independent versus correlated priors. The bounds clarify when a mediator's guidance is powerful and when private information limits it.

Catalog record

CREATORKaito Fujii
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE101 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-02655

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The power of mediators: Price of anarchy and stability in Bayesian games with submodular social welfare Kaito Fujii Abstract This paper investigates the role of mediators in Bayesian games by examining their impact on social welfare through the price of anarchy (PoA) and price of stability (PoS). Mediators can communicate with players to guide them toward equilibria of varying quality, and different communication protocols lead to a variety of equilibrium concepts collectively known as Bayes (coarse) correlated equilibria. To analyze these equilibrium concepts, we consider a general class of Bayesian games with submodular social welfare, which naturally extends valid utility games and their variant, basic utility games. These frameworks, introduced by Vetta 2002 , have been developed to analyze the social welfare guarantees of equilibria in games such as competitive facility location, influence maximization, and other resource allocation problems. We provide upper and lower bounds on the PoA and PoS for a broad class of Bayes (coarse) correlated equilibria. Central to our analysis is the strategy representability gap, which measures the multiplicative gap between the optimal social welfare achievable with and without knowledge of other players’ types. For monotone submodular social welfare functions, we show that this gap is 1 − 1 / e 1-1/\mathrm{e} for independent priors and Θ ⁡ ( 1 / n ) \Theta(1/\sqrt{n}) for correlated priors, where n n is the number of players. These bounds directly lead to upper and lower bounds on the PoA and PoS for various equilibrium concepts, while we also derive improved bounds for specific concepts by developing smoothness arguments. Notably, we identify a fundamental gap in the PoA and PoS across different classes of Bayes correlated equilibria, highlighting essential distinctions among these concepts. 1 Introduction Mediators play a significant role in shaping outcomes in Bayesian games, where players make decisions under uncertainty about other players’ private information. By communicating with players and facilitating coordination, mediators can influence players’ decision-making, guiding them toward equilibria with varying quality of social welfare. Depending on the communication protocols employed, various equilibrium concepts arise, collectively referred to as Bayes (coarse) correlated equilibria ( Forges 1993 ; Fujii 2023 ) (see Figure 1 ), which have recently attracted attention in information design studies ( Bergemann and Morris 2019 ) . These equilibrium concepts generalize Nash equilibria by allowing for coordination among players assisted by mediators, opening up the possibilities both improved and degraded social welfare. A key question in the study of Bayesian games is how mediators affect the quality of equilibria, particularly in terms of the price of anarchy (PoA) and the price of stability (PoS). The PoA measures the extent to which mediators can deteriorate the quality of equilibria compared to the optimal social welfare, whereas the PoS quantifies how close mediators can bring the best achievable equilibria to the optimal social welfare. Understanding these metrics is crucial for evaluating the positive and negative influence of mediators and designing communication strategies to optimize social welfare in real-world policymaking. To address this question, we focus on a general class of Bayesian games with submodular social welfare, which naturally extends valid utility games and their variant, basic utility games in the complete-information setting. Since the introduction by Vetta 2002 , valid and basic utility games have stood out as one of the most extensively studied frameworks of resource allocation games with diverse applications, including competitive facility location ( Vetta 2002 ; Ben-Porat and Tennenholtz 2017 ) , competitive influence maximization ( Bharathi et al. 2007 ; He and Kempe 2013 ) , and selfish routing ( Vetta 2002 ) . In the complete-information setting, Vetta 2002 proved that the PoA for mixed Nash equilibria is guaranteed to be at least 1/2 in any valid utility game. This bound was later extended to (coarse) correlated equilibria, a class of equilibria realized by mediators, by developing a general proof technique known as smoothness arguments by Roughgarden 2015a . In other words, mediators cannot reduce the quality of equilibria to less than half of the optimal social welfare, demonstrating that valid utility games are robust against malicious mediators. The goal of this study is to analyze the PoA and PoS in the Bayesian version of valid utility games. We suppose that each player i\in[n] possesses private information represented by a random variable \theta_{i}\in\Theta_{i} , referred as their type , and the type profile (\theta_{1},\theta_{2},\dots,\theta_{n}) is generated from a common prior distribution \rho\in\Delta(\Theta_{1}\times\dots\times\Theta_{n}) . To extend valid utility games to Bayesian setting, we consider a varying action set A_{i}^{\theta_{i}} depending on their own type \theta_{i} for each player i . 1 1 1 This definition based on type-dependent action sets is different from the standard formulation with fixed action sets A_{i} and type-dependent utility functions v_{i}\colon(\Theta_{1}\times\dots\times\Theta_{n})\times(A_{1}\times\dots\times A_{n})\to\mathbb{R} . However, as described in Section B.1 , any Bayesian game can be reformulated with type-dependent action spaces by treating each type-action pair (\theta_{i},a_{i}) as an action. The key feature of our formulation is the existence of a submodular social welfare function consistent across all type profiles, which facilitates our theoretical analysis. If there is a monotone submodular function f\colon 2^{E}\to\mathbb{R}_{\geq 0} , where E={\bigcup_{i\in N}\bigcup_{\theta_{i}\in\Theta_{i}}A_{i}^{\theta_{i}}} , that serves as a social welfare function satisfying the conditions for valid utility games for all type profiles, we refer to this Bayesian game as a Bayesian valid utility game (Bayesian basic utility games can be defined similarly). In practical examples of Bayesian valid and basic utility games, mediators commonly emerge as follows: 1. Transportation planners (mediators) coordinate commuters (players) with varying schedules (types) to choose transit options and avoid peak-hour congestion. 2. Volunteer coordinators (mediator) assist participants (players) with different availability or capabilities (type) in selecting suitable tasks. 3. Network planners (mediator) help devices (players) with different locations and demands (type) select appropriate base stations. Submodularity naturally arises in these applications, as the marginal gain in social welfare diminishes due to “crowding” when many users select the same resource. See Section B.2 for more detailed descriptions on these applications. Table 1: Summary of our main results. Note that the PoA decreases as the equilibrium concept is coarsened, while the PoS increases. Each of “valid” and “basic” stands for valid and basic utility games, and “independent” and “correlated” represent the assumption for type prior distributions. BNE, SF/ANFCE, ANF/SFCCE Com.Eq. BS, ANF/SFCBS PoA (valid, independent) 1/2 1/2 \in\left[\frac{1-1/\mathrm{e}}{2},0.441\right] PoA (valid, correlated) \Theta\left(\frac{1}{\sqrt{n}}\right) \Theta\left(\frac{1}{\sqrt{n}}\right) \Theta\left(\frac{1}{\sqrt{n}}\right) PoS (basic, independent) 1-1/\mathrm{e} \leq 4/5 1 PoS (basic, correlated) \Theta\left(\frac{1}{\sqrt{n}}\right) \leq 4/5 1 Bayes–Nash equilibria SFCE Communication equilibria ANFCE Bayesian solutions ANFCCE SFCCE ANFCBS SFCBS Figure 1: Relations of various classes of Bayes correlated equilibria and Bayes coarse correlated equilibria. The tail of each arrow is a subset of its head. Each of “CE”, “CCE”, “CBS”, “SF”, and “ANF” stands for “correlated equilibria”, “coarse correlated equilibria”, “coarse Bayesian solutions”, “strategic-form”, and “agent-normal-form”, respectively. See Appendix C for definitions. 1.1 Our contribution In this study, we analyze the PoA and PoS for various equilibrium concepts in Bayesian valid and basic utility games. The PoA and PoS are defined as the ratio of the expected social welfare value achieved by the worst and best equilibrium to the optimal social welfare value, respectively. The optimal social welfare value is defined as \mathop{\mathbb{E}}_{(\theta_{1},\dots,\theta_{n})\sim\rho}\left[\max_{(a_{1},\dots,a_{n})\in A^{\theta_{1}}_{1}\times\dots\times A^{\theta_{n}}_{n}}f(\{a_{1},\dots,a_{n}\})\right] ,

Read the complete text