Game theory in practice
Computing: Software that models human behaviour can make forecasts, outfox rivals and transform negotiations

The Economist | September 3, 2011

FOR a man who claims to lack expertise in the field, Bruce Bueno de Mesquita, an academic at New York University, has made some impressively accurate political forecasts. In May 2010 he predicted that Egypt’s president, Hosni Mubarak, would fall from power within a year. Nine months later Mr Mubarak fled Cairo amid massive street protests. In February 2008 Mr Bueno de Mesquita predicted that Pakistan’s president, Pervez Musharraf, would leave office by the end of summer. He was gone before September. Five years before the death of Iran’s Ayatollah Khomeini in 1989, Mr Bueno de Mesquita correctly named his successor, and, since then, has made hundreds of prescient forecasts as a consultant both to foreign governments and to America’s State Department, Pentagon and intelligence agencies. What is the secret of his success? “I don’t have insights—the game does,” he says.

Mr Bueno de Mesquita’s “game” is a computer model he developed that uses a branch of mathematics called game theory, which is often used by economists, to work out how events will unfold as people and organisations act in what they perceive to be their best interests. Numerical values are placed on the goals, motivations and influence of “players”—negotiators, business leaders, political parties and organisations of all stripes, and, in some cases, their officials and supporters. The computer model then considers the options open to the various players, determines their likely course of action, evaluates their ability to influence others and hence predicts the course of events. Mr Mubarak’s influence, for example, waned as cuts in American aid threatened his ability to keep cronies in the army and security forces happy. Underemployed citizens then realised that disgruntled officials would be less willing to use violence to put down street protests against the ailing dictator.

Mesquita & Roundell, Mr Bueno de Mesquita’s company, is just one of several consulting outfits that run such computer simulations for law firms, companies and governments. Most decision-making advice is political, in the broadest sense of the word—how best to outfox a trial prosecutor, sway a jury, win support from shareholders or woo alienated voters by shuffling a political coalition and making legislative concessions.

But feeding software with good data on all the players involved is especially tricky for political matters. Reinier van Oosten of Decide, a Dutch firm that models political negotiations and vote-trading in European Union institutions, notes that forecasts go astray when people unexpectedly give in to “non-rational emotions”, such as hatred, rather than pursuing what is apparently in their best interests. Sorting out people’s motivations is much easier, however, when making money is the main object. Accordingly, modelling behaviour using game theory is proving especially useful when applied to economics.

Follow the money

Modelling auctions has proved especially successful, says Robert Aumann, an academic at the Hebrew University of Jerusalem who received a Nobel prize in 2005 for his work in game-theory economics. Bids, being quantified, facilitate analysis, and predicting the right answer can be very lucrative. Consulting firms are popping up to help clients design profitable auctions or win them less expensively. In the run-up to an online auction in 2006 of radio-spectrum licences by America’s Federal Communications Commission, Paul Milgrom, a consultant and Stanford University professor, customised his game-theory software to assist a consortium of bidders. The result was a triumph.

When the auction began, Dr Milgrom’s software tracked competitors’ bids to estimate their budgets for the 1,132 licences on offer. Crucially, the software estimated the secret values bidders placed on specific licences and determined that certain big licences were being overvalued. It directed Dr Milgrom’s clients to obtain a patchwork of smaller, less expensive licences instead. Two of his clients, Time Warner and Comcast, paid about a third less than their competitors for equivalent spectrum, saving almost $1.2 billion.

Advances in game theory have “picked up dramatically” in recent years as it has become apparent that failing to do a proper analysis can be costly, says Sergiu Hart, a colleague of Dr Aumann’s at Hebrew University. For example, a few years ago Israel’s government added a novel twist to an auction of oil-refinery facilities. To encourage more and higher bids, the government offered a $12m prize to the second-highest bidder. It was an expensive mistake. Without the incentive, the highest bid would have been about $12m higher, an analysis showed—participants bid low because the loser would strike it rich. Combine that sum with the prize payout, and the government’s loss amounted to roughly $24m. The conclusion, then, is “don’t presume you know what the solution is” without help from modelling software, says Brad Miller, senior modeller at Charles River Associates, a consultancy in Boston. It designs game-theory software to model industrial auctions and the plotting of corporate mergers and acquisitions.

Software is not always needed. A student at Hebrew University, for example, demonstrated the Israeli government’s $24m loss using pen and paper. It took him about two days, however, according to a professor there. Software, naturally, is far faster. But gathering and handling the necessary data can require expensive expertise or training. Decide, the Dutch consultancy, usually charges €20,000-70,000 ($28,000-100,000) to solve a problem using its software, called DCSim, because it must first conduct lengthy interviews with experts. Its clients include government bodies in the Netherlands and abroad, and big companies including IBM, a computer giant, and ABN AMRO, a Dutch bank.

