We had the great pleasure of talking with Haijun Zhang, postdoctoral research fellow at the Department of Electrical and Computer Engineering at the University of British Columbia in Vancouver, and general chair of the 6th EAI International Conference on Game Theory for Networks (GAMENETS 2016), which will take place in Kelowna, Canada, on May 11-12, 2016. Read on to explore the origins of game theory, and ways to apply it on the problems of our highly networked society.
Game theory did not originate anywhere near computer sciences. Why was applying game theory to this field such a big success?
Game theory is the study of mathematical models of conflict and cooperation between intelligent rational decision-makers. It studies participants’ behavior in strategic situations. Recently, its presence in computer science has become impossible to ignore. It features routinely in the leading conferences and journals of artificial intelligence theory, certainly electronic commerce, as well as networking and other areas of computer science.
There are several reasons for this. One is application pull; the Internet calls for analysis and design of systems that span multiple entities with diverging information and interests. Game theory, for all its limitations, is by far the most developed theory of such interactions. Another is technology push; the mathematics and scientific mindset of game theory are similar to those of many computer scientists. Indeed, it is interesting to note that modern computer science and modern game theory in large measure originated at the same place and time.
Are there other theories from different fields being applied to computer science with a similar success?
From my perspective, recursion theory has made great contribution to computer science. It is a branch of mathematical logic, which is originated from the study on computable function and Turing degrees. The term has a variety of meanings specific to a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, in which it refers to a method of defining functions in which the function being defined is applied within its own definition. Specifically, this defines an infinite number of instances, using a finite expression that for some instances may refer to other instances, but in such a way that no loop or infinite chain of references can occur. The term is also used more generally to describe a process of repeating objects in a self-similar way.
In computer science, a common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms. Divide and conquer serves as a top-down approach to problem solving, where problems are solved by solving smaller and smaller instances. A contrary approach is dynamic programming. This approach serves as a bottom-up approach, where problems are solved by solving larger and larger instances, until the desired size is reached. So we can use recursive thinking to write concise and simple programs. Of course, we’d better pay attention to amounts of memory if the depth of the recursion is very large.
What obstacles are the network researchers trying to overcome using the game theory?
Using game theory to solve the problems in the computer network has a long history. The core issue of game theory is the motive. On the one hand, studies show that participants are selfish, for example, in a wireless network, due to the limited node communication radius, the node communicates with the outside need to be forwarded, but in transmission, the node assists other nodes need to consume their limited resources, such as energy supply, CPU processing time, so they refuse to route discovery service or to forward packets to other nodes and the like. Therefore, using incentive mechanism for the protocol design and coping with users’ selfishness based on mechanism design method of game theory came into being.
On the other hand, with the continuing development of network security technology and the increasing expansion of the network, network security issues have become the information age mankind’s challenges. The attack and defense against network information has also become one of the issues of network security concerns. Network security attack and defense must have a clear understanding and prediction on the other side, and the combination of active defense and game theory can help a lot. By recording intruder tracking analysis, game theory processes the collected data to achieve the purpose of early warning, thus reducing the risk of a real system attack.
What is the importance of GAMENETS 2016, and what does it aim for?
Game theory is the study of mathematical models of conflict and cooperation between intelligent rational decision-makers, which is mainly used in economics, political science, and psychology, as well as logic, computer science, biology, and poker. Originally, it addressed zero-sum games, in which one person’s gains result in losses for the other participants. Today, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers.
Recently, game theory has come to play an increasingly important role in logic and in computer science. Several logical theories have a basis in game semantics. In addition, computer scientists have used games to model interactive computations. Also, game theory provides a theoretical basis to the wireless communication networks.
Separately, game theory has played a role in online algorithms. In particular, the k-server problem, which has in the past been referred to as games with moving costs and request-answer games. Yao’s principle is a game-theoretic technique for proving lower bounds on the computational complexity of randomized algorithms, especially online algorithms.
The emergence of the internet has motivated the development of algorithms for finding equilibrium in games, markets, computational auctions, peer-to-peer systems, and security and information markets. Algorithmic game theory and within it algorithmic mechanism design combine computational algorithm design and analysis of complex systems with economic theory.
Thus, to provide a high level platform for the scholars to communicate and study, GAMENETS is held annually. Additionally, it can exert positive influence on the young generation, who will be the pillars of our future.
Registration for GAMENETS 2016 is now open! Find out more.
