Maximal Cooperation in Repeated Games on Social Networks
Authors: Catherine Moon, Vincent Conitzer
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this paper, we consider games with cooperation and defection. We prove that there exists a unique maximal set of forevercooperating agents in equilibrium and give an efficient algorithm for computing it. We then evaluate this algorithm on random graphs and find experimentally that there appears to be a phase transition between cooperation everywhere and defection everywhere, based on the value of cooperation and the discount factor. Finally, we provide a condition for when the equilibrium found is credible, in the sense that agents are in fact motivated to punish deviating agents. We find that this condition always holds in our experiments, provided the graphs are sufficiently large. |
| Researcher Affiliation | Academia | Catherine Moon Duke University Durham, NC 27708, USA csm17@duke.edu Vincent Conitzer Duke University Durham, NC 27708, USA conitzer@cs.duke.edu |
| Pseudocode | No | Algorithm 1 is described in text: "Initialize Scurrent to include all agents. Then, in each iteration, check, for each i S, whether the incentive constraint holds for i relative to Scurrent. Remove those i for which it does not hold from Scurrent. Repeat this until convergence; then, return Scurrent." This is a description rather than a formally structured pseudocode block labeled as such. |
| Open Source Code | No | The paper does not provide any specific statement or link regarding the availability of its source code. |
| Open Datasets | No | The paper does not use a publicly available or open dataset. Instead, it generates random graphs based on two models (Erdos-Renyi and Barabasi-Albert) for its experimental analysis: "We generate random graphs based on two models: the Erd os-R enyi random graph model (ER) and the Barab asi Albert preferential-attachment random graph model (PA)..." |
| Dataset Splits | No | The paper conducts experimental analysis on generated random graphs but does not mention specific training, validation, or test dataset splits for model reproduction. The experiments evaluate the algorithm on these generated graphs. |
| Hardware Specification | No | The paper does not specify any hardware details (e.g., CPU, GPU models, memory) used for running the experiments. It only mentions experimental analysis on random graphs. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers needed to replicate the experiments. |
| Experiment Setup | Yes | For our experimental analysis, we make the following additional assumptions on the cost and benefit structure. First, i s cost of cooperation is proportional to the number of outgoing edges i initially has: κi = P i S:(i,j) E 1, normalizing the per-edge cost to 1. Also, we assume a constant benefit to having an incoming edge, that is, βj,i = β for all (j, i) E. We generate random graphs based on two models: the Erd os-R enyi random graph model (ER) and the Barab asi Albert preferential-attachment random graph model (PA)... The ER model requires n, the number of nodes, and p, the probability of a directed edge between two nodes. The PA model requires n, the number of nodes, e, the number of edges per node, and γ, a parameter determining the degree of preference... All the graphs presented in this paper are with p = 0.3, and with each point averaged over 100 graphs. |