Game theory at work: OR models and algorythms to solve multi-actor heterogeneous decision problems

Key words: Game theory, operations research, optimisation methods, algorithms. The objective of this thesis is to explore the potential of combining Game Theory (GT) models with Operations Research (OR) modelling. This includes development of algorithms to solve these complex OR models for different empirical situations. The challenge is to get GT “at work” by applying such models and techniques to practical cases. Four different cases with a challenge on the development of algorithms are studied. A first case illustrates a multiple coalition formation game in which membership rules and different transfer schemes are described. Given the GT model and the OR model, the goal is to develop methods for checking stability of coalition structures. A new mathematical programming formulation, crucial for the development of the algorithms, is elaborated. Available data is used to determine which stable coalitions appear and which procedures (transfer schemes) can be used to make coalitions stable. Also the influence of membership rules (whether actors are free to become a member) is investigated. Main conclusion is that transfer schemes are useful to be implemented to obtain stable coalitions. Moreover, different membership rules, e.g. veto or majority voting of current members, generate different results with and without transfer schemes. A second case studies a model of coalition formation in politics with n parties trying to form a government. Given the number of parties n and policy dimension m (number of items), computational algorithms are developed to compute all possible majority coalitions and preferences of parties over those coalitions. Application to Dutch data and theoretical examples leads to testing of hypotheses with surprising results with respect to coalition formation such as: being a first mover is not necessarily advantageous, being less flexible is not necessarily advantageous, forming a minimal winning coalition is not necessarily advantageous. A third case describes a two-stage location-quantity game where n > 2 firms are competing on m > 2 markets. The space where the firms can locate are nodes on a network. Analytical solutions for the supplying decisions and properties for determining the number of suppliers to each market are derived. In finding the equilibria, a complete enumeration algorithm and a local search algorithm are used. Two cases are elaborated to illustrate the procedures and the analytical results. The last case deals with a competitive facility location problem in which the concept of Stackelberg leader-follower problem is applied. The follower problem and leader problem are global optimisation problems. Branch-and-Bound (B&B) algorithms that guarantee to find the optimum of both problems are designed.