Quotulatiousness

November 16, 2024

The 1980 Iterated Prisoner’s Dilemma Tournament

Filed under: Gaming, History — Tags: , , — Nicholas @ 03:00

At Astral Codex Ten, Scott Alexander starts a post titled “The Early Christian Strategy” with some relevant back-story (fore-story?) involving game theory and the famous Prisoner’s Dilemma:

An example prisoner’s dilemma payoff matrix drawn by CMG Lee using emojis from Wikimedia Commons.

In 1980, game theorist Robert Axelrod ran a famous Iterated Prisoner’s Dilemma Tournament.

He asked other game theorists to send in their best strategies in the form of “bots”, short pieces of code that took an opponent’s actions as input and returned one of the classic Prisoner’s Dilemma outputs of COOPERATE or DEFECT. For example, you might have a bot that COOPERATES a random 80% of the time, but DEFECTS against another bot that plays DEFECT more than 20% of the time, except on the last round, where it always DEFECTS, or if its opponent plays DEFECT in response to COOPERATE.

In the “tournament”, each bot “encountered” other bots at random for a hundred rounds of Prisoners’ Dilemma; after all the bots had finished their matches, the strategy with the highest total utility won.

To everyone’s surprise, the winner was a super-simple strategy called TIT-FOR-TAT:

  1. Always COOPERATE on the first move.
  2. Then do whatever your opponent did last round.

This was so boring that Axelrod sponsored a second tournament specifically for strategies that could displace TIT-FOR-TAT. When the dust cleared, TIT-FOR-TAT still won — although some strategies could beat it in head-to-head matches, they did worst against each other, and when all the points were added up TIT-FOR-TAT remained on top.

In certain situations, this strategy is dominated by a slight variant, TIT-FOR-TAT-WITH-FORGIVENESS. That is, in situations where a bot can “make mistakes” (eg “my finger slipped”), two copies of TIT-FOR-TAT can get stuck in an eternal DEFECT-DEFECT equilibrium against each other; the forgiveness-enabled version will try cooperating again after a while to see if its opponent follows. Otherwise, it’s still state-of-the-art.

The tournament became famous because – well, you can see how you can sort of round it off to morality. In a wide world of people trying every sort of con, the winning strategy is to be nice to people who help you out and punish people who hurt you. But in some situations, it’s also worth forgiving someone who harmed you once to see if they’ve become a better person. I find the occasional claims to have successfully grounded morality in self-interest to be facile, but you can at least see where they’re coming from here. And pragmatically, this is good, common-sense advice.

For example, compare it to one of the losers in Axelrod’s tournament. COOPERATE-BOT always cooperates. A world full of COOPERATE-BOTS would be near-utopian. But add a single instance of its evil twin, DEFECT-BOT, and it folds immediately. A smart human player, too, will easily defeat COOPERATE-BOT: the human will start by testing its boundaries, find that it has none, and play DEFECT thereafter (whereas a human playing against TIT-FOR-TAT would soon learn not to mess with it). Again, all of this seems natural and common-sensical. Infinitely-trusting people, who will always be nice to everyone no matter what, are easily exploited by the first sociopath to come around. You don’t want to be a sociopath yourself, but prudence dictates being less-than-infinitely nice, and reserving your good nature for people who deserve it.

Reality is more complicated than a game theory tournament. In Iterated Prisoners’ Dilemma, everyone can either benefit you or harm you an equal amount. In the real world, we have edge cases like poor people, who haven’t done anything evil but may not be able to reciprocate your generosity. Does TIT-FOR-TAT help the poor? Stand up for the downtrodden? Care for the sick? Domain error; the question never comes up.

Still, even if you can’t solve every moral problem, it’s at least suggestive that, in those domains where the question comes up, you should be TIT-FOR-TAT and not COOPERATE-BOT.

This is why I’m so fascinated by the early Christians. They played the doomed COOPERATE-BOT strategy and took over the world.

July 18, 2022

John von Neumann, The Man From The Future

Filed under: Books, History, Science — Tags: , , , , , — Nicholas @ 05:00

