Research

Recently, the study of communication and data networks follows a new, more realistic paradigm; according to it, the users of the network are selfish agents, who are not coordinated by a central authority.  Obviously, this new way of modelling networks like the Internet or ad-hoc networks gives rise to new issues, ranging from network performance to network security, and these issues are the target of this proposal.

Game-theoretic techniques can be used to model and analyze such systems in a natural way.  In essence, Game Theory studies the phenomena occurring when independent, autonomous entities, called agents or users, act selfishly.  Thus, the models of Game Theory are abstract representations of real-life situations of interaction and conflict among decision-makers. Such models have already been used in the setting of large transportation networks by the Operations Research community for many years. A more realistic modelling of communication and data networks of selfish users using game-theoretic models is the first objective of the proposed research.

The performance of a network of selfish decision-makers (users) is measured by an appropriate cost function which depends on the behaviour, or strategies of the users.  For example in the case of network routing, the total, system-wide cost can be defined as the total routing cost, or the total latency experienced by all the users in the network.  On the other hand, there is also a cost associated with each individual user (for example the latency experienced by the user). A well known fact is that if each user optimizes her own cost, then they might choose a strategy that does not give the optimal total cost for the entire system.  In other words, the selfish behavior of the users leads to a sub-optimal performance.  The study of the effects that selfish behavior has on the overall network performance, and the design of networks that prevents the rapid degradation of the performance due to such behavior, is the second objective of the proposed research.  This also includes the study of malicious behavior by some of the users, and the design of networks that are secure against such behavior.

We give a brief description of the current modelling of data networks, which follows closely the modelling of large traffic networks. Each user is defined by an origin-destination pair on the network, and the amount of data (bandwidth demand) that he/she wants to route through the network.  The data latency on the network paths depends on the data flow through this (and possibly other) paths, i.e., there are congestion effects.  The users act selfishly, i.e., they try to send their data through paths that they perceive to be the fastest, regardless of the effect their actions will have on the network or other users’ delays.  It is exactly at this point that game-theoretical concepts can be utilized:  this behavior creates an environment of competition, with each user changing continuously the paths he/she uses, until possibly such changes in the flow pattern are not beneficial, in which case the system arrives at a state of equilibrium. The current selfish routing models rely heavily on Wardrop’s principle to describe the selfish users’ behavior at equilibrium: 

• at equilibrium, for each user the travel costs on all the routes actually used are equal, or less than the travel costs on all nonused routes.

Wordrop’s principle can be formulated as a Variational Inequality (VI) over a convex body or as a Complementarity Problem (CP). While these formulations are very flexible, the models they describe are a gross simplification of real-life networks. Our research aims at studying different models that capture Wardrop's principle in more realistic settings (cf. Milestones).