NETWORK CONGESTION / RESOURCE ALLOCATION GAME

We first consider the K-user(player) resource allocation problem when the resources or strategies are associated with homogeneous functions. Further, we consider the K-user(player) matroid resource allocation problem satisfying the specified requirements of the users, which are maximal independent sets of a matroid. The objective is to choose strategies so as to minimize the average maximum cost incurred by a user where the cost of a strategy is the sum of the costs of the elements comprising the strategy. For k commodity networks with heterogeneous latency functions, we consider the price of anarchy (PoA) in multi-commodity selfish routing problems where the latency function of an edge has a heterogeneous dependency on the flow commodities, i.e. when the delay is dependent on the flow of individual commodities, rather than on the aggregate flow. Further we consider the price of anarchy (PoA) in multi-commodity atomic flows where the latency function of an edge has a heterogeneous dependency on the flow commodities, i.e. when the delay is dependent on the flow of individual commodities, rather than on the aggregate flow. Lastly, we show improved bounds on the price of anarchy for uniform latency functions where each edge of the network has the same delay function. We prove bounds on the price of anarchy for the above functions. Our bounds illustrate how the PoA is dependent on θ and the coefficients gij . At the end, we consider security aspects of network routing in a game-theoretic framework where an attacker is empowered with the ability for intrusion into edges of the network; on the other hand, the goal of the designer is to choose routing paths.PH.D in Computer Science, December 201