School of Mechanical Engineering:Erella Eisenstadt-Matalon
SCHOOL OF MECHANICAL ENGINEERING SEMINAR
Wednesday, November 20, 2019 at 14:00
Wolfson Building of Mechanical Engineering, Room 206
Co-evolving rationalizable strategies in multi-objective games
PhD student of Ami Moshaiov
The vast majority of game-theoretic studies are on Single Objective Games (SOG), also known as single payoff games. The area of Multi-Objective Games (MOGs), which are also termed as multi payoff, multi criteria or vector payoff games, has received lesser attention. Yet, in many practical problems, in economics and engineering, the players must cope with multiple objectives or payoffs.
The considered MOGs are static, non-cooperative, two-persons, zero-sum games with pure strategies, in which each player has self-conflicting objectives and none of the players has a-priori objective preferences. Yet, each player knows all the available strategies of the opponent and all the payoff vectors that result from all possible interactions between the player's strategies and those of the opponent. Here, common knowledge of rationality is assumed. Namely, it is assumed that each player is rational, and that each player knows it, and so on.
The common approach to deal with MOGs is to assume that the objective preferences of the players are known a-priori. In such a case a utility function is employed which transforms the MOG into a surrogate SOG (usually by a weighted-sum approach). However, players may have doubts when trying to a-priori make a rational decision on their objective preferences. Moreover, existing solution techniques, such as by equilibrium or by a MiniMax approach, suffer from not considering the performance trade-offs. In contrast, here it is assumed that in general, decision-makers should take into account performance trade-offs when making a decision. In view of this assertion and of the state-of-the-art, a novel solution concept to MOGs is suggested, which is based on the idea of rationalizability.
The proposed mutual-rationalizability solution concept for solving MOGs involves two-stages. In the first stage, a Set of Rationalizable Strategies (SRS) and their associated payoff vectors are sought for each of the players. This is done using Pareto-based best replies of the opponent, under the assumptions of common knowledge of rationality and undecided objective preferences by the players. The proposed approach results with trade-off information at the end of the first stage. In the second stage, Multi-Criteria Decision Analysis (MCDA) techniques are used to select a strategy out of the obtained SRSs based on the trade-off information that is revealed in the first stage. To realize the proposed two-stage solution approach, a multi-objective co-evolutionary algorithm is devised, which co-evolve the players’ strategies and finds approximated SRS for each of them.
To demonstrate the proposed approach, a novel MOG version of the Traveling Salesperson Problem (TSP) is suggested. It amalgamates two known versions of the TSP including the competing TSP and the selective TSP. The demonstration shows the capabilities of the proposed search algorithm and the significance of the proposed solution approach.