Efficiency of (Revenue-)Optimal Mechanisms (2009)
Aggarwal, Gagan, Goel, Gagan, Mehta, Aranyak
We compare the expected efficiency of revenue maximizing (or {\em optimal}) mechanisms with that of efficiency maximizing ones. We show that the efficiency of the revenue maximizing mechanism for...
Online Stochastic Matching: Beating 1-1/e (2009)
Feldman, Jon, Mehta, Aranyak, Mirrokni, Vahab, Muthukrishnan, S.
We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani...
Greedy List Intersection (2009)
Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman, Atri Rudra
Abstract — A common technique for processing conjunctive queries is to first match each predicate separately using an index lookup, and then compute the intersection of the resulting rowid lists,...
Deeparnab Chakrabarty, Aranyak Mehta
We study two problems, that of computing social optimum and that of finding fair allocations, in the congestion game model of Milchtaich[8] Although we show that the general problem is hard to...
On Earthmover Distance, Metric Labeling, and 0-Extension (2008)
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
We study the classification problem Metric Labeling and its special case 0-Extension in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial...
On the Fourier Spectrum of Symmetric Boolean Functions ∗ (2008)
Aranyak Mehta, Nisheeth K. Vishnoi
We study the following question:
Is Shapley Cost Sharing Optimal? (2008)
Shahar Dobzinski, Aranyak Mehta, Tim Roughgarden
Abstract. We study the best guarantees of efficiency approximation achievable by cost-sharing mechanisms. Our main result is the first quantitative lower bound that applies to all truthful...
and Problem Complexity General Terms Theory (2008)
Deeparnab Chakrabarty, Aranyak Mehta
We study two problems, that of computing social optimum and that of finding fair allocations, in the congestion game model of Milchtaich[8] Although we show that the general problem is hard to...
Rob Legrand, Evangelos Markakis, Aranyak Mehta
Voting has been the most general scheme for preference aggregation in multi-agent settings involving agents of diverse preferences. Here, we study a specific type of voting protocols for multi-winner...
ABSTRACT Beyond Moulin Mechanisms (2008)
Aranyak Mehta, Tim Roughgarden, Mukund Sundararajan
The only known general technique for designing truthful, approximately budget-balanced cost-sharing mechanisms is due to Moulin. While Moulin mechanisms have been successfully designed for a wide...
Is Shapley Cost Sharing Optimal? (2008)
Shahar Dobzinski, Aranyak Mehta, Tim Roughgarden
Abstract. We study the best guarantees of efficiency approximation achievable by cost-sharing mechanisms. Our main result is the first quantitative lower bound that applies to all truthful...
Deeparnab Chakrabarty, Aranyak Mehta
We study two problems, that of computing social optimum and that of finding fair allocations, in the congestion game model of Milchtaich[8] Although we show that the general problem is hard to...
Extension and Metric Labeling. 0-Extension is closely (2008)
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
We study the fundamental classification problems 0-
Improved Bounds for Learning Symmetric Juntas (2008)
Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
We consider a fundamental problem in computational learning theory: learning in the presence of irrelevant information. In particular we are interested in learning an arbitrary boolean function of n...
Single-item Auctions, Kamal Jain, Aranyak Mehta, Kunal Talwar, Vijay Vazirani
Abstract. We give a simple characterization of all single-item truthrevealing auctions under some mild (and natural) assumptions about the auctions. Our work opens up the possibility of using...
Caching with Expiration Times for Internet Applications (2008)
Parikshit Gopalan, Howard Karloff, Aranyak Mehta, Milena Mihail, Nisheeth Vishnoi
Abstract. Caching data together with expiration times beyond which the data are no longer valid is a standard method for promoting information coherence in distributed systems, including the...
Randomized Time Space Tradeoffs for Directed Graph Connectivity (2008)
Parikshit Gopalan, Richard Lipton, Aranyak Mehta
Abstract. We present a spectrum of randomized time-space tradeoffs for solving directed graph connectivity or STCONN in small space. We use a strategy parameterized by a parameter k that uses k...
Online budgeted matching in random input models with applications to adwords (2008)
We study an online assignment problem, motivated by Adwords Allocation, in which queries are to be assigned to bidders with budget constraints. We analyze the performance of the Greedy algorithm...
Adwords Auctions with Decreasing Valuation Bids (2008)
The choice of a bidding language is crucial in auction design in order to correctly capture bidder utilities. We propose a new bidding model for the Adwords auctions of search engine advertisement...
Posted Price Profit Maximization for Multicast by Approximating Fixed Points (2008)
Aranyak Mehta, Scott Shenker, Vijay V. Vazirani
We describe an iterative fixed point approach for the following stochastic optimization problem: given a multicast tree and probability distributions of user utilities, find an optimal posted price...
Keeping Track of the Latest Gossip in Shared Memory Systems (2007)
Bharat Adsul, Aranyak Mehta, Milind Sohoni
Abstract. In this paper we present a solution to the `Latest Gossip Problem ' for a shared memory distributed system. The Latest Gossip Problem is essentially one of bounded timestamping in...
Randomized Time-Space Tradeoffs for Directed Graph Connectivity (2007)
Parikshit Gopalan, Richard J. Lipton, Aranyak Mehta
We present a spectrum of randomized time-space tradeoffs for solving directed graph connectivity or STCONN in small space. We use a strategy parameterized by a parameter k that uses k pebbles and...
RUDRA: Pricing commodities, or how to sell when buyers have restricted valuations (2007)
Robert Krauthgamer, Aranyak Mehta, Atri Rudra
Abstract. How should a seller price his goods in a market where each buyer prefers a single good among his desired goods, and will buy the cheapest such good, as long as it is within his budget? We...
Design is as easy as optimization (2006)
Deeparnab Chakrabarty, Aranyak Mehta, Vijay V. Vazirani
We consider the class of max-min and min-max optimization problems subject to a global budget (or weight) constraint and we undertake a systematic algorithmic and complexitytheoretic study of such...
Design is as easy as optimization (2006)
Deeparnab Chakrabarty, Aranyak Mehta, Vijay V. Vazirani
We identify a new genre of algorithmic problems – design problems – and study them from an algorithmic and complexity-theoretic view point. We use the learning techniques of Freund-Schapire...
A note on approximate Nash equilibria (2006)
Constantinos Daskalakis, Aranyak Mehta, Christos Papadimitriou
Abstract. In view of the intractability of finding a Nash equilibrium, it is important to understand the limits of approximation in this context. A subexponential approximation scheme is known...
Algorithmic Game Theory (2005)
The interaction of theoretical computer science with game theory and economics has resulted in the emergence of two very interesting research directions. First, it has provided a new model for...
Algorithmic Game Theory (2005)
The interaction of theoretical computer science with game theory and economics has resulted in the emergence of two very interesting research directions. First, it has provided a new model for...
Algorithmic Game Theory (2005)
The interaction of theoretical computer science with game theory and economics has resulted in the emergence of two very interesting research directions. First, it has provided a new model for...
Algorithmic Game Theory (2005)
The interaction of theoretical computer science with game theory and economics has resulted in the emergence of two very interesting research directions. First, it has provided a new model for...
Learning symmetric k-juntas in time n^o(k) (2005)
Kolountzakis, Mihail N., Markakis, Evangelos, Mehta, Aranyak
We give an algorithm for learning symmetric k-juntas (boolean functions of $n$ boolean variables which depend only on an unknown set of $k$ of these variables) in the PAC model under the uniform...
Caching with Expiration Times for Internet Applications (2005)
Gopalan, Parikshit, Karloff, Howard, Mehta, Aranyak, Mihail, Milena, Vishnoi, Nisheeth
Caching data together with expiration times beyond which the data are no longer valid is a standard method for promoting information coherence in distributed systems, including the Internet, the...
Algorithmic game theory (2005)
Thesis (Ph. D.)--Computing, Georgia Institute of Technology, 2006.
Inapproximability results for combinatorial auctions with submodular utility functions (2005)
Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
We consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the...
Adwords and generalized on-line matching (2005)
Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani
How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce...
Adwords and generalized on-line matching (2005)
Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani
How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce...
Adwords and generalized on-line matching (2005)
Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani
How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce...
Richard J. Lipton, Aranyak Mehta, Evangelos Markakis, Nisheeth K. Vishnoi
We study the following question: What is the smallest t such that every symmetric boolean function on k variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of...
Adwords and generalized on-line matching (2005)
Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani
How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce...
Inapproximability results for combinatorial auctions with submodular utility functions (2005)
Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
We consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the...
An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case (2004)
Sanjiv Kapoor, Aranyak Mehta, Vijay Vazirani
Abstract. We present an auction-based algorithm for computing market equilibrium prices in a production model, in which producers have a single linear production constraint, and consumers have linear...
Randomized truthful auctions of digital goods are randomizations over truthful auctions (2004)
In the digital goods setting we prove that for any randomized auction which is truthful in expectation, there exists an equivalent randomized auction which randomizes over truthful deterministic...
Profit-Maximizing Multicast Pricing by Approximating Fixed Points (Extended Abstract) (2003)
Aranyak Mehta, Scott Shenker, Vijay V. Vazirani
Aranyak Mehta Atlanta, GA 30332 aranyak@cc.gatech.edu Scott Shenker ICSI Berkeley, CA 94704 shenker@icsi.berkeley.edu Vijay V. Vazirani Atlanta, Ga 30332 vazirani@cc.gatech.edu ABSTRACT We describe a...
Profit-Maximizing Multicast Pricing by Approximating Fixed Points (2003)
Aranyak Mehta, Scott Shenker, Vijay V. Vazirani
We describe a xed point approach for the following stochastic optimization problem: given a multicast tree and probability distributions of user utilities, compute prices to oer the users in order to...
Playing Large Games using Simple Strategies (2003)
Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
We prove the existence of #-Nash equilibrium strategies with support logarithmic in the number of pure strategies. We also show that the payo#s to all players in any (exact) Nash equilibrium can be...
Caching with expiration times (2002)
Parikshit Gopalan, Howard Karloff, Aranyak Mehta, Milena Mihail, Nisheeth Vishnoi
Abstract. Caching data together with expiration times beyond which the data is no longer valid is a standard method for promoting information coherence in distributed systems, including the Internet...
Mehta, Aranyak, Roughgarden, Tim, Sundararajan, Mukund
The only known general technique for designing truthful and approximately budget-balanced cost-sharing mechanisms with good efficiency or computational complexity properties is due to Moulin [1999....