Showing posts with label game theory. Show all posts
Showing posts with label game theory. Show all posts

Saturday, October 20, 2012

Game theory can be practical

Children play games. Teenagers play video games. Footballers play games. Economists don't admit to playing games. They prefer to say they study game theory.

This week two academic gamesters, the economist Alvin Roth, of Harvard Business School, and the mathematician Lloyd Shapley, of the University of California, Los Angeles, were awarded the Nobel Prize in Economics for their efforts.

This brought to 10 the number of academics who've won the prize in recent years for helping to develop game theory.

You read a lot about economics in newspapers, but you rarely read about game theory. This may be because, as yet, it's still pretty theoretical without much practical application - though, as we'll see, Roth's endeavours are a notable exception.

But, as all those prizes attest, it's a relatively new area of economic inquiry, one the academics are greatly excited by and believe holds much promise. It's also an approach that's spread to other social sciences.

I'll try to explain it simply, using information cribbed from various sources, but it's actually highly mathematical - another reason it's so attractive to academics, who seem to be turning economics into applied maths.

Economists study how societies allocate resources between competing uses. Conventionally, they study how this is achieved by the movement of prices paid in markets bringing supply and demand into equilibrium.

The standard model assumes the buyers and sellers in those markets are each so small they have no effect on the prices being paid. In reality, many markets are dominated by a few big companies which do have the ability to influence the price.

So game theory began as an alternative way of studying the behaviour of the many ''oligopolies'' that characterise modern economies.

Game theory is the study of how people or firms behave in ''strategic'' situations - those where each player in a market, when deciding what to do, has first to consider how others might respond to that action. So, like a game of chess, the ''games'' economists study have a set of players, a set of moves or strategies available to those players and a range of ''payoffs'' (consequences) of each combination of strategies.

Economists use game theory to describe, predict and explain people's behaviour. They've used it to study auctions, bargaining, merger pricing, oligopolies and much else.

Unlike conventional analysis, game theory allows the possibility of ''multiple equilibria'' - more than one possible outcome the participants regard as satisfactory. And it studies ''decision-making under uncertainty'' - having to make decisions without knowing what the future holds.

Game theory is also able to study co-operative games (where players may form coalitions in competing with other players) as well as non-co-operative games (where all players compete as individuals).

For the most part, however, game theory retains the conventional (unrealistic) assumption of ''rationality'' - people know what's in their best interests and that's what they do.

Game theory began with simple two-player, ''zero-sum games'' - if I win, you must lose. It's moved on to multiple-player, positive-sum games - games where all players may gain because of the ''gains from trade'' (exchange) between people.

The classic game is ''the prisoner's dilemma'', where two prisoners must separately decide whether to co-operate with the other (by admitting nothing) or to ''defect'' (dob in the other in the hope of a lighter sentence). It shows why, in the absence of trust between them, the prisoners may choose not to co-operate (the ''rational'' choice for each), even though it's in their best interests to do so. This game is so famous because it studies the great problem of civilised societies: how to deal with ''free-riders'' - people who take advantage of others' willingness to co-operate.

The work of Shapley and Roth is a long way from that. Shapley, a theoretician who did most of his work in the 1960s, studied ''matching markets''. In most markets you choose what you want and hand over your money. In matching markets you make your choice, but you also need to be chosen by the other side.

If a market has an application or selection procedure, it's a matching market. Such markets determine some of the most important changes in our lives. Marriage, for instance. You don't like thinking of marriage as a market? That's why, in many matching markets, the transaction occurs without the use of money. Using money to determine who gets what would be ''repugnant''.

Shapley was concerned with reaching outcomes in non-monetary matching markets that were ''stable'' - where nobody wanted to change their pair in the belief they could do better.

(This equilibrium is the co-operative games' equivalent to a ''Nash equilibrium'' in non co-operative games. In a Nash equilibrium, each player is making the best choice they can, given the choices of the other players. John Nash, an earlier Nobel laureate, was the mentally disturbed mathematician played by Russell Crowe in the movie, A Beautiful Mind.)

Shapley's contribution, with David Gale, was to discover an algorithm (a mathematical set of rules for solving a problem) that would lead to stable pairs. Say thousands of students have applied to enter 20 universities, setting out their preferences.

The algorithm turns on ''deferred acceptance'' - the unis make their offers, the students select the best offer they've received, but delay accepting it, rejecting any other offers. The unis make further rounds of offers until the process is complete and students then accept the best offer they've had.

Gale and Shapley proved their algorithm always leads to stable pairs. They also showed the side that starts the process gets the better deal. Their approach discourages players from attempting to game the system by not stating their true preferences.

The contribution of Roth, who spent time at Sydney University this year, is more practical. He's taken the Gale-Shapley algorithm, studied it using laboratory experiments and applied it to real-world matching exercises.

He's expert in ''market design'' - changing the rules in markets so they work more efficiently in producing the best outcomes for people. He says a ''free market'' is one that moves freely in achieving efficient outcomes, not necessarily a market with no intervention by the government. In the United States, Roth has helped make changes that improve the pairing of medical interns with hospitals, the pairing of students with high schools and the matching of kidney donors with recipients. He's also done the last one in Australia, actually improving some people's lives.