One of the readers of Scott Alexander’s Astral Codex Ten has contributed a review of The Man From The Future: The Visionary Life of John von Neumann by Ananyo Bhattacharya. This is one of perhaps a dozen or so anonymous reviews that Scott publishes every year with the readers voting for the best review and the names of the contributors withheld until after the voting is finished:

John von Neumann invented the digital computer. The fields of game theory and cellular automata. Important pieces of modern economics, set theory, and particle physics. A substantial part of the technology behind the atom and hydrogen bombs. Several whole fields of mathematics I hadn’t previously heard of, like “operator algebras”, “continuous geometry”, and “ergodic theory”.

The Man From The Future, by Ananyo Bhattacharya, touches on all these things. But you don’t read a von Neumann biography to learn more about the invention of ergodic theory. You read it to gawk at an extreme human specimen, maybe the smartest man who ever lived.

By age 6, he could multiply eight-digit numbers in his head. At the same age, he spoke conversational ancient Greek; later, he would add Latin, French, German, English, and Yiddish (sometimes joked about also speaking Spanish, but he would just put “el” before English words and add -o to the end). Rumor had it he memorized everything he ever read. A fellow mathematician once tried to test this by asking him to recite Tale Of Two Cities, and reported that “he immediately began to recite the first chapter and continued until asked to stop after about ten or fifteen minutes”.

A group of scientists encountered a problem that the computers of the day couldn’t handle, and asked von Neumann for advice on designing a new generation of computers that was up to the task. But:

    When the presentation was completed, he scribbled on a pad, stared so blankly that a RAND scientist later said he looked as if “his mind had slipped his face out of gear”, then said “Gentlemen, you do not need the computer. I have the answer.” While the scientists sat in stunned silence, Von Neumann reeled off the various steps which would provide the solution to the problem.

Do these sound a little too much like urban legends? The Tale Of Two Cities story comes straight from the mathematician involved — von Neumann’s friend Herman Goldstine, writing about his experience in The Computer From Pascal to von Neumann. The computer anecdote is of less certain provenance, quoted without attribution in a 1957 obituary in Life. But this is part of the fun of reading von Neumann biographies: figuring out what one can or can’t believe about a figure of such mythic proportions.

This is not really what Bhattacharya is here for. He does not entirely resist gawking. But he is at least as interested in giving us a tour of early 20th century mathematics, framed by the life of its most brilliant practitioner. The book devotes more pages to set theory than to von Neumann’s childhood, and spends more time on von Neumann’s formalization of quantum mechanics than on his first marriage (to be fair, so did von Neumann — hence the divorce).

Still, for those of us who never made their high school math tutors cry with joy at ever having met them (another von Neumann story, this one well-attested), the man himself is more of a draw than his ergodic theory. And there’s enough in The Man From The Future — and in some of the few hundred references it cites — to start to get a coherent picture.

November 1, 2018

QotD: Game theory

Filed under: Humour, Quotations, Science — Tags: , — Nicholas @ 01:00

“Guys,” he writes. “It’s time for some game theory.” Game theory, for the uninitiated, is a branch of mathematics that uses computational models to predict the behavior of human beings in potentially conflictual situations. It’s complex, involves a lot of formal logic and algebra, and is mostly useless. Game theory models human actions on the presumption that everyone is constantly trying to maximize their potential gain against everyone around them; this is why its most famous example concerns prisoners — isolated people, cut off from all the noncompetitive ties that constitute society. One of its most important theoreticians, John Nash, was also a paranoid schizophrenic, who believed himself to be the target of a vast Russian conspiracy.

Sam Kriss, “The Rise of the Alt-Center: Why did establishment liberals fall in love with a deranged Twitter thread? It’s time for some game theory”, Slate, 2016-12-16.

January 2, 2015

QotD: The co-ordination problem of pure Marxism

Filed under: Economics, History, Politics, Quotations — Tags: , , — Nicholas @ 01:00

… it is interesting to analyze Marx as groping toward something game theoretic. This comes across to me in some of his discussions of labor. Marx thinks all value is labor. Yes, capital is nice, but in a sense it is only “crystallized labor” – the fact that a capitalist owns a factory only means that at some other point he got laborers to build a factory for him. So labor does everything, but it gets only a tiny share of the gains produced. This is because capitalists are oppressing the laborers. Once laborers realize what’s up, they can choose to labor in such a way as to give themselves the full gains of their labor.

