Video games and puzzles can be analyzed through the lens of computational complexity. During the Fun with Algorithms 2012 conference I asked several questions during Giovanni Viglietta's presentation on the NP-hardness of Super Mario Bros. After further discussion with Erik Demaine the researchers invited me to join their follow-up paper establishing the game's PSPACE-hardness. The result was published at the Fun with Algorithms 2014 conference and it attracted attention from a wide variety of media outlets including Popular Science and Wired in early June.

Although the initial stories were mostly well-written, the headlines and stories got progressively less accurate as the days went on, as illustrated by the following sequence of headlines:

• Take that, Mom! Turns out Super Mario Bros was all about solving complex math problems by the Register on June 1, 2016.
• How Playing Super Mario Bros Can Be Harder Than Calculus by Vocativ on June 2, 2016.
• Playing Super Mario Brothers is HARDER than calculus: Video game can be as difficult to solve as most complex algorithm by Daily Mail on June 3, 2016.

Notice how complex math problems changed into calculus problems and then the final conclusion of Super Mario Bros being HARDER than calculus.

The FIFA World Cup tournament is the biggest sporting event in the world. During the initial group stage of the tournament the qualifying countries are divided groups of 4. Each group plays a full round-robin tournament and the top two teams advance to the knock-out stage.

Since soccer football games are low scoring, there are a series of tiebreaker rules that dictate which two teams will advance. Unfortunately, these rules are logically ambiguous. The specific problem occurs when a 3-way tie is partially unbroken (i.e. one of the three teams is deemed to be the best or worst out of the three) and whether to continue breaking the 3-way tie or the new 2-way tie. Partially unbroken 3-way ties arise in other sports, and the procedure for breaking them must be specified. For example, the NBA takes the 2-way approach in its tiebreaker rules (clause c.iii.b).

I noticed the shortcoming in FIFA's rules when preparing a lecture for the 2007 offering of CSC 322 Logic and Computer Science at the University of Victoria, and was able to exploit the issue with an example (see below). The resulting story was first reported by Sarah Petrescu in the Victoria Times Colonist. The article was later named one of the most memorable of the year. It was also the subject of a television segment by Jordan Cunningham who won an Edward R Murrow for it.

In recent years FIFA has introduced additional tie-breaker rules based on fair-play points. However, the logical issue still exists, assuming that the tied teams score equally on the additional criteria. Furthermore, additional ambiguous scenarios can be created that exploit the new rules.

FIFA's official rules can be found here (see Article 32, Section 5) with an example here. My original article with fully explained examples can be found here.