Title: The Pup Matching Problem and Congestion Games

Speaker: Carol Meyers, MIT

Date/Time: Monday, January 9, 2006, 1:00 – 2:00 pm

Location: Building 980, Room 95 (Sandia NM), Building 915, Room W133 (Sandia CA)

Brief Abstract: In the first part of the talk we examine the Pup Matching problem, a network problem arising in the trucking industry.  The goal is to assign small trailers ('pups') to be paired behind truck cabs in an optimal manner, where each cab can have either one or two pups following it.  This problem is a variant of a multicommodity flow problem where two commodities traversing an arc together incur the cost of the arc only once.

We propose a new integer programming formulation for solving the problem, and we show that the lower bounds given by the linear programming relaxation of this problem are stronger than those obtained in previous formulations.  We also examine one of the practical problems that arises with implementing such integer programming solutions, known as the 'waiting ring' phenomenon.  We discuss how this phenomenon arises, and we quantify how bad it can be and how it can be avoided.  We finish this portion of the talk by looking at pure Nash equilibria in the Pup Matching problem and how far the cost of a Nash equilibrium can be from that of an optimal solution (the 'price of anarchy'.)

We next discuss congestion games, which are a general class of noncooperative games of which the Pup Matching problem is a special case.
In particular, we investigate problems of existence and the price of anarchy of pure Nash equilibria in k-splittable congestion games with linear costs. A k-splittable congestion game is one in which each player may split their flow along at most k paths, giving an intermediate problem to the well-studied cases of splittable and unsplittable congestion games.

We claim that Nash equilibria always exist in weighted k-splittable games, with the added requirement that the flow on each arc must be a multiple of an arbitrarily small number.  With regards to the price of anarchy, we obtain an asymptotic lower bound of 2.4 for unweighted k-splittable congestion games and 2.401 for weighted k-splittable congestion games, and an upper bound of 2.618 in both cases.  We also show that the price of anarchy in k-splittable flows may not be monotone with the value of k.

CSRI POC: Suzanne Rountree, 844-4379 and Cindy Phillips, 845-7296