StrivingForLegibility comments on Game Theory without Argmax [Part 2]

[StrivingForLegibility]

Edit: Cleo Nardo has confirmed that they intended $\prod _{i\in I}$ to mean the cartesian product of sets, the ordinary thing for that symbol to mean in that context. I misunderstood the semantics of what $B\left(x\right)$ was intended to represent. I’ve updated my implementation to use the intended cartesian product when calculating the best response function, the rest of this comment is my initial (wrong) interpretation of $B\left(x\right)$.

I needed to go back to one of the papers cited in Part 1 to understand what that $\prod _{i\in I}$ was doing in that expression. I found the answer in A Generalization of Nash’s Theorem with Higher-Order Functionals. I’m going to do my best to paraphrase Hedges’ notation into Cleo’s notation, to avoid confusion.

TLDR: $B\left(x\right)$ is picking out the set of option-profiles $P\left(X\right)$ that are simultaneously best-responses by all players to that option-profile $x$. It does this by considering all of the option-profiles that can result by each player best-responding, then takes the intersection of those sets.

On page 6, Hedges defines the best response correspondence $B\in X\to P\left(X\right)$

$B\left(x\right)=\bigcap _{i\in I}{B}_i\left(x\right)$

Where

$B_i\in X\to P\left(X\right)$

Hedges builds up the idea of Nash Equilibria using quantifiers rather than optimizers, (like $\text{max}$ rather than $\text{argmax}$), but I believe the approaches are equivalent. Unpacking $B:x\mapsto \prod _{i\in I}{\psi }_i(g\circ U_i(x\left)\right)$ from the inside out:

$U_i\left(x\right)\in X_i\to X$

$g\circ U_i\left(x\right)\in X_i\to R$

That makes $g\circ U_i(x$) a ${\psi }_i$-task. Since ${\psi }_i\in (X_i\to R)\to P\left(X_i\right)$, we know that ${\psi }_i(g\circ U_i(x\left)\right)\in P\left(X_i\right)$.

This is where I had to go looking through papers. What sort of product takes a set of best-responses from each player, relative to a given option-profile, and returns a set of option-profiles that are simultaneously regarded by each player as a best-response? I thought about just taking the Cartesian product of the sets, but that wouldn’t get us only the mutual best-responses.

Let’s call the way that each player maps option-profiles to best-responses $b_i\in X\to P\left(X_i\right)$. This is exactly the sets we want to take the product of:

$b_i\left(x\right)={\psi }_i(g\circ U_i(x\left)\right)$

Hedges introduces notation on page 3 to handle the operation of taking an option-profile, varying one player’s option, and leaving the rest the same. Paraphrasing, Hedges defines $x(i\mapsto \alpha )\in \prod _{j\in I}{X}_j$ by

