Two Notions of Best Responsepost by Diffractor · 2018-05-26T17:14:19.000Z · score: 0 (0 votes) · LW · GW · None comments
In game theory, there are two different notions of "best response" at play. Causal best-response corresponds to standard game-theoretic reasoning, because it assumes that the joint probability distribution over everyone else's moves remains unchanged if one player changes their move. The second one, Evidential best-response, can model cases where the actions of the various players are not subjectively independent, such as Death in Damascus, Twin Prisoner's Dilemma, Troll Bridge, Newcomb, and Smoking Lesion, and will be useful to analyze the behavior of logical inductors in repeated games. This is just a quick rundown of the basic properties of these two notions of best response.
Let be the set of actions available to player 1. . Given a matrix , refers to the -th row vector of . Given some vector , is defined in the usual way.
Consider a joint probability distribution over the outcomes of every player other than player 1 and index the set of all outcomes by i. There are possible joint outcomes from everyone else.
This produces a vector in an -dimensional vector space. The superscript denotes that this is not a full joint probability distribution, as it overlooks the probabilities of player 1's actions.
Now, consider an matrix , where is a number in . This is the utility matrix.
An action is a causal best response by player 1 iff
Let be the set of probability vectors for which is a best response. This set is convex. Proof:
Select an arbitrary . By definition of being the best response for the two vectors and ,
By multiplying these equations by and , and adding them together, And then, by the distributive laws of matrix multiplication, we can move the scalars in, and pull out , to yield... And because was arbitrary, the result follows.
#Evidential Best Response
Consider a joint probability distribution over the outcomes of every player, and index the entries by i (for every other player), and j(for player 1).
This produces a vector in an -dimensional vector space (which it is convenient to view as an matrix ).
Now, consider the same utility matrix as before.
The condition for being a best response is now a bit more complicated, because of the possibility of all-0 rows in . This will be handled by lower and upper bounds on the expected utility of a 0-probability event.
If , then . If , then
Now, the condition for being a "best response" is as follows:
This condition of "best response" corresponds to there being some perturbation of by a nonstandard , such that expected utility conditional on all rows is now well-defined, and move doesn't have lower expected utility (which is now well-defined by the equation for nonzero probability actions) than any other row. This perturbation could be thought of as the expected utility of density-zero exploration into the action .
The set of joint probability distributions where is a best action, is not convex, although it is compact.
Technically, this definition of best response applies to any matrix with nonzero entries, even if they don't sum up to 1. This will be important to deal with logical inductors, when the prices on the various outcomes don't have exact coherence (although the logical inductor prices will limit to the subset of the -dimensional hypercube that corresponds to probability distributions)
A matrix is subjectively independent of player 1 when all the row vectors lie in a 1-dimensional subspace. This means that, conditional on any action with nonzero probability, the probability distribution on the moves of everyone else remains the same. If is subjectively independent of player 1, then there's a canonical choice of vector obtained by taking an arbitrary nonzero row vector and renormalizing it so it sums to 1. The causal best response will also be an evidential best response in this case. Subjective independence is the condition necessary for a causal best response to be a correct approximation.
Interestingly enough, a convex combination of subjectively independent joint probability distributions may not be subjectively independent.
Both nonconvexity of the set of best responses, and nonconvexity of subjectively independent distributions, will be proved, by exhibiting a case where there are two subjectively independent distributions where move 1 is a best response, and a 50/50 mixture of the two probability distributions is both not subjectively independent, and move 1 is not a best response. The example was inspired by the smoking lesion problem.
The utility matrix is
The probability matrix is
The probability matrix is
To tell a story, let's say that it is a game against a wizard, and on even-numbered turns, there is an 80% chance of him inflicting a curse on player 1, and on odd-numbered turns, there is a 50% chance of him inflicting a curse on player 1. Seperately, the player can eat a toad (or not) (row 1 and 2, respectively). Eating a toad diminishes the effectiveness of the curse, but the player would prefer not to eat the toad. On even-numbered turns, the best move is to eat the toad, so not eating the toad occurs with probability. ( in this case should be interpreted as a small real number, to show that this isn't just an issue with conditioning on probability 0 events) On odd-numbered turns, player 1 is indifferent between eating the toad or not, so the player does it with 50% probability. In both situations, eating the toad yields the same or higher expected utility than not doing so.
This is obviously not subjectively independent of player 1's actions, and furthermore, the expected utility of eating the toad is ~0.34, which is less than the expected utility of not eating the toad, which is ~0.5.
Comments sorted by top scores.