Dr Nanlin JIN PhD Student (October 2002 - July 2007) Department of Computer Science University of Essex

Nanlin Jin joined the Computational Finance Laboratory at University of Essex in 2002 as a PhD student. She was awarded a PhD degree in 2007. She worked on the Automated Bargaining project. She uses genetic programming to approximate subgame perfect equilibrium in bargaining.

Game Theory
Game theory is an important field in economics, sociology, politics, management and many other fields. Game theory was first formalized by von Neumann and Morgenstern in 1940s. In 1950s John Nash proved the existence of Nash Equilibrium for uncooperative games, which broadened the domain of the game theory. In 1994, John Nash won the Nobel Prize jointly with John Harsanvi and Reinhard Selten, for their work in game theory. Reinhard Selten’s contribution was in experimental economics, which path Nanlin followed, but with a computational emphasis. In 2005, both winners of the Nobel Prize in economics worked in the area of game theory: Professor Thomas Schelling (an user of game theory) specialises in explaining strategies of international conflict, such as nuclear war. Professor Robert Aumann (theorist) develops the theoretical underpinnings of bargaining, co-operation and conflict.

Conventional Approach and its limitations
In finding equilibrium solutions, conventional methods in game theory are very labour intensive. Expert knowledge and a substantial amount of effort must be invested to find solutions for every problem. This means a slight modification of a problem could completely change its solution, which often means the solution must be derived from scratch. This significantly limits our capability in studying complex situations. Besides, conventional methods rely on the assumption of full rationality by participants of the game. This is unlikely to be true in real life situations, especially when intensive computation is required in picking the optimal decisions.

Nanlin Jin's Research
Nanlin applied genetic programming to approximate solutions in game theory. Genetic programming is a branch of evolutionary computation, which borrows its ideas from natural selection. Solutions are “evolved” rather than designed. The advantage of this approach is that it is very general and robust. The same search engine can be applied to different game models with relatively little adaptation. In other words, it is not sensitive to minor changes in the problem. Furthermore, it does not rely on the full rationality assumption. Instead, it assumes reinforcement learning by agents, which is a more realistic model for human rationality.

Nanlin Jin's contributions
Evolutionary computation is a general method for searching in the space of solutions. This does not mean that it will magically find solutions in any problem. Care must still be taken in searching efficiently and effectively. To guide the search in genetic programming, Nanlin extended the incentive method, which was originally proposed by Dr Jin Li in his Financial Genetic Programming system (part of the EDDIE Project). Nanlin used co-evolution to evolve bargaining strategies. This allowed her to handle asymmetric situations, e.g. the two players have different information/belief, or they have different outside options.

Acknowledgements
Essex is a research centre with international reputation in computational intelligence. Nanlin benefited from researchers in the constraint satisfaction and optimization laboratory. She has also benefited from advices by Professor Riccardo Poli and Bill Langdon, co-authors of the advanced text “Foundations of Genetic Programming” (Springer 2001). Nanlin has also received substantial support by Professor Abhinay Muthoo (author of “Bargaining Theory with Applications” Cambridge Press 1999) of the Economics Department at the time, and members of the Centre for Computational Finance and Economics (CCFEA).

PhD Thesis

Constraint-based Co-evolutonary Genetic Programming for Bargaining Problems, PhD Thesis, University of Essex, 2007 (pdf / Appendix)