Nash Equilibria

Followup To: An Introduction To Prisoner’s Dilemma
Part Of: Algorithmic Game Theory sequence
Content Summary: 500 words, 5 min read

Consider the following game:

Both spouses prefer the company of one another. In fact, they spent the evening together, they incur zero cost. However, if faced with a choice of waiting in an empty house vs. earning some overtime, they would prefer the latter twice as much.

We encode this game’s strategy-space as follows:

Nash Equilibria- Spouse Game

Recall our previous discussion of Pareto optimality and strategic dominance. There are myriad ways to think about games, why isolate those two properties, in particular? One reason to invent names is to construct a universal toolkit: non-trivial properties that exist in all games, and amenable to our analyses.

Pareto optimality makes an appearance in the above game (H, H). But strategic dominance does not. Take a moment to convince yourself this is true.

Since strategic dominance is too strong to be a universal property, we might relax it. What happens when we encode regret? That is, what does the Spousal Game look like after we consider cases when a player wishes she had made a different choice?

Nash Equilibria- Regret

Arrows represent regret.

  • In bottom-left cell, Spouse A wishes she had worked (purple arrow right) but Spouse B wishes he had gone home (orange arrow up).
  • In top-right cell, we see an entirely symmetric expression of mutual regret.
  • In the remaining cells, neither spouse can do better by individually changing their strategy.

Let us view Prisoner’s Dilemma from the same lens.

Nash Equilibria- PD Regret

These arrows have a peculiar pattern. Why? Because of strategic dominance!

We can explain strategic dominance in terms of regret. That is, if a player’s regrets are all in the same direction, then that player is subject to strategic dominance.

Does regret belong in our universal toolbox? No. Regret by itself is rather uninteresting: every game with non-trivial utilities comprises myriad regrets.

We need a stronger property. How about games containing outcomes with no regret? Call such outcomes Nash equilibrium.

Does every game have Nash equilibria?

  • Prisoner’s Dilemma has one: (D, D)
  • Spousal Game has two: (H, H) and (W, W)

Perhaps no game fail to have this peculiar creature..

Conjecture 1: Every game with a finite number of players and strategies has at least one Nash equilibrium.

Time to search for counter-examples! Consider the game Rock-Paper-Scissors. Here’s how it looks to a game theorist:

Nash Equilibrium- Rock-Paper-Scissors

Crucially, every node has at least one arrow leaving it. Rock/Paper/Scissors has no equilibrium! We have thus disproven Conjecture 1. What now?

In addition to the absence of Nash equilibria, this game is interesting in another sense. It turns out that having a deterministic strategy in Rock/Paper/Scissors is a bad idea.  In fact, machines can reliable beat people at Rock/Paper/Scissors by exploiting patterns in human gameplay.

What happens when we expand our notion of game to incorporate non-deterministic strategies. The best mixed strategy a player can adopt is [⅓ ⅓ ⅓]; that is where each choice is randomly selected with probability 0.33.

While hard to visualize, it is easy to intuitively grasp the existence of a new equilibrium. If each player adopts [⅓ ⅓ ⅓], neither will experience regret! Thus we can safely repair our Conjecture:

Conjecture 2. Every game with a finite number of players and strategies has at least one Nash equilibrium if mixed strategies are allowed.

It turns out that Conjecture 2 is entirely correct. In fact, its correctness is one of the most significant results in all of game theory.

Overfitting: Failure Mode of Meat Science

Followup To: [Data Partitioning: How To Repair Explanation]

If I have seen a little further, it is by standing on the shoulders of giants
– Isaac Newton

Table Of Contents

  • Context
  • The Optimization Level Of Science
  • The Fruits Of Science
  • Translation Proxy Lag
  • Cheap Explanations
  • Failure Mode of Meat Science
  • Takeaways

Context

Last time, we learned two things:

  1. Explainers who solely optimize against prediction error are in a state of sin.
  2. Data partitions immunize abductive processes against overfitting.

Today, we will apply these results to human scientific processes, or to what I will affectionately call meat science.

The Optimization Level Of Science

Nietzsche captures the reputation of science well:

