game theory | The Aperiodical

You're reading: Posts Tagged: game theory

Exciting new maths of 2024

By Peter Rowlett. Posted December 17, 2024

Over at the Finite Group, members (including me and Katie) have been discussing what in maths news has excited us this year. Here’s a summary.

Brayden Casella and fellow authors claimed that there exists a non-terminating game of Beggar-My-Neighbour, solving one of John H. Conway’s anti-Hilbert problems. Beggar-My-Neighbour is a card game similar to War in which two players deal cards onto a shared pile, aiming to win all the cards into their hand. Matthew Scroggs made a bot: Beggar-my-neighbour forever. In other game theory news, Othello is solved.

a sofa with 18 curve sections, each taking a smooth analytic form — Gerver’s sofa, image from Wikimedia.

Jineon Baek claims a resolution to the moving sofa problem. This considers a 2D version of turning a sofa around an L-shaped corner, attempting to find a shape of largest area. (There are some nice animations at Wolfram MathWorld.) Baek offers a proof that the shape above, created by Joseph L. Gerver in 1992, is optimal.

The Great Internet Mersenne Prime Search (GIMPS) announced a new Mersenne prime: \(2^{136,279,841}-1\). You can get maximum excitement about this news from Ayliean on TikTok, and join in the fun by signing up to record yourself saying a chunk of the prime for the Say The Prime project.

One thing that’s new, apart from the prime itself, is that the work was done on a network of GPUs, ending “the 28-year reign of ordinary personal computers finding these huge prime numbers”. Also this was the first GIMPS prime discovered using a probable prime test, so the project chose to use the date the prime was verified by the Lucas-Lehmer primality test as the discovery date. In other computation news, the fifth Busy Beaver number has been found, as well as 202 trillion digits of pi.

A new elliptic curve was discovered, breaking a record set in 2006 and pushing at the limits of current methods for finding them. Here’s some background on the curves and some of the characters involved.

This year also saw a proof of the geometric Langlands conjecture, and this article explains why this is such a big deal.

We’re all still excited about the discovery of the aperiodic monotiles, and the result passed peer review and was published this year.

And finally, it may not be top research news, but 2024 was also the year that Colin Beveridge started his Double Maths First Thing newsletter. Subscribe to the newsletter here, and check out the archive of past issues here at The Aperiodical.

Finite Group is a friendly online mathematical discussion group which is free to join, and members can also pay to access monthly livestreams (next one Friday 20th December 2024 at 8pm GMT and recorded for viewing later). The content isn’t at the level of the research mathematics in this post, but we try to have a fun time chatting about interesting maths. Join us!

Aperiodical News Roundup – January 2024

By Katie Steckles and Peter Rowlett. Posted February 2, 2024

Here’s a round-up of some mathematical news stories not reported elsewhere on the site this month.

Maths News

Hiroki Takizawa claims Othello is solved: perfect play leads to a draw. (via Lance Fortnow)

Stephen Wolfram has announced version 14 of Mathematica, which will be available immediately both on the desktop and in the cloud. The latest version has 6602 built-in functions, and is accompanied by significant documentation and online tutorials to help people learn how to use it.

A new mathematical modelling competition, open from 1st Feb, invites predictions for when cherry trees will blossom in five cities in the USA and Japan, with cash and prizes awarded for a compelling narrative and reproducible analysis containing any data and code used. (via IMAmaths on X)

Science is reporting that a group of mathematicians are producing “low-quality papers” that repeatedly reference their work, distorting citation metrics apparently in an attempt to raise their institution’s rankings. As a result of this practice,

publishing analytics company Clarivate has excluded the entire field of math from the most recent edition of its influential list of authors of highly cited papers, released in November 2023.

(via Nalini Joshi on Mastodon)

Claire Voisin has been awarded the Crafoord Prize in Mathematics by the Royal Swedish Academy of Sciences — the first woman to win this award in mathematics. (via European Mathematical Society on Mastodon)

Sad News

Several death announcements this month, including differential geometer Sigurður Helgason (via Nalini Joshi), Prof Nick Higham FRS, maths education giant Tony Gardiner (via Colin Wright) – and a lovely obituary of Tony from Sacha Borovik – Alan Schoen, physicist and discoverer of the gyroid (via Alison Martin), and Bernd Wegner, who was Editor-in-chief of zbMATH for 37 years (via European Mathematical Society).

Bouton numbers: a new integer sequence

By Peter Rowlett. Posted August 6, 2023

In the 1901 paper that named the game Nim and provided its mathematical analysis, Charles Bouton defined “safe combinations”, positions that if you leave the game in this state, your opponent cannot win. In combinatorial game theory, these are \(\mathcal{P}\) positions (the previous player has already won), as opposed to \(\mathcal{N}\) positions (the next player can win).

Bouton gives a list of “the 35 safe combinations all of whose piles are less than 16”, working in three-heap Nim. Naturally it seemed sensible to check these, so I wrote a bit of Python code to do this. Bouton’s list is good. I realised I could easily adapt my code to find out how many \(\mathcal{P}\) positions there are for three-heap Nim games with other maximum heap sizes: 1, 2, 3, and so on.