$x(i\mapsto \alpha {)}_j=\{\begin{array}{cc}\alpha & \text{if}i=j\\ x_j& otherwise\end{array}$

You can read $x(i\mapsto \alpha )$ as “give me a new copy of $x$, where the $i$th entry has been set to the value $\alpha$.” Hedges uses this to define the deviation maps equivalently to the way Cleo did. $U_i:X\to (X_i\to X)$

$U_i\left(x\right)\left(\alpha \right)=x(i\mapsto \alpha )$

The correspondences $B_i\in X\to P\left(X\right)$ take as input an option profile, and returns the set of option-profiles which are player $i$’s optimal unilateral deviations from that option profile. To construct $B_i$ from $b_i$, we want to map $b_i\left(x\right)\in P\left(X_i\right)$ to the option-profiles which deviate from $x$ in those exact ways.

$B_i\left(x\right)=\left\{x\right(i\mapsto \alpha ):\alpha \in b_i(x\left)\right\}$

We can then use Hedges’ $B\left(x\right)=\bigcap _{i\in I}{B}_i\left(x\right)$ to get the best-response correspondence! We can unpack this to get a definition of $B$ using objects that Cleo defined, using that deviation notation from Hedges:

$B\left(x\right)=\bigcap _{i\in I}\left\{x\right(i\mapsto \alpha ):\alpha \in {\psi }_i(g\circ U_i(x\left)\right)\}$

Thank you Cleo for writing this article! This was my first introduction to Higher-Order Game Theory, and I wrote up an implementation in TypeScript to help me understand how all of the pieces fit together!

[rotatingpaguro]

I’m weirded out by this. To look at everything together, I write the original expression, and your expression rewritten using the OP’s notation:

Original: $B:x\mapsto \prod _{i\in I}{\psi }_i(g\circ U_i(x\left)\right)$

Yours: $\begin{array}{cc}B\left(x\right)& =\bigcap _{i\in I}\left\{x\right(i\mapsto \alpha ):\alpha \in {\psi }_i(g\circ U_i(x\left)\right)\}\\ & =\bigcap _{i\in I}{U}_i\left(x\right)\left({\psi }_i\right(g\circ U_i\left(x\right)\left)\right)\end{array}$

(I’m using the notation that a function applied to a set is the image of that set.)

So the big pi symbol stands for

${\prod }_{i\in I}{A}_i={\bigcap }_{i\in I}{U}_i\left(x\right)\left(A_i\right)$

So it’s not a standalone operator: it’s context-dependent because it pops out an implicit $x$. The OP otherwise gives the impression of a more functional mindset, so I suspect the OP may mean something different from your guess.

Other problem with your interpretation: it yields the empty set unless all agents consider doing nothing an option. The only possible non-empty output is $\left\{x\right\}$. Reason: each set you are intersecting contains tuples with all elements equal to the ones in $x$, but for one. So the intersection will necessarily only contain tuples with all elements equal to those in $x$.

[StrivingForLegibility]

Edit: Cleo Nardo has confirmed that they intended $\prod _{i\in I}$ to mean the cartesian product of sets, the ordinary thing for that symbol to mean in that context. I misunderstood the semantics of what $B\left(x\right)$ was intended to represent. I’ve updated my implementation to use the intended cartesian product when calculating the best response function, the rest of this comment is based on my initial (wrong) interpretation of $B\left(x\right)$.

I write the original expression, and your expression rewritten using the OP’s notation:

Original: $B:x\mapsto \prod _{i\in I}{\psi }_i(g\circ U_i(x\left)\right)$

Yours: $\begin{array}{cc}B\left(x\right)& =\bigcap _{i\in I}\left\{x\right(i\mapsto \alpha ):\alpha \in {\psi }_i(g\circ U_i(x\left)\right)\}\\ & =\bigcap _{i\in I}{U}_i\left(x\right)\left({\psi }_i\right(g\circ U_i\left(x\right)\left)\right)\end{array}$

(I’m using the notation that a function applied to a set is the image of that set.)

This is a totally clear and valid rewriting using that notation! My background is in programming and I spent a couple minutes trying to figure out how mathematicians write “apply this function to this set.”

I believe the way that $B\left(x\right)$ is being used is to find Nash equilibria, using Cleo’s definition 6.5:

Like before, the $\Psi$-nash equilibria of $g$ is the set of option-profiles $x\in X$ such that $x\in B\left(x\right)$.

These are going to be option-profiles where “not deviating” is considered optimal by every player simultaneously. I agree with your conclusion that this leads $B\left(x\right)$ to take on values that are either $\left\{\right\}$ or $\left\{x\right\}$. When $B\left(x\right)=\left\{\right\}$, this indicates that $x$ is not a Nash equilibrium. When $B\left(x\right)=\left\{x\right\}$, we know that $x$ is a Nash equilibrium.

[rotatingpaguro]

Oh I see now, $B$ just needs to work to pinpoint Nash equilibria, I did not make that connection.

But anyway, the reason I’m suspicious of your interpretation is not that your math is not correct, but that it makes the OP notation so unnatural. The unnatural things are:

1. $\prod$ being context-dependent.

2. $\prod$ not having its standard meaning.

3. $U_i$ used implicitly instead of explicitly, when later it takes on a more important role to change decision theory.

4. Using $x\in B\left(x\right)$ as condition without mentioning that already $B\left(x\right)\ne \varnothing ⟺x\text{is Nash}$ if $|I|\ge 2$.

So I guess I will stay in doubt until the OP confirms “yep I meant that”.

[Cleo Nardo]

$B\left(x\right)\ne \varnothing$ isn’t equivalent to $x$ being Nash.

Suppose Alice and Bob are playing prisoner’s dilemma. Then the best-response function of every option-profile is nonempty. But only one option-profile is nash.

$x\in B\left(x\right)$ is equivalent to $x$ being Nash.