Computing Equilibria in Binary Networked Public Goods Games
Authors: Sixie Yu, Kai Zhou, Jeffrey Brantingham, Yevgeniy Vorobeychik2310-2317
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we propose a heuristic approach for computing approximate equilibria in general binary networked public goods games, and experimentally demonstrate its effectiveness. Due to space limitation, some proofs are deferred to the extended version1. 1 Introduction Public goods games have been a major subject of inquiry as a natural way to model the tension between individual interest and social good (Kollock 1998; Santos, Santos, and Pacheco 2008). In a canonical version of such games, individuals choose the amount to invest in a public good, and the subsequent value of the good, which is determined by total investment of the community, is then shared equally by all. A number of versions of this game have been studied, including variants where players are situated on a network, with individual payoffs determined solely by the actions of their network neighbors (Bramoull e and Kranton 2007). An important variation of networked public goods games treats investment decisions as binary (Galeotti et al. 2010). One motivating example is crime reporting, known to vary widely, with the general observation that crime is considerably under-reported (Morgan and Truman 2017). In a game theoretic abstraction of crime reporting, individuals choose whether or not to report crimes, and benefits accrue to the broader community, for example, causing a reduction in overall crime rate. Another example of binary public goods games is vaccination. In this example, parents decide whether to vaccinate their children, with herd immunity becoming the public good. To keep terminology general, we will refer to Copyright c 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 1Extended version available at: https://arxiv.org/abs/1911.05788 the binary decision whether or not to invest in a public good (thus, reporting a crime and vaccinating are forms of such investment). A special case of binary public goods games (BNPGs), commonly known as best-shot games, has received some prior attention (Dallasta, Pin, and Ramezanpour 2011; Galeotti et al. 2010; Komarovsky et al. 2015; Levit et al. 2018). However, best-shot games make a strong assumption about the structure of the player utility functions. While Levit et al. (Levit et al. 2018) recently showed that equilibria for best-shot games can be computed in polynomial time by best response dynamics, these may fail to find social welfareoptimal equilibria, and nothing is known about BNPGs more generally. We study the problem of computing pure strategy Nash equilibria in general binary public goods games on networks. We provide examples to show that a pure strategy Nash equilibria is not guaranteed to exist for general BNPGs. Furthermore, we show that even determining if a pure strategy Nash equilibrium exists is hard in general. However, while pure strategy equilibria need not in general exist, and are hard to compute, we exhibit a number of positive results for important special cases. One class of special cases pertains to binary public goods games for completely connected networks (communities), in which case an equilibrium can be found efficiently if it exists. Similarly, we can efficiently find a pure strategy equilibrium in general BNPGs when the graph is a tree. If we further restrict the externalities to have an identical impact on all players (we call this the homogeneous case), we can characterize all pure strategy equilibria, and efficiently compute a socially optimal equilibrium. Moreover, if both investment costs and externalities are identical (termed the fully homogeneous case), we can characterize all pure strategy equilibria for arbitrary networks. Finally, we present a heuristic approach for finding approximate equilibria to tackle general BNPGs, and experimentally demonstrate that it is highly effective. Our algorithmic results are summarized in Table 1. |
| Researcher Affiliation | Academia | Sixie Yu,1 Kai Zhou,1 P. Jeffrey Brantingham,2 Yevgeniy Vorobeychik1 1Department of Computer Science and Engineering, Washington University in St. Louis 2Department of Anthropology, University of California, Los Angeles {sixie.yu,zhoukai, yvorobeychik}@wustl.edu, branting@ucla.edu |
| Pseudocode | Yes | Algorithm 1 Compute conditional best-response table TY for a leaf node; Algorithm 2 Compute conditional best-response table TY for an internal node; Algorithm 3 Heuristic to find approximate PSNE |
| Open Source Code | No | The paper provides a link to an extended version of the paper on arXiv, but not to source code for the methodology or experiments. |
| Open Datasets | Yes | The experiments were conducted on a Facebook network (Leskovec and Mcauley 2012), which is a connected graph with 4093 nodes and 88234 edges. |
| Dataset Splits | No | The paper mentions using a Facebook network but does not specify any training, validation, or test splits for the data. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run the experiments. |
| Software Dependencies | No | The paper does not specify any software or library names with version numbers used in the experiments. |
| Experiment Setup | Yes | The parameters ci are sampled from the uniform distribution on [0, 1]. In our experiments we assume gi = λihi where λi is sampled uniformly at random on [0, 1], and hi are either convex or concave, corresponding to strategic substitutes and complements, respectively (Galeotti et al. 2010). If gi(x) is convex, it is sampled from a set of convex functions { α log (x + 1)β} by uniformly at random sampling α and β from {0.1, 0.3, 0.5, 0.7, 0.9} and {1.2, 1.5, 2.0}, respectively. Similarly, if gi(x) is concave it is sampled from a set of concave functions { αxβ} by sampling α and β from the same sets. We normalize the values of the utility functions Ui to [0, 1] when evaluating the approximation quality of an ϵ-PSNE. In each simulated game, we feature a mix of players with concave and convex gi. This mix is determined using a parameter γ [0, 1], which is the probability that a particular player i s gi is concave; consequently, higher γ implies a larger fraction of the population with convex utility functions. For each value of γ we simulated 1000 BNPG games. The experiments were conducted on a Facebook network (Leskovec and Mcauley 2012), which is a connected graph with 4093 nodes and 88234 edges. The input δ is the stopping criterion. When the distance d of two consecutive profiles is small enough (< δ) the algorithm converges. |