Extensions to the Chicken Game in the Context of Public Goods

We study the Edge-Building Game (EBG), a parameterized formulation of the Chicken Game in the context of a public goods game. In the EBG, each of two players can either propose or abstain from building a shared resource. At least one person must propose in order for the resource to be built, but neither wants to contribute the associated edge cost. They must then trade off the possible benefi?t of gaining the resource for free against the chance that neither get anything at all. Contexts include trade deals between countries and interest signaling in interpersonal relationships.

We ?first study two extensions to the game: the EBG on a continuous strategy set where players can propose from a continuum of strength (as opposed to just proposing

or abstaining), and the EBG with multiple players on the same resource. Even with continuous strategy sets, the EBG is a discontinuous game, and we ?find discontinuous

Nash equilibrium distributions for different game scenarios. These discontinuous equilibria take the following general form: Propose with a ?fixed probability, and with

the remaining probability draw from some parameterized probability distribution. In the multiplayer game, we fi?nd that proposal probability drops rapidly with an increase

in the number of players (at low edge-cost), and we fi?nd that the expected utility when playing a mixed-strategy Nash equilibrium is worse than the two-player case, but the reverse holding true for a particular correlated equilibrium.

Next, we play the game on a graph/network, under both simultaneous- and sequential-play rules. Here, we allow nodes to have different utility functions that

depend on graph topology. We explore the general intractability of computing Nash and correlated equilibria of the simultaneous EBG on networks, and present some special cases of the problem where Nash and correlated equilibria can be efficiently found. Correlated equilibria can even be optimized over when the simultaneous game

on networks is played on a tree with bounded degree, and when node utilities only depend on a local subgraph with a particular radius.

We then run simulations of the sequential game, where pairs of players on the network take turns playing, and study how the parameterization of node utility functions affects output metrics. We also introduce a novel submodular network measure that we use in the sequential game simulations.

Relatedly, we introduce a combinatorial problem on attacking defended networks, the Probe-and-Attack Problem (PAP). In the PAP, nodes confer protection from

attacks to all its neighbors. An attacker must decide how to allocate a budget between probing nodes to disable this protection, and attacking unprotected nodes to extract

direct utility. We show it is NP-hard, produce upper- and lower-bounds that are found by solving a (much more tractable) knapsack problem, and present efficient

heuristics or the problem, testing the heuristics on simulated networks.