And, having generated a sequence of integers, I naturally looked to see if it was in the OEIS. This is sometimes a good way to discover that your sequence of numbers is also found in some unexpected places. It wasn’t there! So I submitted it, and I just got the exciting email “N. J. A. Sloane published your changes”. So I present A363166: “Bouton numbers: a(n) is the number of P positions in games of Nim with three nonzero heaps each containing at most n sticks”.

This is my first OEIS submission, so it’s all very pleasing, even if I’m submitting a ‘new’ sequence inspired by a 1901 paper!

Review: How to Expect the Unexpected, by Kit Yates

By Colin Beveridge. Posted June 16, 2023

Disclosure: I know Kit slightly, off the back of conferences and WhatsApp groups. I try to remain impartial in reviews, but you know, human biases. From here on, in the interests of neutrality, Kit will be known only as Yates.

Book cover: How To Expect The Unexpected, The Science of Making Predictions and the Art of Knowing When Not To

At some point during the pandemic, Kit Yates‘s bushy beard (and the rest of his face) popped onto our TV screen and I said to the kids “oh! I know him!”

It seemed like every news broadcast for the next month was interrupted by shouts of “hey! That’s dad’s maths friend!” Someone they’d never noticed before was suddenly in their consciousness; they had become victims of the Baader-Meinhof phenomenon. Meanwhile, I suffered from linearity bias, fearing that this was going to be the case forever — lockdown would never end, and he would be eternally prevented from writing his book by having to go on telly and explain that COVID is a big deal, actually, to people suffering from normalcy bias.

If you’re not happy with the occasional, justified bit of sweariness, then this probably isn’t the book for you

Cards on the table, I’m a Yates fan. His style is all-clarity-no-bullshit, and apparently happy to argue his corner against all-comers. His first book, The Maths of Life and Death, I reviewed here previously; I expected his second to build from there. Which, given that it’s called How to Expect the Unexpected, gave me a slight worry that I’d fallen into a paradox.

Don’t worry. It’s good.

Of course I wasn’t going to miss a chance to mention the Baader-Meinhof phenomenon again, who do you take me for?

The premise is that humans are, by nature, not very good at prediction, but can be better (at least sometimes). We have evolved an ad-hoc collection of heuristics that have served us perfectly well up to now, thank-you-very-much — like the linearity bias of thinking things will continue much as they are, the normalcy bias of thinking it’s not worth moving camp just because Ug saw what might have been a tiger in the undergrowth, and the Baader-Meinhof tendency of paying attention to new things.

These are admirable starting points — but they’re nowhere near the whole story. A linearity bias lulls us into a false sense of security when a process is exponential; everything is absolutely fine until suddenly it goes very very wrong very very quickly. A normalcy bias means that we’re loath to evacuate a building that really is under attack by tigers.

The book gives us tools to overcome these biases, backed up with plentiful examples and supporting evidence. If I say “Bayes’ rule and basic game theory,” you’ll roll your eyes; practically every pop-maths book of the last few decades has covered both in depth. However, Yates doesn’t tackle them from the usual direction; his examples are fresh and shed a new light on them — for example, he doesn’t lead with the birthday paradox when he’s talking about a combinatorial explosion, he uses several different applications first.

Image of book author Kit Yates. Smiling, bearded man in a blue shirt with arms crossed standing in front of a brick wall. — Author Kit Yates

He also looks at the limitations of prediction, for example in the face of feedback loops: if the chief of a bank publicly admits they’re in difficulty, it only makes the difficulty worse (a snowball); if an epidemiologist says “we need to lock down or we risk 500,000 deaths” and we follow their advice, we lose rather fewer people to the disease, making the forecast wrong (a boomerang).

Prediction (especially weather forecasting) is also cursed by people not understanding probability and by chaos; Yates gives a brief history of meteorology, from sailors’ tales to modern supercomputing, that puts these curses in context.

My main gripe with How to Expect the Unexpected is that it starts off a bit dense — it’s really hard to keep track of all of the biases, fallacies and effects introduced, rat-a-tat-a-tat, in the early stages. I was a bit uncomfortable with the first chapter, in which he visits (and gently misleads) a spiritualist; for all that I agree that spiritualism runs a gamut from self-delusion to outright fraud, it still felt a tiny bit mean-spirited.

Despite that, I enjoyed How to Expect the Unexpected as much as I expected to. Yates has good science, good jokes and good explanations, and I hope for all our sakes that his next book isn’t held up by bird flu or something.

How To Expect The Unexpected is published by Quercus and due out in July 2023.

Mathematical Objects: Fingers with Ben Orlin

By Katie Steckles and Peter Rowlett. Posted July 15, 2022

A conversation about mathematics inspired by some fingers. Presented by Katie Steckles and Peter Rowlett, with special guest Ben Orlin. Ben’s new book is Math Games with Bad Drawings.