From Jessica’s earlier post about conditional oracles, the question was asked: what is the equilibrium concept for games with more than one COEDT agent?
This post will (partially) answer that question, and provide a link to a tool to visualize 2-player 2-move COEDT equilibria sets.
To begin with, we will review how conditional oracles work. A conditional oracle is a mapping from M4→{0,1} (where M is some set of finitely many probabilistic oracle machines). A conditional oracle distribution is a probability distribution over conditional oracles. A conditional oracle distribution Q weakly leads to Q′, if
From the last post, all reflective conditional oracle distributions weakly lead to themselves.
Two things must be noted. First, the space that the equilibrium set lies in is actually correlated strategy space (a probability distribution over all joint outcomes, which in a 2-player 2-move game, is a tetrahedron). This is because the same oracle is selected from the oracle distribution for all the algorithms to use, which opens the door to correlated outcomes, instead of both players independently drawing an oracle from the oracle distribution. Second, the full concept of an equilibrium produced by a reflective COD (in the sense of a necessary and sufficient condition) is difficult to characterize, because it involves a bunch of fiddly details of the utilities of various probability-zero actions and whether it is possible to limit to them in the appropriate way. Therefore, the following definition doesn’t characterize all COEDT equilibria, just the fully-mixed ones that lie in the interior of the space instead of on a boundary (because that corresponds to having no outcomes occur with probability zero).
Let Pi be the i‘th player, Ui be the utility function of the i‘th player, Si be the strategy set of the i‘th player, S=∏i∈ISi be the set of outcomes, si be the move the i’th player plays as dictated by some s∈S, and Δ be a probability distribution over S.
Definition 1: A fully-mixed conditional equilibria is a probability distribution Δ with nonzero probability over all s∈S, s.t.
∀i∀j,j′∈Si:Es∼Δ(Ui|si=j)=Es∼Δ(Ui|si=j′)
In short, all players are indifferent between all of the moves that they could play.
Theorem 1:All fully mixed conditional equilibria in a game have a reflective conditional oracle distribution which results in the equilibrium being played.
The proof will be deferred to the end, along with Theorem 2:
Theorem 2:All conditional oracle distributions which result in nonzero probability for all outcomes, when used, which aren’t fully-mixed conditional equilibria, aren’t reflective.
Due to these theorems, in the 2-player 2-move case, all conditional equilibria except for some points on the boundary may be found by plotting an “indifference surface” (where a player is indifferent between both moves) for both players in the unit tetrahedron, and the intersection of the indifference surfaces in the interior of the tetrahedron is the set of fully-mixed conditional equilibria.
Adam Scherlis has kindly coded a tool to do this, using the Wolfram CDF player. The .cdf file is here.
Now for pictures.
This is Prisoner’s Dilemma. Both D,D and C,C are possible equilibria.
This is Chicken. There is a line of possible equilibria where both players get 4 utility in expectation. The two swerve/straight outcomes are also possible equilibria, because there are points arbitrarily close to them where the players pick swerve and straight, so there is a sequence of oracles which limit to swerve/straight, so the distribution Q which corresponds to swerve/straight lies in StepClosure(Q). This is an instance of disconnected points on the boundary which are produced by reflective conditional oracle distributions, which aren’t fully-mixed, so they aren’t an instance of the equilibrium concept that we defined. Note that the intuitively desirable outcome where both players go straight with 10% probability to get an expected utility of 4.05 is not an equilibrium, despite being the optimal strategy if you know your opponent will select the same probability distribution over moves as you, because it incentivizes both players to go straight if they know that the other player plays that strategy, and so isn’t stable.
This is Stag Hunt. Again, there are many equilibria where both players earn 1 utility in expectation, and a disconnected equilibrium point where both players cooperate on hunting the stag.
Theorem 1 Proof:
For all outcomes, there is an oracle O that produces it when used, by mapping the appropriate queries made by all the players to 1 or 0, respectively. Therefore, all fully-mixed distributions over outcomes have fully-mixed oracle distributions which produce that distribution when used. Given a fully-mixed distribution Δ, let Q be an arbitrary fully-mixed oracle distribution which produces it. Assume the implementation of COEDT where 1 means to take an action a and 0 means to defer to a COEDT algorithm that chooses among the action set without action a. COEDTi,j is the j’th instance in this chain, for player i.(to implement choice among more than two actions)
Because all oracle queries are of the form (Ui,COEDTi,j,Ui,1−COEDTi,j), by starting with the final COEDT algorithm in the chain, because expected utility is the same for both actions (by Δ being a fully-mixed conditional equilibrium), there is no constraint on the oracle distribution. Working backward from the maximum j to 1, for all the COEDT algorithms, because expected utility is the same for taking an action and deferring, there is no constraint on the oracle distribution produced.
Because Q produces no constraints on what Q′ must be, Q weakly leads to all Q′, and in particular, Q weakly leads to Q. By the definition of StepClosure from the previous post, and Q being fully-mixed, Q∈StepClosure(Q)⊆StepHull(Q), so Q is a reflective conditional oracle distribution.
Theorem 2 Proof:
As before, given a fully-mixed distribution Δ, select an arbitrary Q which produces it. By the same reasoning as before (backwards induction), when we get to the first action with higher or lower expected utility than the other actions that have been seen so far, due to the difference in expected utility, we get a constraint on Q′, namely that PQ′(O(Ui,COEDTi,j,Ui,1−COEDTi,j)=1)=1, or PQ′(O(Ui,COEDTi,j,Ui,1−COEDTi,j)=0)=1. Because Q has some of its probability mass composed of oracles which permit later actions to be taken (because Δ is fully-mixed) , it violates this condition, so Q does not weakly lead to itself. All reflective Q weakly lead to themselves, from the previous post, so Q cannot be reflective.
COEDT Equilibria in Games
From Jessica’s earlier post about conditional oracles, the question was asked: what is the equilibrium concept for games with more than one COEDT agent?
This post will (partially) answer that question, and provide a link to a tool to visualize 2-player 2-move COEDT equilibria sets.
To begin with, we will review how conditional oracles work. A conditional oracle is a mapping from M4→{0,1} (where M is some set of finitely many probabilistic oracle machines). A conditional oracle distribution is a probability distribution over conditional oracles. A conditional oracle distribution Q weakly leads to Q′, if
PQ(mO1=1∧nO1)PQ(nO2=1)>PQ(mO2=1∧nO2)PQ(nO1=1)→PQ′(O(m1,n1,m2,n2)=1)=1
PQ(mO1=1∧nO1)PQ(nO2=1)<PQ(mO2=1∧nO2)PQ(nO1=1)→PQ′(O(m1,n1,m2,n2)=0)=1
From the last post, all reflective conditional oracle distributions weakly lead to themselves.
Two things must be noted. First, the space that the equilibrium set lies in is actually correlated strategy space (a probability distribution over all joint outcomes, which in a 2-player 2-move game, is a tetrahedron). This is because the same oracle is selected from the oracle distribution for all the algorithms to use, which opens the door to correlated outcomes, instead of both players independently drawing an oracle from the oracle distribution. Second, the full concept of an equilibrium produced by a reflective COD (in the sense of a necessary and sufficient condition) is difficult to characterize, because it involves a bunch of fiddly details of the utilities of various probability-zero actions and whether it is possible to limit to them in the appropriate way. Therefore, the following definition doesn’t characterize all COEDT equilibria, just the fully-mixed ones that lie in the interior of the space instead of on a boundary (because that corresponds to having no outcomes occur with probability zero).
Let Pi be the i‘th player, Ui be the utility function of the i‘th player, Si be the strategy set of the i‘th player, S=∏i∈ISi be the set of outcomes, si be the move the i’th player plays as dictated by some s∈S, and Δ be a probability distribution over S.
Definition 1: A fully-mixed conditional equilibria is a probability distribution Δ with nonzero probability over all s∈S, s.t.
∀i∀j,j′∈Si:Es∼Δ(Ui|si=j)=Es∼Δ(Ui|si=j′)
In short, all players are indifferent between all of the moves that they could play.
Theorem 1: All fully mixed conditional equilibria in a game have a reflective conditional oracle distribution which results in the equilibrium being played.
The proof will be deferred to the end, along with Theorem 2:
Theorem 2: All conditional oracle distributions which result in nonzero probability for all outcomes, when used, which aren’t fully-mixed conditional equilibria, aren’t reflective.
Due to these theorems, in the 2-player 2-move case, all conditional equilibria except for some points on the boundary may be found by plotting an “indifference surface” (where a player is indifferent between both moves) for both players in the unit tetrahedron, and the intersection of the indifference surfaces in the interior of the tetrahedron is the set of fully-mixed conditional equilibria.
Adam Scherlis has kindly coded a tool to do this, using the Wolfram CDF player. The .cdf file is here.
Now for pictures.
This is Prisoner’s Dilemma. Both D,D and C,C are possible equilibria.
This is Chicken. There is a line of possible equilibria where both players get 4 utility in expectation. The two swerve/straight outcomes are also possible equilibria, because there are points arbitrarily close to them where the players pick swerve and straight, so there is a sequence of oracles which limit to swerve/straight, so the distribution Q which corresponds to swerve/straight lies in StepClosure(Q). This is an instance of disconnected points on the boundary which are produced by reflective conditional oracle distributions, which aren’t fully-mixed, so they aren’t an instance of the equilibrium concept that we defined. Note that the intuitively desirable outcome where both players go straight with 10% probability to get an expected utility of 4.05 is not an equilibrium, despite being the optimal strategy if you know your opponent will select the same probability distribution over moves as you, because it incentivizes both players to go straight if they know that the other player plays that strategy, and so isn’t stable.
This is Stag Hunt. Again, there are many equilibria where both players earn 1 utility in expectation, and a disconnected equilibrium point where both players cooperate on hunting the stag.
Theorem 1 Proof:
For all outcomes, there is an oracle O that produces it when used, by mapping the appropriate queries made by all the players to 1 or 0, respectively. Therefore, all fully-mixed distributions over outcomes have fully-mixed oracle distributions which produce that distribution when used. Given a fully-mixed distribution Δ, let Q be an arbitrary fully-mixed oracle distribution which produces it. Assume the implementation of COEDT where 1 means to take an action a and 0 means to defer to a COEDT algorithm that chooses among the action set without action a. COEDTi,j is the j’th instance in this chain, for player i.(to implement choice among more than two actions)
Because all oracle queries are of the form (Ui,COEDTi,j,Ui,1−COEDTi,j), by starting with the final COEDT algorithm in the chain, because expected utility is the same for both actions (by Δ being a fully-mixed conditional equilibrium), there is no constraint on the oracle distribution. Working backward from the maximum j to 1, for all the COEDT algorithms, because expected utility is the same for taking an action and deferring, there is no constraint on the oracle distribution produced.
Because Q produces no constraints on what Q′ must be, Q weakly leads to all Q′, and in particular, Q weakly leads to Q. By the definition of StepClosure from the previous post, and Q being fully-mixed, Q∈StepClosure(Q)⊆StepHull(Q), so Q is a reflective conditional oracle distribution.
Theorem 2 Proof:
As before, given a fully-mixed distribution Δ, select an arbitrary Q which produces it. By the same reasoning as before (backwards induction), when we get to the first action with higher or lower expected utility than the other actions that have been seen so far, due to the difference in expected utility, we get a constraint on Q′, namely that PQ′(O(Ui,COEDTi,j,Ui,1−COEDTi,j)=1)=1, or PQ′(O(Ui,COEDTi,j,Ui,1−COEDTi,j)=0)=1. Because Q has some of its probability mass composed of oracles which permit later actions to be taken (because Δ is fully-mixed) , it violates this condition, so Q does not weakly lead to itself. All reflective Q weakly lead to themselves, from the previous post, so Q cannot be reflective.