Colloquium

Network Connection Games: Properties and Complexity of Equilibria

Dr. Rajmohan Rajaraman
Northeastern University

November 21, 2008
JEC 3117, 4:00 p.m. Refreshments at 3:30 p.m.

Abstract:

This talk concerns two classes of network connection games. Motivated by applications in social networks, peer-to-peer and overlay networks, we first introduce the Bounded Budget Connection (BBC) games. In a BBC game, we have a collection of players each of whom has a budget for purchasing links; each link has a cost as well as a length and each node has a set of preference weights for each of the remaining nodes; the objective of each node is to use its budget to buy a set of outgoing links so as to minimize its sum of preference-weighted distances to the remaining nodes. We first consider the special case of uniform BBC games, where all link costs, link lengths and preference weights are equal and all budgets are equal. We show that pure Nash equilibria always exist for uniform BBC games, and establish near-tight bounds on the price of anarchy. For general BBC games, however, determining the existence of a pure Nash equilibrium is NP-hard. We counterbalance this result by considering a natural variant, fractional BBC games -- where it is permitted to buy fractions of links -- and show that a pure Nash equilibrium always exists in such games. The second class of games is based on a fractional model of the Border Gateway Protocol (BGP), the interdomain routing protocol used in the Internet today. The selection of routes in BGP can be modeled as a game, whose pure Nash equilibria correspond to a set of stable routes for given route preferences. It has been shown that pure Nash equilibria do not always exist in such games, thus implying that for certain route preferences BGP may not converge. In recent work, Haxell and Wilfong introduced a fractional model for BGP and showed that when fractional routes are allowed, equilibria always exist. We prove that the problem of computing even an approximate equilibrium in a fractional BGP game is PPAD-hard. The PPAD-hardness result also extends to finding approximate equilibria in fractional BBC games. (Joint work with Nikos Laoutaris, Laura Poplawski, Ravi Sundaram, and Shanghua Teng)

Bio:

TBA

Hosted by: Dr. Elliot Anshelevich (x6491)

Administrative support: Christine Coonrad (x8412)

Last updated: Nov. 13, 2008