The Notion of a Rational Convex Program, and an Algorithm for the Arrow-Debreu Nash Bargaining Game

Vijay Vazirani

Abstract: We introduce the notion of a rational convex program (RCP) and we classify the known RCPs into two classes: quadratic and logarithmic. The importance of rationality is that it opens up the possibility of computing an optimal solution to the program via an algorithm that is either combinatorial or uses an LP-oracle. Next we define a new Nash bargaining game, called ADNB, which is derived from the linear case of the Arrow-Debreu market model. We show that the convex program for ADNB is a logarithmic RCP, but unlike other known members of this class, it is non-total.
Our main result is a combinatorial, polynomial time algorithm for ADNB. It turns out that the reason for infeasibility of logarithmic RCPs is quite different from that for LPs and quadratic RCPs. We believe that our ideas for surmounting the new difficulties will be useful for dealing with other non-total RCPs as well. We give an application of our combinatorial algorithm for ADNB to an important “fair” throughput allocation problem on a wireless channel. Finally, we present a number of interesting questions that the new notion of RCP raises.

 

Guest: Vijay Vazirani
Host: Zvi Lotker

A Proof of the Boyd-Carr Conjecture

Frans Schalekamp, David P. Williamson, Anke van Zuylen

Abstract: Determining the precise integrality gap for the subtour LP relaxation of the traveling salesman problem is a significant open question, with little progress made in thirty years in thegeneral case of symmetric costs that obey triangle inequality. Boyd and Carr [3] observe that we do not even know the worst-case upper bound on the ratio of the optimal 2-matching to the subtour LP; they conjecture the ratio is at most 10/9.

In this paper, we prove the Boyd-Carr conjecture. In the case that a fractional 2-matching has no cut edge, we can further prove that an optimal 2-matching is at most 10/9 times the cost of the fractional 2-matching.

Guest: Anke Van Zuylen
Host: Zvi Lotker