Invited Speakers

Dr. Francis Y. L. Chin

(The University of Hong Kong)

Online Tree Node Assignment Problem


This problem involves the assignment and release of nodes in a complete binary tree when faced with a sequence of requests for either an assignment of a node at specified level of the tree or a release of a specified node of the tree. The only rule which dictates the assignments/releases is that the tree remains in a legal configuration where no two assigned nodes lie on a single path from the root to a leaf. The requirement of our problem is to accommodate each request if at all possible and, in order to accommodate a new request, it might be necessary to swap nodes to "make room" for the new request. The target of this problem is to minimize the number of swaps in satisfying a sequence of node assignments and releases.

In this talk, we shall give the background and some recent results of this problem. The online tree node assignment problem is a generalization of the OVSF code assignment problem and fundamental to other applications, such as buddy memory allocation and hypercube subcube allocation.

Dr. Vijay V. Vazirani

(Georgia Tech)

Nash Bargaining via Flexible Budget Markets


In his seminal 1950 paper, John Nash defined the bargaining problem; the ensuing theory of bargaining lies today at the heart of game theory. In this work, we initiate an algorithmic study of Nash bargaining problems.

We consider a class of Nash bargaining problems whose solution can be stated as a convex program. For these problems, we show that there corresponds a market whose equilibrium allocations yield the solution to the convex program and hence the bargaining problem. For several of these markets, we give combinatorial, polynomial time algorithms, using the primal-dual paradigm.

Unlike the traditional Fisher market model, in which buyers spend a fixed amount of money, in these markets, each buyer declares a lower bound on the amount of utility she wishes to derive. The amount of money she actually spends is a specific function of this bound and the announced prices of goods.

Over the years, a fascinating theory has started forming around a convex program given by Eisenberg and Gale in 1959. Besides market equilibria, this theory touches on such disparate topics as TCP congestion control and efficient solvability of nonlinear programs by combinatorial means. Our work shows that the Nash bargaining problem fits harmoniously in this collage of ideas.