Fun with numbers for January 15, 2020

Infinites make for math fun

Link: https://twitter.com/3blue1brown/status/1215087264792887296

I did as GS suggested and figured out the solution myself. (That's the point of following recreational math accounts, after all.)

It wasn't difficult, since the behavior of a function $ f_n(x) = x^{x^{x\ldots}}$ where there are $n-1$ exponentiations, when $n \rightarrow \infty$ is likely to be divergent for any $x>1$. This was my intuition, and based on that intuition, I assumed there couldn't exist $x$ and $y$ such that $f_{\infty}(x) = 2$ and $f_{\infty}(y) = 4$. Therefore the premise is false and the reasoning fails because of that.

But I didn't prove it. I did play around with a spreadsheet to check the behavior of the function around $x=1$, since $f_n(1) =1$ for all $n$ and the functions are continuous in $x$. A simple spreadsheet shows the behaviors for $x$ between 0 and 1 and for $x$ above 1. The rows are increasing $n$, the relevant part is the diff-in-diff column, a discrete version of a second derivative w.r.t. $n$:

What these results (and several others, the point of a spreadsheet model being to play around with the numbers, or as a responsible adult would say it "do sensitivity analysis") show is that for $0 < x <  1$ the function is increasing and "concave," therefore most likely converging to a number in the [0,1] interval; for numbers above 1, the function is increasing and "convex," therefore most likely diverging to infinity.

Still not a proof, but confidence is high. (And confirmed later by the rest of the thread.)

True to my origins as a Prolog (and Lisp, occasionally) programmer, I feel compelled to write a formal definition of this function, thusly:

$\qquad f_1(x) = x;$
$\qquad f_n(x) = x^{f_{n-1}(x)} \quad\text{for $n>1$} $

As usual, recursions FTW!

Go beyond one-step thinking to understand executive pay

Scott Manley, whose space videos are among the most informative on YouTube, expressed a common complaint about executive severance pay, on the occasion of Boeing's change of the guard:

My response is the précis of why you have to pay outgoing executives significant severance: it's a signal to the incoming executives, not a reward to the outgoing executives.

(This was particularly obvious in the case of PG&E in California, which paid a lot to its executives in what most people thought scandalous and well-informed people recognized as a move to retain talent under circumstances when most top managers were considering outside options.)

The responses to SM's tweet contained a lot of misconceptions about executive-level, also called C-suite, management, and this one, which was a response to my response illustrates the three most important ones:

(As I try to be more positive, I'll be anonymizing tweets that I'm critiquing.)

Yet another Rotten Tomatoes calculation (Doctor Who)

Given these numbers, it's

5,872,182,639,638,860,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

times more likely that critics and audience use opposite criteria than the same criteria.

Never give up; never surrender!

An annoying mistake people make using game theory

There's a lot of confusion between actions and strategies, at least in the minds (and presentations and papers, sadly) of some analytical modelers.

In a game each agent $i$ has a set of actions $\mathcal{A}_i$. For example, in the prisoners' dilemma, the actions are {Defect,Cooperate}; in the matching pennies game they are {H,T}.

A strategy for player $i$, $\sigma_i$, can be a simple action, in the case of pure strategies. For example, the strategy for the prisoners' dilemma is to Defect always, a pure strategy. So in this very particular case, the observed action, say $A_i \in \mathcal{A}_i$ coincides with the strategy $\sigma_i$.

A strategy can be a distribution $\sigma_i(A_i) \in \Delta(\mathcal{A}_i)$ over actions $A_i \in \mathcal{A}_i$, which is the case with mixed strategies. The balanced matching pennies game has a unique Nash equilibrium where both players play H with 1/2 probability and T with 1/2 probability.

And this is where a lot of modelers get confused.

I've heard (and read, sadly) modelers say "we never see mixed strategies, so we are going to look at equilibria with pure strategies only." (Usually even this statement is wrong. What they are looking at are "equilibria" in which players are forced to play pure strategies, which is different. These are usually not equilibria at all: typically they have competitive best responses in mixed strategies that dominate the "equilibrium" one.)

Of course you don't see mixed strategies. You never see any strategy; all you can see are actions. What you see in pure strategies is an action that happens to coincide with the strategy. In the matching pennies game, any play is executed by drawing from the distribution an action; that is what you see, say H. There's still an underlying $\sigma_i(H) = \sigma_i(T)=1/2$, but it is not visible; it must be inferred from the structure of the game's payoffs.

And, of course, a strategy can be a distribution $\sigma_i(A_i|\mathcal{I}_i)$ over $\mathcal{A}_i$ that is a function of information set of player $i$ at the time of play, $\mathcal{I}_i$, which makes things even more complicated. And more error-prone.

Some times during my first game theory course I thought all the formalism was a bit pedantic. Then I met people who didn't learn game theory properly, and realized that the formalism is there for a reason.

It removes the confusion.

Factoring game and algorithmic game theory

(A vignette inspired by Ehud Kalai's talk at the Lens 2011 Conference.)

Consider the following sequential-move game:

1. Player 1 chooses an integer $n > 1$.
2. Player 2 chooses an integer $k > 1$.
3. Player 2 wins if $k$ is a prime factor of $n$; Player 1 wins if $k$ is not a prime factor of $n$.

The backward induction solution to this game is obvious: Player 2 picks $k$ such that it is a prime factor of $n$, and Player 1 picks any $n$, which is irrelevant because Player 2 always wins.

This game, created by Ben-Sasson, Kalai, and Kalai, called the Factoring Game, illustrates a problem with the concept of equilibrium: it assumes that Player 2 can solve a complex problem (integer factorization) in useful time.*

So that "because Player 2 always wins" boldface part above should really be preceded by "assuming that Player 2 has a quantum computer to run Shor's algorithm." In other words, in actual useful time the more likely event is that Player 1 wins (by picking a number that is the product of two very large primes, for example).

The Factoring Game exposes a problem with game-theoretic solutions to some strategic problems: they don't take into account computability or complexity. That is a problem for many real-world situations, like paid search and auction mechanism design.

There's a new-ish field at the intersection of economic game theory and computer science, algorithmic game theory. This field explicit models computation as part of the process of solving games. Something that we should keep our eyes open for, as it already has real world applications in search, mechanism design, and online auctions.

Game theory is really expanding its purview: modal logic, computational (simulated, numerical), algorithmic (computation-theoretic), and behavioral versions... good times.

Reference: E. Ben-Sasson, A. Kalai, and E. Kalai. "An approach  to bounded rationality." In Advances in Neural Information Processing, Volume 19, pages 145–152. MIT Press,  Cambridge, MA, 2006.

* This game actually only illustrates the problem of subgame-perfect Nash equilibrium, not all equilibria concepts. Hey, I had to take a ton of game theory, might as well use some of it to be pedantic here.