I think here that he is thinking of coordination as something that happens instantly in the absence of any obstacle to coordination, and the obstacle to coordination is the capitalists and the “false consciousness” they produce. Remove the capitalists, and the workers – who represent the full productive power of humanity – can direct that productive power to however it is most useful. In my language, Marx simply assumed the invisible nation, thought that the result of perfect negotiation by ideal game theoretic agents with 100% cooperation under a veil of ignorance – would also be the result of real negotiation in the real world, as long as there were no capitalists involved. Maybe this idea – of gradually approaching the invisible nation – is what stood in for the World-Spirit in his dialecticalism. Maybe in 1870, this sort of thinking was excusable.

If capitalists are to be thought of as anything other than parasites, part of the explanation of their contribution has to involve coordination. If Marx didn’t understand that coordination is just as hard to produce as linen or armaments or whatever, if he thought you could just assume it, then capitalists seem useless and getting rid of all previous forms of government so that insta-coordination can solve everything seems like a pretty swell idea.

If you admit that, capitalists having disappeared, there’s still going to be competition, positive and negative sum games, free rider problems, tragedies of the commons, and all the rest, then you’ve got to invent a system that solves all of those issues better than capitalism does. That seems to be the real challenge Marxist intellectuals should be setting themselves, and I hope to eventually discover some who have good answers to it. But at least from the little I learned from Singer, I see no reason to believe Marx had the clarity of thought to even understand the question.

Scott Alexander, “Book Review: Singer on Marx”, Slate Star Codex, 2014-09-13.

May 10, 2014

What did King Solomon and David Lee Roth have in common?

Filed under: Business, Economics, History, Media — Tags: , , — Nicholas @ 12:59

Actually, more than a few things, as the Freakonomics team of Dubner and Levitt explain:

King Solomon built the First Temple in Jerusalem and was known throughout the land for his wisdom.

David Lee Roth fronted the rock band Van Halen and was known throughout the land for his prima-donna excess.

What could these two men possibly have had in common? Well, both were Jewish; both got a lot of girls; and both wrote the lyrics to a No. 1 pop song (“Jump” in Mr. Roth’s case and, in Solomon’s, several verses from Ecclesiastes that appeared in the Byrds’ 1965 hit “Turn! Turn! Turn”). But most improbably, they both dabbled in game theory, as seen in classic stories about their clever strategic thinking.

[…]

And so it was that David Lee Roth and King Solomon both engaged in a fruitful bit of game theory — which, narrowly defined, is the art of beating your opponent by anticipating his next move.

Both men faced a similar problem: How to sift the guilty from the innocent when no one is stepping forward to profess their guilt? A person who is lying or cheating will often respond to an incentive differently than an honest person. Wouldn’t it be nice if this fact could be exploited to ferret out the bad guys?

We believe it can — by tricking the guilty parties into unwittingly revealing their guilt through their own behavior. What should this trick be called? In honor of King Solomon, we’ll name it as if it is a lost proverb: Teach Your Garden to Weed Itself.

September 2, 2013

Macroeconomics and math

Filed under: Economics — Tags: , , , — Nicholas @ 09:06

Noah Smith on the uneasy foundations of modern macroeconomics:

In macro, most of the equations that went into the model seemed to just be assumed. In physics, each equation could be — and presumably had been — tested and verified as holding more-or-less true in the real world. In macro, no one knew if real-world budget constraints really were the things we wrote down. Or the production function. No one knew if this “utility” we assumed people maximized corresponded to what people really maximize in real life. We just assumed a bunch of equations and wrote them down. Then we threw them all together, got some kind of answer or result, and compared the result to some subset of real-world stuff that we had decided we were going to “explain”. Often, that comparison was desultory or token, as in the case of “moment matching”.

In other words, the math was no longer real. It was all made up. You could no longer trust the textbook. When the textbook told you that “Households maximize the expected value of their discounted lifetime utility of consumption”, that was not a Newton’s Law that had been proven approximately true with centuries of physics experiments. It was not even a game theory solution concept that had been proven approximately sometimes true with decades of economics experiments. Instead, it was just some random thing that someone made up and wrote down because A) it was tractable to work with, and B) it sounded plausible enough so that most other economists who looked at it tended not to make too much of a fuss.

