Recently, a couple of friends and I entered the Brilliant.org Hunger Games competition, in which competitors must create programs which are pitted against others in an arena of sorts. In any given round of the competition, the programs must choose for each other program whether to cooperate with them or take advantage of them. In the Hunger Games competition, these are framed as "hunting" and "slacking".
At face value, the competition is a very standard iterated prisoner’s dilemma. For the general case, the optimal strategy for this game has already been discovered: tit-for-tat. This essence of this strategy is to reciprocate everything done to you in the previous round, and cooperate with everyone in the first round in a show of "good faith". However, the Hunger Games competition had a slight twist: although your program would be able to see the overall reputation of each opponent (id est how many times they hunted versus slacked), no other identifying information would be supplied. This limited knowledge makes true tit-for-tat impossible, since your opponents are effectively anonymized. Although you may know that a player you decided to cooperate with in the previous round defected against you, there’s no way to retaliate against the same player in this round with 100% confidence.
My team’s strategy, nicknamed "The Underminer", both compensated for this lack of knowledge and managed to exploit it. We started with the assumption that tit-for-tat is possible, to a degree. As the number of rounds increases, the reputations of individual opponents becomes solidified, thus making this a means of identification. Although a player with a reputation of 1.0 in round one could drop to a reputation of 0.5 in round two, a player with a reputation of 1.0 in round 20 can only drop to 0.95. Based on this, one can say that the ranking of players by reputation remains mostly static: the worst-ranked opponent will have a very difficult time becoming the highest-ranked. While this is very untrue in the first rounds, at a certain point changing ranks becomes almost impossible. This phenomenon can be imagined like a zipper: before any zipping has occurred, there’s a very large degree of freedom of motion available. However, as you begin to zip, the freedom of motion becomes more and more constrained, until none remains.
While our program implements tit-for-tat as described above in most circumstances, there’s a very specific scenario in which it deviates from this otherwise optimal strategy. As mentioned, the "tit-for-tat" allowed by the Hunger Games competition is not foolproof, since player identities can only be approximately tracked at the beginning of the game. Assuming other players are also tracking opponents by reputation, we can exploit this limitation in knowledge by occasionally attempting to "undermine" another player, assuming their identity. This technique is probably best illustrated by example. Suppose in some round we’re ranked 2nd by reputation at 0.7, while another player is ranked 3rd at 0.6 reputation. Assuming both we and the 3rd ranked player slacked completely this round, there would be no way for us to displace our opponent as 3rd ranked player, since they already have the "bad reputation" head-start. However, the likelihood of our opponent slacking completely this round is very low. In fact, the decisions of our opponent can be estimated given their current reputation, the number of rounds elapsed so far, and a rating of how certain we want our estimation to be by using the lower bound of the Wilson score interval. While this formula is most often used to rank items based on user reviews (and is employed perhaps most famously by Reddit’s "hot" algorithm), in this case we can use it to infer the "true" cooperation rate of opponents and, based on this, their (probable) reputation at the end of the round. Supposing in this circumstance that we predict with a large amount of certainty that our opponent’s reputation at the end of this round will be at worst 0.55, and we can manage to lower our reputation below that, then we choose to slack completely this round. Assuming that the other player remained at 0.6 reputation, while we dove down to 0.5, from a third player’s perspective, this is what happened: the 2nd ranked player went from 0.7 reputation to 0.6 reputation, and the 3rd ranked player went from 0.6 reputation to 0.5 reputation. For the third player to make the assumption that the 2nd ranked player went under the 3rd ranked player - going from 0.7 reputation to 0.5 - would be a strange and unintuitive leap of logic. So, in this way, we can choose to take the advantageous route of fully slacking while passing off some of the negative repercussions of this to a worse-ranked player.
Recently, I was reading about some sample interview questions used (at some point) by Google. One such question was "what are the first 10 consecutive digits of e that form a prime number?" Curious, I went to Wikipedia and looked up some primality tests that I could run on 10-digit prime candidates (if you'll forgive the pun) from e. One such test was Fermat's Primality Test, which can be used to probabilistically assess a number's primality (it fails on Carmichael numbers, et alia). I've written up a short python script which runs the test on the numbers 1 to 100 using computed probable primes as possible coprimes and returns all probable primes.
def test(end): candidates = range(1,end+1) primes = list() for candidate in candidates: prime = True for prime in primes: if candidate % prime: test_result = ((prime ** (candidate - 1)) % candidate) print "Candidate: %s, Prime: %s, Result:%s" %(candidate,prime,test_result) if test_result != 1: prime = False break if prime: primes.append(candidate) return primes test(100)
Human beings are social animals. We live and interact in societies, adopt social norms, and incorporate our society into our identity. I would even say that our sense of justice, morality, and fairness stem from the fact that we are constantly interacting with each other within (in the ancestral environment) a mostly closed community. Doing so means that we are in a constant, mutiplayer iterated prisoner's dilemma, wherein we can earn reputations which will influence our interactions with others. For those not familiar with this concept, allow me to explain: the prisoner's dilemma can be explained as a two-player game. Each of the two players has but a single option: to either cooperate or to defect (in the original scenario, there were two prisoners who could either choose to "rat out" their criminal accomplice or to remain silent). Both players cooperating produces a moderately good outcome for both, whereas both defecting produces a mutually bad outcome for both. Should one player choose to cooperate while the other chooses to defect, the cooperating player gets the worst possible outcome and the defecting player gets the best. This can be represented in the below table:
If two players choose to play only one round of this game, the optimal strategy is to defect, as defection will net an average of 3 points, whereas cooperation will net only 1.5. Moreover, if this game is viewed under the lens of the maximin principle (which states that you should opt for the decision that will have the best worst-case scenario), the worst case for cooperating gets you 0 points, whereas defecting ensures you are rewarded with at least one point.
Player 1 Cooperates Player 1 Defects Player 2 Cooperates Player 1: 3
Player 2: 3
Player 1: 5
Player 2: 0
Player 2 Defects Player 1: 0
Player 2: 5
Player 1: 1
Player 2: 1
Although not as popular as it was during the Cold War, the notion that society is degenerating, international relations are getting worse, and humanity is on the brink of World War III still seems to be a fairly common belief. Moreover, many would have you believe that the apocalypse is due around 2012, a meteor is headed directly for earth, Yellowstone's about to blow, the next ice age is neigh, the magnetic fields of the planet are suddenly about to switch, and a long-overdue solar flare is about to wipe out all of our necessary technological systems. Still others warn that the singularity is near, robot uprising is inevitable, and grey goo will rapidly devour the world. I won't go into detail on other such scenarios. Within the group of people you know, I'd wager at least some of them think that civilization is not long for this world. This is reflected over and over again in our media, producing a plethora of post-apocalyptic films (many of which are quite good). Even if you don't subscribe to this school of thought, clearly there is still some manner of nagging concern which can be preyed upon. However, regardless of present circumstances, the idea that civilization as we know it will terminate within the next century is significantly discredited by employing the simple assumption that we are not special. More specifically, what I mean is that almost certainly we are not at the end of civilization's lifespan, and not at the very beginning (relative to what will come in the future), but instead somewhere in the middle. One can with 95% certainty say that we are currently somewhere in the middle 95% of civilization's lifetime (this is to say, supposing we were to choose 100 random points during the time that civilization will or has existed and claim that it was in the middle 95% of civilization's existence, we would be right 95% of the time (which, arguably, may not be a high enough degree of confidence)). We do have to employ a second assumption, specifically regarding how long "civilization" has been around. A nice, fairly conservative estimate would say that civilization has been around for 7500 years, which places us back at roughly the time the Egyptians were establishing themselves more formally and transitioning into a society which would later become pharaonic. Using these two assumptions, we can then evaluate the following formula in order to get the minimum amount of time civilization should last for:
A / (C + .5 * (1 – C)) – AIn the above, A is the current age of civilization (7500 years), and C is our confidence interval (95%). A quick calculation using these values yields roughly 192 years. Ergo, we can assert with 95% confidence that civilization will last for at least the better part of two centuries. For comparison, the maximum amount of time we could (with 95% confidence) predict civilization lasting for is 292,500 years, as given by the formula
A / (.5 * (1 - C)) - AIn short, civilization isn't going anywhere, at least within our lifetimes. In fact, even raising the confidence interval to 97.5% gives us 95 more years. The interval must be raised to a whopping 98.68 percent until civilization ending in as little as 50 years becomes a possibility, at which point we'd also be stating that civilization could last as long as 1.13 million years (as our interval approaches 1, the lower bound of our predicted remaining civilization lifetime nears 0 and the upper bound approaches infinity, which is to say, "Sometime between as you're reading this and never"). Another way of putting this is that there is a 99.34 % chance that civilization will not end within the next 50 years, putting the likelihood somewhere between the chance you have of dying from poisoning and the chance you have of dying from a fall (statisticians, please feel free to correct me if this last figure is wrong). It should now be apparent to the reader that if I were smarter, I would have titled this post "Models Show Civilization Could End in as Little as Fifty Years". With that settled, you can get some pretty fun results with these formulas; for example, while the world wide web will probably last between half a year and 819 years, the internet will probably last between one year and 1,638 years. Apply them yourself for fun and profit!Tags: civilization, futurism, internet, math, probability, society