Rahul Sami

TCS Journal 2010 Journal Article

Path auctions with multiple edge ownership

• Ye Du
• Rahul Sami
• Yaoyun Shi

In this paper, we study path auction games in which multiple edges may be owned by the same agent. The edge costs and the set of edges owned by the same agent are privately known to the owner of the edges. In this setting, we show that, assuming that edges not on the winning path always get 0 payment, there is no individually rational, strategyproof mechanism in which only edge costs are reported. If the agents are asked to report costs as well as identity information, we show that there is no Pareto efficient mechanism that is false-name proof. We then study a first-price path auction in this model. We show that, in the special case of parallel-path graphs, there is always a Pareto efficient pure strategy ϵ -Nash equilibrium in bids. However, this result does not extend to general graph; we construct a graph in which there is no Pareto efficient pure strategy ϵ -Nash equilibrium.

TCS Journal 2007 Journal Article

Subjective-cost policy routing

• Joan Feigenbaum
• David R. Karger
• Vahab S. Mirrokni
• Rahul Sami

We study a model of path-vector routing in which nodes’ routing policies are based on subjective cost assessments of alternative routes. The routes are constrained by the requirement that all routes to a given destination must be confluent. We show that it is NP-hard to determine whether there is a set of stable routes. We also show that it is NP-hard to find a set of confluent routes that minimizes the total subjective cost; it is hard even to approximate the minimum cost closely. These hardness results hold even for very restricted classes of subjective costs. We then consider a model in which the subjective costs are based on the relative importance nodes place on a small number of objective cost measures. We show that a small number of confluent routing trees is sufficient for each node to have a route that nearly minimizes its subjective cost. We show that this scheme is trivially strategy proof and that it can be computed easily with a distributed algorithm. Furthermore, we prove a lower bound on the number of trees required to contain a ( 1 + ϵ ) -approximately optimal route for each node and show that our scheme is nearly optimal in this respect.

TCS Journal 2005 Journal Article

Computation in a distributed information market

• Joan Feigenbaum
• Lance Fortnow
• David M. Pennock
• Rahul Sami

According to economic theory—supported by empirical and laboratory evidence—the equilibrium price of a financial security reflects all of the information regarding the security's value. We investigate the computational process on the path toward equilibrium, where information distributed among traders is revealed step-by-step over time and incorporated into the market price. We develop a simplified model of an information market, along with trading strategies, in order to formalize the computational properties of the process. We show that securities whose payoffs cannot be expressed as weighted threshold functions of distributed input bits are not guaranteed to converge to the proper equilibrium predicted by economic theory. On the other hand, securities whose payoffs are threshold functions are guaranteed to converge, for all prior probability distributions. Moreover, these threshold securities converge in at most n rounds, where n is the number of bits of distributed information. We also prove a lower bound, showing a type of threshold security that requires at least n / 2 rounds to converge in the worst case.

STOC Conference 2003 Conference Paper

A sublinear algorithm for weakly approximating edit distance

• Tugkan Batu
• Funda Ergün
• Joe Kilian
• Avner Magen
• Sofya Raskhodnikova
• Ronitt Rubinfeld
• Rahul Sami

TCS Journal 2003 Journal Article

Hardness results for multicast cost sharing

• Joan Feigenbaum
• Arvind Krishnamurthy
• Rahul Sami
• Scott Shenker

We continue the study of multicast cost sharing from the viewpoints of both computational complexity and economic mechanism design. We provide fundamental lower bounds on the network complexity of group-strategyproof, budget-balanced mechanisms. We also extend a classical impossibility result in game theory to show that no strategyproof mechanism can be both approximately efficient and approximately budget-balanced. Our results show that one important and natural case of multicast cost sharing is an example of a canonical hard problem in distributed, algorithmic mechanism design; in this sense, they represent progress toward the development of a complexity theory of Internet computation.