Science is flourishing today and her good conscience is written all over her face, while the level to which all modern philosophy has gradually sunk… philosophy today, invites mistrust and displeasure, if not mockery and pity. It is reduced to “theory of knowledge”… how could such a philosophy dominate? … The scope and the tower-building of the sciences has grown to be enormous, and with this also the probability that the philosopher grows weary while still learning….

Attempts to ground such sentiments in something rigorous exceeds the scope of this post. Today, we simply accept that science is particularly epistemically productive. But let us move beyond the cheerleading, and ask ourselves why this is so.

If I were to hand over a map of our specie’s cognitive architecture to an alien species, I would expect them to predict demagogues much more easily than the discovery of the Higg’s Boson. The simple truth is that our minds are flawed: we are born with clumsy inference machinery. How then is epistemic productivity possible?

The success of science has been said to derive from the scientific method:

Overfitting- Scientific Method

But does the scientific method lend itself to the debiasing of the human animal? I argue it does not. Tribalism in scientific communities, for example, doesn’t seem particularly muted compared to other realms of human experience. Further, in his classic text The Structure of Scientific Revolutions, Thomas Kuhn showed that scientific revolutions emerge from strong, extra-rational motives. In his view, the nature of paradigm shifts is a bit like mystical religious experience: deeply personal, and difficult to verbalize.

I like to imagine science as a socio-historical process. Individuals and even sub-communities within its disciplines may fail to track what is Really There, but communities on the whole tend to move towards this direction. As Max Planck once observed:

A scientific truth does not triumph by convincing its opponents and making them see the light, but rather because its opponents eventually die and a new generation grows up that is familiar with it.

The question of how the scientific method facilitates socio-historical truth-tracking is, I believe, unsolved. But all I must do today, is flag the optimization level of science. If science organically debiases our species at the socio-historical level, there is much room for improvement. If cognitive science can forge new debiasing weapons, we will become increasingly able to transcend ourselves, able to move faster than science.

The Fruits Of Science

Consider again the following:

Overfitting- Newton Seen Further Quote

This meme is sticky, and signals humility… but it also frames a crisis.

The shoulders keep growing taller.

Because of the accretive nature of science, our collective knowledge far outpaces our cognitive abilities. Even if the controversial Flynn effect is true and our collective IQ really is improving over time, the size of our databases would still outstrip the reach of our cognitive cone.

Various technologies have been invented that assuage this crisis. Curriculum compression is one of the older ones. That which was originally available as an anthology of journal articles is compressed into a review article, review articles compressed to graduate courses, graduate courses polished into undergraduate presentations. Consider how Newton would marvel at a present-day course in differential calculus: 300 years of mathematical research, successfully installed into an undergraduate’s semantic memory in a matter of weeks.

Curriculum compression is but one answer to our exploding knowledge base. Other implicit reactions include:

  1. the narrowing of research trajectories
  2. the fractionating of disciplines into the Ivory Achipellago
  3. research crowdsourcing (the de-popularization of the Lone Intellectual Warrior model)

In the years ahead, society seems geared to add two more solutions to our “bag of tricks”:

  1. the cognitive reform of education technology
  2. the mechanization of science

And yet, the shoulders keep growing taller…

Translation Proxy Lag

In Knowledge, an Empirical Sketch, I introduced measurement under the title of translation proxies. Why the strange name? To underscore the nature of measurement: forcibly relocating sensory phenomena from its “natural habitat” towards a signature that our bodies are equipped to sense. In this light, a translation proxy can be viewed as a kind of faucet, bringing novel forms of physical reality into the human umwelt.

But consider physics, where the “low-hanging fruit” translation proxies have already been built. You don’t see many physicists clamoring for new hand-held telescopes. Instead, you see them excited over ultra-high precision telescope mirrors, over particle colliders producing energies in the trillions of electronvolts. Such elaborate proxy technologies simply do not flow as quickly from the furnace of invention. Call this phenomenon data intake stagnation.

Not only are our proxy innovations becoming more infrequent, but they are also severely outpaced by our theoreticians. In physics, M theory (the generalization of string theory) posits entities at the 10^-34 m scale, but our current microscopes can only interrogate resolutions around the 10^-15 m scale. In neuroscience, connectome research programs seek to graph the nervous system at the neuronal level (10^-6 m), but most imaging technologies only support the millimeter (10^-3) range. Call this phenomenon translation proxy lag.

