“much of its credibility as a prediction”: Christos Papadimitriou, “The Complexity of Finding Nash Equilibria,” in Nisan et al., Algorithmic Game Theory.
“should be considered relevant also”: Aaronson, “Why Philosophers Should Care About Computational Complexity.”
“If your laptop cannot find it”: In Christos Papadimitriou, “The Complexity of Finding Nash Equilibria,” in Nisan et al., Algorithmic Game Theory, p. 30.
“the prisoner’s dilemma”: The prisoner’s dilemma was first conceived by Merrill Flood (of secretary problem and traveling salesman problem fame) and Melvin Drescher at RAND Corporation. In January 1950, they staged a game between UCLA’s Armen Alchian and RAND’s John D. Williams that had prisoner’s dilemma–like payoffs (Flood, “Some Experimental Games”). Princeton’s Albert Tucker was intrigued by this experiment, and in preparing to discuss it that May in a lecture at Stanford, he gave the problem its now famous prison formulation and its name. A detailed history of the origins of game theory and its development in the work of the RAND Corporation can be found in Poundstone, Prisoner’s Dilemma.
a price of anarchy that’s a mere 4/3: Roughgarden and Tardos, “How Bad Is Selfish Routing?” Roughgarden’s 2002 Cornell PhD also addresses the topic of selfish routing.
“the pessimist fears this is true”: Cabell, The Silver Stallion.
picture a “commons” of public lawn: Hardin, “The Tragedy of the Commons.”
“there was this thing called leaded gasoline”: Avrim Blum, personal interview, December 17, 2014.
headline put the trouble succinctly: Scott K. Johnson, “Stable Climate Demands Most Fossil Fuels Stay in the Ground, but Whose?,” Ars Technica, January 8, 2015.
“nowhere is the value of work higher”: “In Search of Lost Time,” Economist, December 20, 2014.
15% take no vacation at all: The study is from Glassdoor and is referenced in ibid.
“People will hesitate to take a vacation”: Mathias Meyer, “From Open (Unlimited) to Minimum Vacation Policy,” December 10, 2014, http://www.paperplanes.de/2014/12/10/from-open-to-minimum-vacation-policy.html.
“Stores are opening earlier than ever before”: Nicole Massabrook, “Stores Open on Thanksgiving 2014: Walmart, Target, Best Buy and Other Store Hours on Turkey Day,” International Business Times, November 26, 2014.
“Don’t hate the player, hate the game”: Ice-T, “Don’t Hate the Playa,” The Seventh Deadly Sin, 1999.
“Don’t ever take sides with anyone against the family”: The Godfather, screenplay by Mario Puzo and Francis Ford Coppola, Paramount Pictures, 1972.
“loaded against the emergence of cooperation”: This quotation of Binmore’s appears in a number of sources, including Binmore, Natural Justice, and Binmore, Game Theory. Kant’s “categorical imperative” originates in his 1785 Groundwork of the Metaphysic of Morals and is discussed in his 1788 Critique of Practical Reason.
a thousand dollars cash for taking a vacation: Libin discusses the motivations for the thousand dollars in, for instance, an interview with Adam Bryant, “The Phones Are Out, but the Robot Is In,” New York Times, April 7, 2012.
make a certain minimal amount of vacation compulsory: Compulsory vacation is already a standard practice in finance, although for reasons of fraud detection rather than morale. For more on compulsory vacation and fraud see, e.g., Philip Delves Broughton, “Take Those Two Weeks Off—or Else,” Wall Street Journal, August 28, 2012.
without federal requirements for paid vacation: Rebecca Ray, Milla Sanes, and John Schmitt, “No-Vacation Nation Revisited,” Center for Economic Policy and Research, May 2013, http://www.cepr.net/index.php/publications/reports/no-vacation-nation-2013.
Things a Computer Scientist Rarely Talks About: Donald E. Knuth.
“The heart has its reasons”: As Pascal put it in Pascal, Pensées sur la religion et sur quelques autres sujets, §277: “Le cœur a ses raisons, que la raison ne connaît point.”
“The canopy can be thought of as an aerial meadow”: Dawkins, The Evidence for Evolution.
makes mice permanently lose their fear of cats: Ingram et al., “Mice Infected with Low-Virulence Strains of Toxoplasma Gondii.”
“Morality is herd instinct in the individual”: The Gay Science, §116, trans. Walter Kaufmann.
“If people expect us to respond irrationally”: Frank, Passions within Reason.
“The worry that people will leave relationships”: Ibid.
“you need a feeling that makes you not want to separate”: Robert Frank, personal interview, April 13, 2015. Frank, “If Homo Economicus Could Choose,” contains this idea, though as he is quick to acknowledge, it builds on work such as Schelling, The Strategy of Conflict; Schelling, “Altruism, Meanness, and Other Potentially Strategic Behaviors”; Akerlof, “Loyalty Filters”; Hirshleifer, “On the Emotions as Guarantors of Threats and Promises”; Sen, “Goals, Commitment, and Identity”; and Gauthier, Morals by Agreement. Frank treats the ideas at book length in Passions within Reason.
“If the prisoner is happy, why lock him in?”: Shaw, Man and Superman.
makes more than 90% of its revenue from selling ads: Google’s 2014 advertising revenue, as detailed in its shareholder report, was $59.6 billion, roughly 90.3% of its total revenue of $66 billion. See https://investor.google.com/financial/tables.html.
raising tens of billions of dollars in revenue: The AWS-3 auction that closed on January 29, 2015, resulted in winning bids totaling $44.899 billion. See http://wireless.fcc.gov/auctions/default.htm?job=auction_factsheet&id=97.
they’re shading their bids based on their prediction of yours!: The equilibrium strategy for a sealed-bid first-price auction with two players is to bid exactly half what you think the item is worth. More generally, in this auction format with n players, you should bid exactly (n−1)⁄n times what you think the item is worth. Note that this strategy is the Nash equilibrium but is not a dominant strategy; that is to say, nothing is better if everyone else is doing it, too, but isn’t necessarily optimal under all circumstances. Caveat emptor. Also, if you don’t know the number of bidders in the auction, the optimal strategy gets complicated in a hurry; see, for instance, An, Hu, and Shum, “Estimating First-Price Auctions with an Unknown Number of Bidders: A Misclassification Approach.” Actually, even the seemingly clean results—(n−1)⁄n—require some serious assumptions, namely that the bidders are “risk neutral” and that their different values for the item are distributed evenly across some given range. The (n−1)⁄n result here comes from Vickrey, “Counterspeculation, Auctions, and Competitive Sealed Tenders,” who warns, “If the assumption of homogeneity among the bidders be abandoned, the mathematics of a complete treatment become intractable.”
the largest flower auction in the world: For more about the Aalsmeer Flower Auction, see http://www.floraholland.com/en/about-floraholland/visit-the-flower-auction/.
a bunch of people all going over a cliff together: Sometimes these cliffs are all too literal. The New York Times, for instance, reported on the deaths of several experienced backcountry skiers in Washington State. The accounts of the survivors show how a group of extremely skilled skiers ended up doing something that almost all the individual members had a bad feeling about.
“If it was up to me, I would never have gone backcountry skiing with twelve people,” said one survivor. “That’s just way too many. But there were sort of the social dynamics of that—where I didn’t want to be the one to say, you know, ‘Hey, this is too big a group and we shouldn’t be doing this.’”
“There’s no way this entire group can make a decision that isn’t smart,” another said to himself. “Of course it’s fine, if we’re all going. It’s got to be fine.”
“Everything in my mind was going off, wanting to tell them to stop,” said a third.
“I thought: Oh yeah, that’s a bad place to be,” recounted a fourth member of the party. “That’s a bad place to be with that many people. But I didn’t say anythin
g. I didn’t want to be the jerk.”
As the Times summarized: “All the locals in the group presumed they knew what the others were thinking. They did not.” See Branch, “Snow Fall.”
known as an “information cascade”: Bikhchandani, Hirshleifer, and Welch, “A Theory of Fads.” See also Bikhchandani, Hirshleifer, and Welch, “Learning from the Behavior of Others.”
“the public pool of information is no longer growing”: David Hirshleifer, personal interview, August 27, 2014.
a sale price of more than $23 million: The pricing on this particular Amazon title was noticed and reported on by UC Berkeley biologist Michael Eisen; see “Amazon’s $23,698,655.93 book about flies,” April 23, 2011 on Eisen’s blog it is NOT junk, http://www.michaeleisen.org/blog/?p=358.
worsen the irrationality of the market: See, for instance, the reactions of Columbia University economist Rajiv Sethi in the immediate wake of the flash crash. Sethi, “Algorithmic Trading and Price Volatility.”
save the entire herd from disaster: This can also be thought of in terms of mechanism design and evolution. It is better on average for any particular individual to be a somewhat cautious herd follower, yet everyone benefits from the presence of some group members who are headstrong mavericks. In this way, overconfidence can be thought of as a form of altruism. For more on the “socially optimal proportion” of such group members, see Bernardo and Welch, “On the Evolution of Overconfidence and Entrepreneurs.”
a way to rethink mechanism design: The phrase “algorithmic mechanism design” first entered the technical literature in Nisan and Ronen, “Algorithmic Mechanism Design.”
It’s called the Vickrey auction: See Vickrey, “Counterspeculation, Auctions, and Competitive Sealed Tenders.”
“strategy-proof,” or just “truthful”: “Strategy-proof” games are also known as “incentive-compatible.” See Noam Nisan, “Introduction to Mechanism Design (for Computer Scientists),” in Nisan et al., eds., Algorithmic Game Theory.
honesty is the dominant strategy: In game theory terms, this makes the Vickrey auction “dominant-strategy incentive-compatible” (DSIC). And a major result in algorithmic game theory, known as “Myerson’s Lemma,” asserts that there is only one DSIC payment mechanism possible. This means that the Vickrey auction is not just a way to avoid strategic, recursive, or dishonest behavior—it’s the only way. See Myerson, “Optimal Auction Design.”
a game-theoretic principle called “revenue equivalence”: The revenue equivalence theorem originated with Vickrey, “Counterspeculation, Auctions, and Competitive Sealed Tenders” and was generalized in Myerson, “Optimal Auction Design,” and Riley and Samuelson, “Optimal Auctions.”
the Vickrey auction is “awesome”: Tim Roughgarden, “Algorithmic Game Theory, Lecture 3 (Myerson’s Lemma),” published October 2, 2013, https://www.youtube.com/watch?v=9qZwchMuslk.
“I think that’s really fantastic”: Noam Nisan, personal interview, April 13, 2015.
“one of the best things you can see”: Paul Milgrom, personal interview, April 21, 2015.
“Hell is other people”: Sartre, No Exit.
CONCLUSION
“to learn how to live well together”: Flood, “What Future Is There for Intelligent Machines?”
“define this as the wisest act”: Russell, “The Elements of Ethics.”
a kind of computational Stoicism: See, e.g., Baltzly, “Stoicism.”
knowing a good song when you hear it: It also happens to be the difference between P and NP. For more delightful philosophical ruminations of this nature, see Aaronson, “Reasons to Believe,” and Wigderson, “Knowledge, Creativity, and P versus NP.”
none of them had wanted to see the bullfight: Scenarios like this one sometimes go by the name of “The Abilene Paradox”; see Harvey, “The Abilene Paradox.”
moving the group toward resolution: This point has also been made by Tim Ferriss, who writes, “Stop asking for suggestions or solutions and start proposing them. Begin with the small things. Rather than asking when someone would like to meet next week, propose your ideal times and second choices. If someone asks, ‘Where should we eat?,’ ‘What movie should we watch?,’ ‘What should we do tonight?,’ or anything similar, do not reflect it back with ‘Well, what/when/where do you want to…?’ Offer a solution. Stop the back and forth and make a decision.” See Ferriss, The 4-Hour Workweek.
offering one or two concrete proposals: Ideally, one would want to know the values that each person in the group assigns to all the options, and adopt a reasonable policy for making a decision based on those. One potential approach is to simply select the option that maximizes the product of the values assigned by everyone—which also lets anyone veto an option by assigning it a value of zero. There are arguments from economics that this is a good strategy, going all the way back to John Nash. See Nash, “The Bargaining Problem.”
minimize the number of coins: Shallit, “What This Country Needs Is an 18¢ Piece.”
ungainly denominations turn change-making: Lueker, “Two NP-Complete Problems in Nonnegative Integer Programming,” showed that under certain assumptions, making change with the fewest number of coins is NP-hard. This result holds if the coins are denominated in binary or the familiar base ten, but not if they are denominated in unary (base one), which does have an efficient solution, as shown in Wright, “The Change-Making Problem.” For more on the computational complexity of making change, see also Kozen and Zaks, “Optimal Bounds for the Change-Making Problem.”
Consider a large parking lot: Cassady and Kobza, “A Probabilistic Approach to Evaluate Strategies for Selecting a Parking Space,” compares the “Pick a Row, Closest Space (PRCS)” and “Cycling (CYC)” parking space–hunting algorithms. The more complicated CYC includes an optimal stopping rule, while PRCS starts at the destination, pointing away, and simply takes the first space. The more aggressive CYC found better spaces on average, but the simpler PRCS actually won in terms of total time spent. Drivers following the CYC algorithm spent more time finding better spaces than those better spaces saved them in walk time. The authors note that research of this nature might be useful in the design of parking lots. Computational models of parking are also explored in, e.g., Benenson, Martens, and Birfir, “PARKAGENT: An Agent-Based Model of Parking in the City.”
“spinning” and “blocking”: For a deeper look at when to spin and when to block, see, for instance, Boguslavsky et al., “Optimal Strategies for Spinning and Blocking.” (Note that this is the same Leonid Boguslavsky we encountered briefly in chapter 1 on a water-skiing trip.)
Bibliography
Aaronson, Scott. “Reasons to Believe” Shtetl-Optimized (blog), September 4, 2006. http://www.scottaaronson.com/blog/?p=122/.
______. “Why Philosophers Should Care About Computational Complexity.” arXiv preprint arXiv:1108.1791, 2011.
Abramson, Norman. “The ALOHA System: Another Alternative for Computer Communications.” In Proceedings of the November 17–19, 1970, Fall Joint Computer Conference, 1970, 281–285.
Ackley, David H. “Beyond Efficiency.” Communications of the ACM 56, no. 10 (2013): 38–40.
Agrawal, Manindra, Neeraj Kayal, and Nitin Saxena. “PRIMES Is in P.” Annals of Mathematics 160 (2004): 781–793.
Agrawal, Rajeev. “Sample Mean Based Index Policies with O(log n) Regret for the Multi-Armed Bandit Problem.” Advances in Applied Probability 27 (1995): 1054–1078.
Agrawal, Shipra, and Navin Goyal. “Analysis of Thompson Sampling for the Multi-armed Bandit Problem.” In Proceedings of the 25th Annual Conference on Learning Theory, 2012.
Akerlof, George A. “Loyalty Filters.” American Economic Review 1983, 54–63.
Allen, David. Getting Things Done: The Art of Stress-Free Productivity. New York: Penguin, 2002.
Aloupis, Greg, Erik D. Demaine, and Alan Guo. “Classic Nintendo Games Are (NP-) Hard.” arXiv preprint arXiv:1203.1895, 2012.
An, Yonghong, Yingyao Hu, and Matthew Shum. “
Estimating First-Price Auctions with an Unknown Number of Bidders: A Misclassification Approach.” Journal of Econometrics 157, no. 2 (2010): 328–341.
Anderson, John R. The Adaptive Character of Thought. Hillsdale, NJ: Erlbaum, 1990.
Anderson, John R., and Robert Milson. “Human Memory: An Adaptive Perspective.” Psychological Review 96, no. 4 (1989): 703–719.
Anderson, John R., and Lael J. Schooler. “Reflections of the Environment in Memory.” Psychological Science 2, no. 6 (1991): 396–408.
Ariely, Dan, and Simon Jones. Predictably Irrational. New York: HarperCollins, 2008.
Arrhenius, Gustaf. “An Impossibility Theorem in Population Axiology with Weak Ordering Assumptions.” Philosophical Studies 49 (1999): 11–21.
Auer, Peter, Nicolò Cesa-Bianchi, and Paul Fischer. “Finite-Time Analysis of the Multiarmed Bandit Problem.” Machine Learning 47 (2002): 235–256.
Austen, Jane. Emma. London: John Murray, 1815.
Austrian, Geoffrey D. Herman Hollerith: Forgotten Giant of Information Processing. New York: Columbia University Press, 1982.
Bachmann, Paul. Die analytische zahlentheorie. Leipzig: Teubner, 1894.
Badger, Lee. “Lazzarini’s Lucky Approximation of π.” Mathematics Magazine 67 (1994): 83–91.
Bailey, Arthur L. Credibility Procedures: Laplace’s Generalization of Bayes’ Rule and the Combination of Collateral Knowledge with Observed Data. New York: New York State Insurance Department, 1950.
Baker, Kenneth R. Introduction to Sequencing and Scheduling. New York: Wiley, 1974.
Baker, Kenneth R., Eugene L. Lawler, Jan Karel Lenstra, and Alexander H. G. Rinnooy Kan. “Preemptive Scheduling of a Single Machine to Minimize Maximum Cost Subject to Release Dates and Precedence Constraints.” Operations Research 31, no. 2 (1983): 381–386.
Algorithms to Live By Page 42