Arrow Research search

Author name cluster

Kamal Jain

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
2 author rows

Possible papers

23

AAAI Conference 2010 Conference Paper

Hidden Market Design

  • Sven Seuken
  • Kamal Jain
  • David Parkes

The next decade will see an abundance of new intelligent systems, many of which will be market-based. Soon, users will interact with many new markets, perhaps without even knowing it: when driving their car, when listening to a song, when backing up their files, or when surfing the web. We argue that these new systems can only be successful if a new approach is chosen towards designing them. In this paper we introduce the general problem of “Hidden Market Design. ” The design of a “weakly hidden” market involves reducing some of the market complexities and providing a user interface (UI) that makes the interaction seamless for the user. A “strongly hidden market” is one where some semantic aspect of a market is hidden altogether (e. g. , budgets, prices, combinatorial constraints). We show that the intersection of UI design and market design is of particular importance for this research agenda. To illustrate hidden market design, we give a series of potential applications. We hope that the problem of hidden market design will inspire other researchers and lead to new research in this direction, paving the way for more successful market-based systems in the future.

PDF Details

TCS Journal 2007 Journal Article

A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property

  • Dinesh Garg
  • Kamal Jain
  • Kunal Talwar
  • Vijay V. Vazirani

We provide the first strongly polynomial time exact combinatorial algorithm to compute Fisher equilibrium for the case when utility functions do not satisfy the Gross substitutability property. The motivation for this comes from the work of Kelly, Maulloo, and Tan [F. P. Kelly, A. K. Maulloo, D. K. H. Tan, Rate control for communication networks: Shadow prices, proportional fairness and stability, Journal of Operational Research (1998)] and Kelly and Vazirani [F. P. Kelly, Vijay V. Vazirani, Rate control as a market equilibrium (2003) (in preparation)] on rate control in communication networks. We consider a tree like network in which root is the source and all the leaf nodes are the sinks. Each sink has got a fixed amount of money which it can use to buy the capacities of the edges in the network. The edges of the network sell their capacities at certain prices. The objective of each edge is to fix a price that can fetch the maximum money for it, and the objective of each sink is to buy capacities on edges in such a way that it can facilitate the sink to pull maximum flow from the source. In this problem, the edges and the sinks play precisely the role of sellers and buyers, respectively, in Fisher’s market model. The utility of a buyer (or sink) takes the form of a Leontief function which is known for not satisfying Gross substitutability property. We develop an O ( m 3 ) exact combinatorial algorithm for computing equilibrium prices of the edges. The time taken by our algorithm is independent of the values of sink money and edge capacities. A corollary of our algorithm is that equilibrium prices and flows are rational numbers. Although there are algorithms to solve this problem they are all based on convex programming techniques. To the best of our knowledge, ours is the first strongly polynomial time exact combinatorial algorithm for computing equilibrium prices of Fisher’s model under the case when buyers’ utility functions do not satisfy gross substitutability property.

Details DOI

FOCS Conference 2004 Conference Paper

A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities

  • Kamal Jain

We provide the first polynomial time exact algorithm for computing an Arrow-Debreu market equilibrium for the case of linear utilities. Our algorithm is based on solving a convex program using the ellipsoid algorithm and simultaneous diophantine approximation. As a side result, we prove that the set of assignments at equilibria is convex and the equilibria prices themselves are log-convex. Our convex program is explicit and intuitive, which allows maximizing a concave function over the set of equilibria. On the practical side, Ye developed an interior point algorithm (Ye, 2004) to find an equilibrium based on our convex program. We also derive separate combinatorial characterizations of equilibrium for Arrow-Debreu and Fisher cases. Our convex program can be extended for many non-linear utilities (Codenotti and Varadarajan, 2004; Jain and Ye) and production models (Jain). Our paper also makes a powerful theorem even more powerful in the area of geometric algorithms and combinatorial optimization. The main idea in this generalization is to allow ellipsoids not to contain the whole convex region but a part of it. This theorem is of independent interest.

Details

FOCS Conference 2004 Conference Paper

Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games

  • Lisa Fleischer
  • Kamal Jain
  • Mohammad Mahdian