It will be decades, perhaps centuries, before our measurement technologies catch up.

Cheap Explanations

Let us bookmark translation proxy lag, and consider a different sort of problem.

Giant shoulders are not merely growing taller. They also render impotent evidence once vital to theoreticians. Let me appeal to a much-cited page from history, to illustrate.

During World War I, Sir Arthur Eddington was Secretary of the Royal Astronomical Society, which meant he was the first to receive a series of letters and papers from Willem de Sitter regarding Einstein’s theory of general relativity. […] He quickly became the chief supporter and expositor of relativity in Britain. […]

After the war, Eddington travelled to the island of Príncipe near Africa to watch the solar eclipse of 29 May 1919. During the eclipse, he took pictures of the stars in the region around the Sun. According to the theory of general relativity, stars with light rays that passed near the Sun would appear to have been slightly shifted because their light had been curved by its gravitational field. This effect is noticeable only during eclipses, since otherwise the Sun’s brightness obscures the affected stars. Eddington showed that Newtonian gravitation could be interpreted to predict half the shift predicted by Einstein.

Eddington’s observations published the next year confirmed Einstein’s theory, and were hailed at the time as a conclusive proof of general relativity over the Newtonian model. The news was reported in newspapers all over the world as a major story:

Overfitting- NYT 1919

Two competing theories, two perfectly adequate explanations for everyday phenomena, one test to differentiate models. Here we see a curiosity: scientists place a high value on new data. Gravitational lensing constituted powerful confirmation because, as far as the model-creators knew, it could have been the other way.

Overfitting- Einstein vs. Newton

A nice, clean narrative. But consider what happens next. General relativity has begun to show its age: it is chronically incompatible with quantum mechanics. Many successors to general relativity have been created; let us call them Quantum Gravity Theory A, B, and C. Frustratingly, no discrepancies have been found between these theory-universes and our observed-universe.

Overfitting- Ad-Hoc Theories

How are multiple correct options possible? From a computational perspective, the phenomenon of multiple correct answers can be modeled with Solomonoff Induction. A less precise, philosophical precursor of the same morale can be found in underdetermination of theory.

But which theory wins? General relativity won via a solar eclipse generating evidence for gravitational lensing. But gravitational lensing is now “old hat”; so long as all theories accommodate its existence, it no longer wields theory-discriminating power. And – given the translation proxy lag crisis outlined above – it may take some time before our generation acquires its test, its analogue of a solar eclipse.

Can anything be done in the meantime? Is science capable of discriminating between QGT/A, QGT/B, and QGT/C in the absence of a clean novel prediction? When we choose to invest more of our lives in one particular theory above the others, are we doomed to make this choice by mere dint of our aesthetic cognitive modules, by a sense of social belonging, by noise in our yedasentiential signals?

Overfitting: Failure Mode of Meat Science

Bayesian inference teaches us that confidence is usefully modeled as a probabilistic thing. But stochastisity is not equiprobability: discriminability is a virtue. If science cannot provide it, let us cast about for ways to reform science.

Let us begin our search by considering the rhetoric of explanation. What does it mean for a hypothesis to be criticized as ad-hoc?

> Scientists are often skeptical of theories that rely on frequent, unsupported adjustments to sustain them. This is because, if a theorist so chooses, there is no limit to the number of ad hoc hypotheses that they could add. Thus the theory becomes more and more complex, but is never falsified. This is often at a cost to the theory’s predictive power, however. Ad hoc hypotheses are often characteristic of pseudoscientific subjects.

Do you recall how we motivated data partitioning? Do you yet recognize the stench of overfitting?

In fact, in my view, current scientific practice is a bit too uncomfortable with falsification. Karl Popper lionized falsifiability, and the result of his movement has been an increase in the operationalization and measurement-affinity of the scientific grammar. But the weaving together scientific abstractions and the particle soup, the dawning taboo around Not Even Wrong, came with baggage.

Logically, no number of positive outcomes at the level of experimental testing can confirm a scientific theory, but a single counterexample is logically decisive: it shows the theory, from which the implication is derived, to be false.

