Algorithmic Game Theory In Communications Network

Most of the existing complex systems,such as the Internet,are operated and built by thousands of large and small agents(or users).Each agent attempts to obtain maximum performance according to his own parameters and objectives.Methods from Game Theory and Mathematical Economics can be used to model and analyze such complex systems in a natural way.The performance of a system with selfish agents is measured by an appropriate cost function which depends on the strategies of the agents. For example in the case of selfish routing game,the system-wise cost can be defined as the total latency experienced by all the agents in the network.On the other hand, there is also a cost associated with each selfish agent,e.g.the latency experienced by the agent.It is a well known fact that if each agent optimizes his own cost,then they might choose a strategy without taking care of the optimum for the entire system,also known as the social cost.In other words,the selfish behavior of the agents leads to a sub-optimal performance.There is a recent interest for quantifying this inefficiency,referred to as the price of anarchy[44;55](also referred to as the coordination ratio),which is defined as the ratio between the worst objective function value of a Nash equilibrium of the game and that of an social optimal outcome.A natural variant of the price of anarchy is the price of stability[4],which is the ratio between the best objective function value of one of its equilibria and that of an social optimal outcome.The price of stability has a rational interpretation in many network games-if we envision the outcome as being initially designed by a central authority for subsequent use by selfish agents,then the best equilibrium is an obvious solution to propose.Indeed,in many networking applications,it is not the case that agents are completely independent;rather,they interact with an underlying protocol that essentially proposes a collective solution to all participants,who can either accept it or defect from it.The price of stability measures the benefit of such protocols.There is another recent interest for designing networks that avoid Braess' Paradox. Braess' Paradox isn't paradoxical in the mathematical terms,but rather is extremely counter-intuitive.In a network,where agents seek to minimize their costs,adding an edge with zero latency function to the network,not only results in the overall cost of the network increasing,but also negatively impacts all of the agents.Braess's paradox motivates the following network design problem[60]for improving the efficiency of a network with selfish players:given a network G=(V,E),find a subgraph H of G minimizing the worst pure-strategy Nash equilibrium.A natural variant of the problem is the selective network design problem[5]:given a network G =(V,E) and E₁(?)E, find a subgraph H of G containing the edges of E₁ that minimizes the worst purestrategy Nash equilibrium.Our contribution consists of three issues.First,we consider weighted linear congestion games.We deal with several social cost functions.For each of them we prove upper bounds of the price of stability.For the global priority and infinitely splittable cases,we show that starting from an empty configuration,the solution after any one round of best responses is of a constant-factor approximation.For the fixed priority weighted linear congestion games,we also consider the price of anarchy of correlated equilibria.Second,.we investigate selfish routing with oblivious agents.For simple networks of two nodes connected by parallel links,we show the price of anarchy for the linear latency function and the M/M/1 function,respectively.Finally,from the perspective of computational complexity,we study the selective network design on bottleneck routing games.