PA Consulting, a British firm, designs bespoke models to help its clients solve specific problems in areas as diverse as pharmaceuticals, fossil-fuel energy and the production of television shows. British government agencies have asked PA Consulting to build models to test regulatory schemes and zoning rules. To give a simple example: if two shrewd, competing ice-cream sellers share a long beach, they will set up stalls back-to-back in the middle and stay put, explains Stephen Black, a modeller in the firm’s London headquarters. Unfortunately for potential customers at the far ends of the beach, each seller prevents the other from relocating—no other spot would be closer to more people. Introduce a third seller, however, and the stifling equilibrium is broken as a series of market-energising relocations and pricing changes kick in. The use of modelling makes business clients more inclined to adopt longer-term strategies, Dr Black says.

But game-theory software can also work well outside the sphere of economics. In 2007 America’s military provided Mr Bueno de Mesquita with classified information to enable him to model the political impact of moving an aircraft carrier close to North Korea (he will not reveal the findings). Game-theory software can even help locate a terrorist’s hideout. To run simulations, Guillermo Owen of the Naval Postgraduate School in Monterey, California, uses intelligence data from the US Air Force to estimate on a 100-point scale the importance a wanted man attaches to his likes (fishing, say) and priorities (remaining hidden or, at greater risk of discovery, recruiting suicide-bombers). Such factors determine where and how terrorists decide to live. Game-theory software played an important role in finding Osama bin Laden’s hideout in Abbottabad, Pakistan, says Mr Owen.

Where is all this heading? Alongside the arms race of increasingly elaborate modelling software, there are also efforts to develop software that can assist in negotiation and mediation. Two decades ago Clara Ponsatí, a Spanish academic, came up with a clever idea while pondering the arduous Israeli-Palestinian peace process. As negotiators everywhere know, the first side to disclose all that it is willing to sacrifice (or pay) loses considerable bargaining power. Bereft of leverage, it can be pushed back to its bottom line by a clever opponent. But if neither side reveals the concessions it is prepared to make, negotiations can stall or collapse. In a paper published in 1992, Dr Ponsatí described how software could be designed to break the impasse.

Difficult negotiations can often be nudged along by neutral mediators, especially if they are entrusted with the secret bottom lines of all parties. Dr Ponsatí’s idea was that if a human mediator was not trusted, affordable or available, a computer could do the job instead. Negotiating parties would give the software confidential information on their bargaining positions after each round of talks. Once positions on both sides were no longer mutually exclusive, the software would split the difference and propose an agreement. Dr Ponsatí, now head of the Institute of Economic Analysis at the Autonomous University of Barcelona, says such “mediation machines” could lubricate negotiations by unlocking information that would otherwise be withheld from an opponent or human mediator.

Such software is now emerging. Barry O’Neill, a game theorist at the University of California, Los Angeles, describes how it can facilitate divorce settlements. A husband and wife are each given a number of points which they secretly allocate to household assets they desire. The wife may inform the software that her valuation of the family car is, say, 15 points. If the husband puts the car’s value at 10 points, he cannot later claim that he deserves more compensation for not getting the car than she would be entitled to.

Predicting an end to conflict

Participants need to be sure that such mediation technology is fully neutral. For large deals, audit firms closely monitor the development and use of such software to ensure that no party secretly obtains information about another’s bargaining positions, says Benny Moldovanu, a game theorist at the University of Bonn. He advises firms that design negotiation software for privatisation schemes and wholesale-electricity markets. This approach will spread to other utility markets, such as water, he believes.

Could software-based mediation spread from divorce settlements and utility pricing to resolving political and military disputes? Game theorists, who consider all these to be variations of the same kind of problem, have developed an intriguing conceptual model of war. The “principle of convergence”, as it is known, holds that armed conflict is, in essence, an information-gathering exercise. Belligerents fight to determine the military strength and political resolve of their opponents; when all sides have “converged” on accurate and identical assessments, a surrender or peace deal can be hammered out. Each belligerent has a strong motivation to hit the enemy hard to show that it values victory very highly. Such a model might be said to reflect poorly on human nature. But some game theorists believe that the model could be harnessed to make diplomatic negotiations a more viable substitute for armed conflict.

Today’s game-theory software is not yet sufficiently advanced to mediate between warring countries. But one day opponents on the brink of war might be tempted to use it to exchange information without having to kill and die for it. They could learn how a war would turn out, skip the fighting and strike a deal, Mr Bueno de Mesquita suggests. Over-optimistic, perhaps—but he does have rather an impressive track record when it comes to predicting the future.