But compare this dictum with our result from machine learning, which suggests that perhaps small “falsifications” may be preferable to “getting everything right”:

Explainers who solely optimize against prediction error are in a state of sin.

In sum, we have reason to believe that overfitting is the pervasive illness of our meat science.

Takeaways

  • Science tracks truth not at the level of individual, but on a socio-historical scale. There is therefore room to move faster than science.
  • Science is accretive: the shoulders keep growing taller.
  • Due to constraints in measurement technology, data of a truly novel character has become increasingly difficult to acquire.
  • On meat science, as data transitions from “novel” to “known”, it loses its ability to wield theory-discriminating power.
  • Given these dual crises, and the philosophical commitments scientific communities have made against falsified hypotheses, science can be shown to suffer from overfitting.

Next time, we will explore applying the machine learning solution to overfitting – data partitioning – to meat science, and motivate the virtue of hiding data from ourselves. See you then!

 

Movement Forecast: Effective Availabilism

Table Of Contents

  • The Availability Cascade
  • Attentional Budget Ethics
  • Effective Availabilism
  • Why Quantification Matters
  • Cascade Reform Technologies
  • Takeaways

The Availability Cascade

The following questions pop up in my Facebook feed all the time.

Why is mental illness, addiction, and suicide only talked about when somebody famous succumbs to their demons?

Why do we only talk about gun control when there is a school shooting?

What is the shape of your answer? Mine begins with a hard look at the nature of attention.

Attention is a lens by which our selves perceive the world. The experience of attention is conscious. However, the control of attention – where it lands, how long it persists – is preconscious. People rarely think to themselves: “now seems an optimal time to think about gun control”. No, the topic of gun control simply appears.

When we pay attention to attention, its flaws become visible. Let me sketch two.

  1. The preconscious control of attention is famously vulnerable to a wide suite of dysrationalia. Like transposons parasitizing your DNA, beliefs parasitize your semantic memory by latching onto your preconscious attention-control software. This is why Evans-Pritchard was so astonished in his anthropological survey of Zande mysticism. This is why your typical cult follower is pathologically unable to pay attention to a certain set of considerations. The first flaw of the attentional lens is that it is a biasing attractor.
  2. Your unconscious mind is subject to the following computational principle: what you see is all there is. This brings us the availability heuristic, the cognitive shortcut your brain uses to travel from “this was brought to mind easily” to “this must be important”. The attentional lens is that the medium distorts its contents. This is nicely summed up in the proverb, “nothing in life is as important as you think it is, while you are thinking about it.” The second flaw of the attentional lens is that bound in a positive feedback loop to memory (“that which I can recall easily, must be important, leads me to discuss more, is something I recall even more easily”).

My treatment of this positive feedback loop was at the level of individual. But that same mechanism must also promote failures at the level of social network. The second flaw writ large – the rippling eddies of attentional currents (as captured by services like Google News) – are known as availability cascades. And thus we have provided a cognitive reason why our social atmosphere disproportionately discusses gun control when school shootings appear in the news.

In electrical engineering, positive feedback typically produces runaway effects: a circuit “hits the rails” (draws maximum current from its power source). What prevents human cognition from doing likewise, from becoming so fixated on one particular memory-attention loop that it cannot escape? Why don’t we spend our days and our nights dreaming of soft drinks, fast food, pharmaceuticals? I would appeal to human boredom as a natural barrier to such a runaway effect.

Attentional Budget Ethics

We have managed to rise above the minutia, and construct a model of political discourse. Turn now to ethics. How should attention be distributed? When is the right time to discuss gun control, to study health care reform, to get clear on border control priorities?

The response profile of such a question is too diverse to treat here, but I would venture most approaches share two principles of attentional budgets:

  1. The Systemic Failure Principle. If a system performance fails to meet some arbitrary criteria of success, that would be an argument for increasing its attentional budget. For example, perhaps the skyrocketing costs of health care would seem to call for more attention than other, relatively more healthy, sectors of public life.
  2. The Low Hanging Fruit Principle. If attention is likely to produce meaningful results, that would be an argument for increasing its attentional budget. For example, perhaps not much benefit would come from a national conversation about improving our cryptographic approaches to e-commerce.