We prove the existence of tolls to induce multicommodity, heterogeneous network users that independently choose routes minimizing their own linear function of tolls versus latency to collectively form the traffic pattern of a minimum average latency flow. This generalizes both the previous known results of the existence of tolls for multicommodity, homogeneous users (Beckman et al. , 1956) and for single commodity, heterogeneous users (Cole et al. , 2003). Unlike previous proofs for single commodity users in general graphs, our proof is constructive - it does not rely on a fixed point theorem - and results in a simple polynomial-sized linear program to compute tolls when the number of different types of users is bounded by a polynomial. We show that our proof gives a complete characterization of flows that are enforceable by tolls. In particular, tolls exist to induce any traffic pattern that is the result of minimizing an arbitrary function from R/sup E(G)/ to the reals that is nondecreasing in each of its arguments. Thus, tolls exist to induce flows with minimum average weighted latency, minimum maximum latency, and other natural objectives. We give an exponential bound on tolls that is independent of the number of network users and the number of commodities. We use this to show that multicommodity tolls also exist when users are not from discrete classes, but instead define a general function that trades off latency versus toll preference. Finally, we show that our result extends to very general frameworks. In particular, we show that tolls exist to induce the Nash equilibrium of general nonatomic congestion games to be system optimal. In particular, tolls exist even when 1) latencies depend on user type; 2) latency functions are nonseparable functions of traffic on edges; 3) the latency of a set S is an arbitrary function of the latencies of the resources contained in S. Our exponential bound on size of tolls also holds in this case; and we give an example of a congestion game that shows this is tight; it requires tolls that are exponential in the size of the game.

Details

STOC Conference 2002 Conference Paper

A new greedy approach for facility location problems

  • Kamal Jain
  • Mohammad Mahdian
  • Amin Saberi

We present a simple and natural greedy algorithm for the metric uncapacitated facility location problem achieving an approximation guarantee of 1.61. We use this algorithm to find better approximation algorithms for the capacitated facility location problem with soft capacities and for a common generalization of the k -median and facility location problems. We also prove a lower bound of 1+2/ e on the approximability of the k -median problem. At the end, we present a discussion about the techniques we have used in the analysis of our algorithm, including a computer-aided method for proving bounds on the approximation factor.

Details

FOCS Conference 2001 Conference Paper

An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem

  • Lisa Fleischer
  • Kamal Jain
  • David P. Williamson

In the survivable network design problem (SNDP), given an undirected graph and values r/sub ij/ for each pair of vertices i and j, we attempt to find a minimum-cost subgraph such that there are r/sub ij/ disjoint paths between vertices i and j. In the edge connected version of this problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the problem (VC-SNDP), the paths must be vertex disjoint. K. Jain et al. (1999) propose a version of the problem intermediate in difficulty to these two, called the element connectivity problem (ELC-SNDP, or ELC). These variants of SNDP are all known to be NP-hard. The best known approximation algorithm for the EC-SNDP has performance guarantee of 2 (K. Jain, 2001), and iteratively rounds solutions to a linear programming relaxation of the problem. ELC has a primal-dual O (log k) approximation algorithm, where k=max/sub i, j/ r/sub ij/. VC-SNDP is not known to have a non-trivial approximation algorithm; however, recently L. Fleischer (2001) has shown how to extend the technique of K. Jain ( 2001) to give a 2-approximation algorithm in the case that r/sub ij//spl isin/{0, 1, 2}. She also shows that the same techniques will not work for VC-SNDP for more general values of r/sub ij/. The authors show that these techniques can be extended to a 2-approximation algorithm for ELC. This gives the first constant approximation algorithm for a general survivable network design problem which allows node failures.

Details

FOCS Conference 1999 Conference Paper

Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems

  • Kamal Jain
  • Vijay V. Vazirani

We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m log m) and O(m log m(L+log(n))) respectively, where n and m are the total number of vertices and edges in the underlying graph. The main algorithmic idea is a new extension of the primal-dual schema.

Details

FOCS Conference 1998 Conference Paper

Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem

  • Kamal Jain

We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, which is also known as the survivable network design problem. Our algorithm first solves the linear relaxation of this problem, and then iteratively rounds off the solution. The key idea in rounding off is that in a basic solution of the LP relaxation, at least one edge gets included at least to the extent of half. We include this edge into our integral solution and solve the residual problem.

Details