The idea is an elaboration of a comment I made previously.
Motivation: Improving our understanding of superrationality.
Topic: Investigate the following conjecture.
Consider two agents playing iterated prisoner’s dilemma (IPD) with geometric time discount. It is well known that, for sufficiently large discount parameters (11−γ≫0), essentially all outcomes of the normal form game become Nash equilibria (the folk theorem). In particular, cooperation can be achieved via the tit-for-tat strategy. However, defection is still a Nash equilibrium (and even a subgame perfect equilibrium).
Fix n1,n2∈N. Consider the following IPD variant: the first player is forced to play a strategy that can be represented by a finite state automaton of n1 states, and the second player is forced to play a strategy that can be represented by a finite state automaton of n2 states. For our purpose a “finite state automaton” consists of a set of states S, the transition mapping τ:S×{C,D}→S and the “action mapping” α:S→{C,D}. Here, τ tells you how to update your state after observing the opponent’s last action, and α tells you which action to take. Denote the resulting (normal form) game FIPD(n1,n2,γ), where γ is the time discount parameter.
Conjecture: If n1,n2≥2 then there are a functions T:(0,1)→(0,∞) and δ:(0,1)→(0,∞) s.t. the following conditions hold:
limγ→1T(γ)=0
limγ→1δ(γ)=0
Any thermodynamic equilibrium of FIPD(n1,n2,γ) of temperature T(γ) has the payoffs of CC up to δ(γ).
Strategies: You could take two approaches: theoretical research and experimental research.
For theoretical research, you would try to prove or disprove the conjecture. If the initial conjecture is too hard, you can try to find easier variants (such as n1=n2=2, or adding more constraints on the automaton). If you succeed proving the conjecture, you can go on to studying games other than prisoner’s dilemma (for example, do we always converge to Pareto efficiency?) If you succeed in disproving the conjecture, you can go on to look for variants that survive (for example, assume n1=n2 or that the finite state automatons must not have irreversible transitions).
To decompose the task I propose: (i) have each person in the team think of ideas how to approach this (ii) brainstorm everyone’s ideas together and select a subset of promising ideas (iii) distribute the promising ideas among people and/or take each promising idea and find multiple lemmas that different people can try proving.
Don’t forget to check whether the literature has adjacent results. This also helps decomposing: the literature survey can be assigned to a subset of the team, and/or different people can search for different keywords / read different papers.
For experimental research, you would code an algorithm that computes the thermodynamic equilibria, and see how the payoffs behave as a function of T and γ. Optimally, you would also provide a derivation of the error bounds on your results. To decompose the task, use the same strategy as in the theoretical case to come up with the algorithms and the code design. Afterwards, decompose it by having each person implement a segment of the code (pair programming is also an option).
It is also possible to go for theoretical and experimental simultaneously, by distributing among people and cross-fertilizing along the way.
The idea is an elaboration of a comment I made previously.
Motivation: Improving our understanding of superrationality.
Topic: Investigate the following conjecture.
Consider two agents playing iterated prisoner’s dilemma (IPD) with geometric time discount. It is well known that, for sufficiently large discount parameters (11−γ≫0), essentially all outcomes of the normal form game become Nash equilibria (the folk theorem). In particular, cooperation can be achieved via the tit-for-tat strategy. However, defection is still a Nash equilibrium (and even a subgame perfect equilibrium).
Fix n1,n2∈N. Consider the following IPD variant: the first player is forced to play a strategy that can be represented by a finite state automaton of n1 states, and the second player is forced to play a strategy that can be represented by a finite state automaton of n2 states. For our purpose a “finite state automaton” consists of a set of states S, the transition mapping τ:S×{C,D}→S and the “action mapping” α:S→{C,D}. Here, τ tells you how to update your state after observing the opponent’s last action, and α tells you which action to take. Denote the resulting (normal form) game FIPD(n1,n2,γ), where γ is the time discount parameter.
Conjecture: If n1,n2≥2 then there are a functions T:(0,1)→(0,∞) and δ:(0,1)→(0,∞) s.t. the following conditions hold:
limγ→1T(γ)=0
limγ→1δ(γ)=0
Any thermodynamic equilibrium of FIPD(n1,n2,γ) of temperature T(γ) has the payoffs of CC up to δ(γ).
Strategies: You could take two approaches: theoretical research and experimental research.
For theoretical research, you would try to prove or disprove the conjecture. If the initial conjecture is too hard, you can try to find easier variants (such as n1=n2=2, or adding more constraints on the automaton). If you succeed proving the conjecture, you can go on to studying games other than prisoner’s dilemma (for example, do we always converge to Pareto efficiency?) If you succeed in disproving the conjecture, you can go on to look for variants that survive (for example, assume n1=n2 or that the finite state automatons must not have irreversible transitions).
To decompose the task I propose: (i) have each person in the team think of ideas how to approach this (ii) brainstorm everyone’s ideas together and select a subset of promising ideas (iii) distribute the promising ideas among people and/or take each promising idea and find multiple lemmas that different people can try proving.
Don’t forget to check whether the literature has adjacent results. This also helps decomposing: the literature survey can be assigned to a subset of the team, and/or different people can search for different keywords / read different papers.
For experimental research, you would code an algorithm that computes the thermodynamic equilibria, and see how the payoffs behave as a function of T and γ. Optimally, you would also provide a derivation of the error bounds on your results. To decompose the task, use the same strategy as in the theoretical case to come up with the algorithms and the code design. Afterwards, decompose it by having each person implement a segment of the code (pair programming is also an option).
It is also possible to go for theoretical and experimental simultaneously, by distributing among people and cross-fertilizing along the way.