Despite how shockingly agreeable these principles are, I have a feeling that different political parties may yet disagree. In a two party system, for example, you can imagine competing attentional budgets as follows:

Attentional Budgets

Interpret “attentional resources” in a straightforward (measurement-affine) way: let it represent the number of hours devoted to public discussion.

This model of attentional budgets requires a bit more TLC. Research-guiding questions might include:

  • How ought we model overlapping topics?
  • Should budget space be afforded for future topics, topics not yet conceived?
  • Could there be circumstances to justify zero attention allocation?
  • Is it advisable to leave “attentional budget creation” topics out of the budget?
  • How might this model be extended to accomodate time-dependent, diachronic budgeting?

Effective Availibilism

Let us now pull together a vision of how to transcend the attentional cascade.

In our present condition, even very intelligent commentators must resort to the following excuse of a thought: “I have a vague sense that our society is spending too much time on X. Perhaps we shouldn’t talk about it anymore”.

In our envisioned condition, our best political minds would be able to construct the following chain of reasoning: “This year, our society has spent three times more time discussing gun control than discussing energy independence. My attentional budget prescribes this ratio to be closer to 1:1. Let us think of ways to constrain these incessant gun-control availability cascades.”

In other words, I am prophesying the emergence of an effective availabilism movement, in ways analogous to effective altruism. Effective availabilist groups would, I presume, primarily draw from neuropolitical movements more generally.

Notice how effective availabilism relies on, and comes after, of publically-available psychometric data. And this is typical: normative movements often follow innovations in descriptive technology.

Why Quantification Matters

Policy discussions influence votes which affect lives. Despite the obvious need for constructive discourse, a frustrating amount of political exchanges are content-starved. I perceive two potential solutions for this failure of our democracy:

  1. Politics is a mind-killer. By dint of our evolutionary origins, our brains do not natively excel at political reasoning. Group boundaries matter more than analyses, arguments are soldiers. But these are epistemic failure modes. Policy debates should not appear one-sided. Movements to establish the cognitive redemption of politics are already underway. See, for example, Jonathon Haidt’s http://www.civilpolitics.org/ (“educating the public on evidence-based methods for improving inter-group civility”)
  2. Greasing policy discussions with data would facilitate progress. One of my favorite illustrations of this effect is biofeedback: if you give a human being a graphical representation of her pulse, the additional data augments the brains ability to reason – biofeedback patients are even able to catch their breath faster. In the same way, improving our data streams gives hope of transcending formerly-intractable social debates.

The effective availabilism movement could, in my view, accelerate this second pathway.

Cascade Reform Technologies

It seems clear that availability cascades are susceptible to abuse. Many advertisers and political campaigns don’t execute an aggregated optimization across our national attentional profile. Instead, they simply run a maximization algorithm on their topic of interest (“think about my opponent’s scandal!”).

With modern-day technology (polls, trending Twitter tags, motive abduction, self-monitoring), noticing attentional budget failures can be tricky. With the above technology in place, even subtle attentional budget failures will be easily detectable. We have increased our supply of failures, but how might effective availabilists increase demand (open vectors of reform towards availability cascade failure modes)?

The first, obvious, pathway is to use the same tool – attentional cascades – to counterbalance. If gun control is getting too much attention, effective availabilists will strive to push social media towards a discussion of e.g., campaign finance reform. They could, further, use psychometric data to evaluate whether they have overshot (SuperPACs are now too interesting), and to adjust as necessary.

Other pathways towards reform might be empirically-precise amplification of boredom circuits. Recruit the influential to promote the message that “this topic has been talked to death” could work; as could the targeted use of satire.

Takeaways

  • Pay more attention to the quiet whispers of your mind. “Haven’t I heard about this enough” represents an undiscovered political movement.
  • Social discourse is laced with the rippling tides of availability cascades, and are at present left to their mercy.
  • As hard psychometric data makes its way towards public accessibility, a market of normative attentional budgets will arise.
  • The business of pushing current attentional profiles towards normative budgets will become the impetus of effective availabilism movements.
  • A cottage industry of cognitive technologies to achieve these ends will thereafter crystallize and mature.

Attentional Budgets Usage (1)