We were told not to worry about this. We were told that although macro needed microfoundations — absolutely required them — it was not necessary for the reality of any of these microfoundations to be independently confirmed by evidence. All that was necessary is that the model “worked” after all the microfoundations were thrown together. We were told this not because of any individual failing on the part of any of our teachers, but because this belief is part of the dominant scientific culture of the macro field. It’s the paradigm.

August 29, 2013

Meet the Undercover Economist, Tim Harford

Filed under: Books, Economics, Media — Tags: , — Nicholas @ 08:36

A profile of economist and popular author Tim Harford in The Independent:

Tim Harford can’t help himself. We are navigating our way to lunch in an unfamiliar city and I am momentarily disorientated by the mass of visual paraphernalia at a busy crossing. My hesitation is his cue for a story about the Dutch traffic engineer who found that getting rid of excess street furniture forced car drivers to take more responsibility, dramatically slashing the number of accidents.

Welcome to the world as seen by Harford, a man who made his name explaining the economic rationale behind everything that we do. His tale about the late Hans Monderman is illustrative. Later, over a tableful of dim sum, he adds: “The world is a constant source of ideas for someone who thinks like an economist.”

His bestselling “Undercover Economist” books have made him a founding member of the new tribe popularising the dismal science; not before time given the circumstances, you might add. His latest volume, The Undercover Economist Strikes Back, subtitled How to Run — or Ruin — an Economy, is out this week. It tackles the recent “titanic” mess and is his first foray into macroeconomics, also known as the “bigger picture”.

“It’s my job to figure out an interesting way to talk about these things, and a different angle that’s fun and memorable and tells people something about how the economy works…. I’ve always been much more of a micro guy — individual behaviour and the psychological elements of game theory were always my thing, so when I started, it felt like a sense of duty. But halfway through, the subject had won me over.”

[…]

As it happens, Harford, who turns 40 next month, didn’t intentionally study economics. His undergraduate PPE degree (philosophy, politics and economics) was the “classic Oxford degree for people who don’t know what to do”, and he spent his first year intending to drop economics at the end of it. Pressed by his tutor, after doing “really well”, he changed his mind and thus his life, not least because he met his wife while working at Shell, in the scenario planning team for a certain Vince Cable.

Despite starting out in a job that required forecasting, Harford is defensive of his profession, which is much maligned for not predicting the global crash. “Economists have allowed themselves to walk into a trap where we say we can forecast, but no serious economist thinks we can,” he says, pointing again to a Keynes quote, this time aligning economists and dentists. “You don’t expect dentists to be able to forecast how many teeth you’ll have when you’re 80. You expect them to give good advice and fix problems. We’ve allowed ourselves to become really bad weather forecasters, which is a shame.”

October 4, 2012

Here’s a reality TV show that should exist

Filed under: Humour, Media, Politics, USA — Tags: , , , , — Nicholas @ 12:20

At Marginal Revolution, Alex Tabarrok has a pitch for a new reality TV show that deserves a chance:

I suggest a game show, So You Think You Can Be President? SYTYCBP would have at least three segments.

Coase it Out: Presidential candidates have 12 hours to get a bitterly divorcing couple to divide their assets in a mutually agreeable manner. (Bonus points are awarded if the candidate convinces the couple to stay together.)

Game Theory: Candidates compete in a game of Diplomacy. I would also include several ringers — say Robin Hanson, Bryan Caplan and Salma Hayek. Why these three? Robin is cold, calculating and merciless — make a logical mistake and he will make you pay. Bryan is crafty and experienced. And Salma? I couldn’t refuse her anything but presidents should be made of stronger stuff so we need a test.

Spot the Fraud: Presidential candidates are provided with an economic scenario (mortgage defaults are up, hedge funds are crashing, liquidity is tight). Three experts propose plans. The candidate must choose one of the plans. After the candidate chooses, the true identities of the “experts” are revealed. One is a trucker, another a scuba diver instructor and the last a distinguished economist. Which did the candidate choose?

Entertaining? Check. Correlated with important skills for governing? Check. Can the voters tell who the winner is? Check.

Powered by WordPress