Selfish rational decisions lead to Nash-equilibria which typically differ from the global optima. We will employ physics-inspired methods to establish the individual-gain and social-cost of selfish decisions, aiming to identify the conditions for which selfish decisions backfire and become detrimental to the individual. We will calculate the ratio between Nash-equilibria and global-optima that is generally difficult to evaluate on the exemplar problem of routing, for different system characteristics such as fractions of selfish users, graph topologies and objective functions. We will develop algorithmic tools to determine the inducements needed to bias the rational decisions of individuals towards the global optimum.
The interplay between making selfish rational decisions and considering the greater good has troubled humans since societies have been formed and has been investigated by sociologists and mathematicians for many years. The underlying assumption is that while selfish, rational choices of individuals lead to a Nash-equilibrium, a state where any deviation from the individual choices made cannot improve their utility-functions, there may be a different global-optimum solution that benefits all, which is inaccessible due to the selfish decisions of individuals. Understanding the relation between selfish choices and global optima is even more pressing and relevant in the digital age where decisions are taken by machines, driven by greedy artificial-intelligence and optimisation algorithms. The underpinning question we aim to address quantitatively is the conditions under which rational selfish decisions become detrimental to the individual, and how they could be influenced to induce changes that would benefit all.
Game-theoretical arguments have been applied to many areas, from finance, traffic and war-games to solid-state physics, but analysing the impact of selfish decisions has been limited. In the exemplar framework of vehicle routing, work carried out on the DynaMIT simulator at MIT shows that above a certain level of penetration, the usefulness of selfish route-planners deteriorates rapidly; which is aligned with the theme of this project. We will develop the analytical framework for investigating the impact of selfish decisions on the individual’s cost/pay-off in stochastic scenarios on networks, with nonlinear interactions between routes at vertices/edges. It will also quantitatively determine the increase in global cost that results from selfish decisions, termed “price of anarchy”, which is generally difficult to evaluate; and provide a principled approach to quantify the measures to be introduced for influencing the selfish choices of individuals. Such measures, in the form of variable-toll roads and lane-control, are already practiced in various countries on the basis of simulations and heuristics.
The aim of the project is to evaluate analytically the impact of selfish routing on both global and individual utility functions and develop algorithmic tools to quantify incentives needed to stir users’ choices towards the global optimum. We will also illustrate the implications for this exemplar domain as a generic model for selfish versus global strategic actions.
Analyse selfish routing in scenarios where, given pre-planned routing suggestions/predictions, individuals can identify and select routes that would benefit them at the expense of others (depending on topology, ratio of users to system-size and fraction of selfish users); evaluate the impact of selfish decisions on both individual and global utility functions.
Investigate analytically the (Nash-like) Wardrop-equilibrium for different system characteristics to evaluate the impact of selfish decisions on the global cost with respect to the global optimum (“price of anarchy”).
Analyse the impact of inducements and develop a principled algorithm for offering incentives such that selfish individual optima (Wardrop-equilibrium) will coincide with the global optimum.
Illustrate extensions from the routing problem to show relevance to other social, economic or biological examples where acting for global good is a superior strategy for the individual, as opposed to a selfish tactic.
The underpinning methodology to be used in this project is inspired by techniques from physics, statistics and game theory. Statistical physics methods aim to analyse large-scale systems with non-linear interactions between system variables that exhibit macroscopic emergent behaviour. Dedicated techniques developed in this area have been exploited to gain insight and devise optimisation algorithms for systems with similar characteristics, from error-correcting codes to hard-combinatorial tasks. We successfully employed methods from this area, such as the cavity and replica methods as well as dynamical message passing, to study both generic and specific routing instances. These methods are particularly useful in the study of networks; they provide insight into the typical behaviour of systems as well as giving rise to decentralised computationally-efficient optimisation algorithms based on passing information (probabilistic messages) between network constituents. Specific methods will be developed to incorporate selfish decisions into the analysis. This framework facilitates the suggested study and algorithmic development for arbitrary objective functions, node/edge costs and uncertainty conditions, which extend the range of scenarios it is applicable for.
We will address rational selfish decisions of individuals, in both “best response” and “repeated game” settings, within a complex and stochastic system. The natural methodology for understanding and analysing such scenarios is that of game theory. We will use game theoretical concepts and techniques to verify that the statistical mechanics tools are consistent and relevant, and make a fair comparison between the obtained solutions and benchmark results achieved in the game theory literature.
 C.H. Yeung, D. Saad, Competition for shortest paths on sparse graphs, Phys. Rev. Lett. 108(20), 208701 (2012).
 K.Y.M. Wong, D. Saad and C.H. Yeung, Distributed Optimization in Transportation and Logistics Networks, The Inst. of Elect., Inf. and Comm. Eng. (IEICE) Transactions, E99-B(11),2237-2246 (2016).
 C.H. Yeung, D. Saad and K.Y.M. Wong, From the physics of interacting polymers to optimizing routes on the London Underground, Proc. National Academy Sci. of the USA 110, 13717-13722 (2013).
 A.Y. Lokhov and D. Saad, Optimal Deployment of Resources for Maximizing Impact in Spreading Processes, Proc. National Academy Sci. of the USA, 114, E8138-E8146 (2017).
Browser does not support script.