Google Research, Mountain View, CA, USA
Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003 – EC
We prove the existence of ε-Nash equilibrium strategies with support logarithmic in the number of pure strategies. We also show that the payoffs to all players in any (exact) Nash equilibrium can be ε-approximated by the payoffs to the players in ...
Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005 – FOCS
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 the notion of a tradeoff revealing LP and use it ...
Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani
Journal of the ACM, vol. 54,no. 5,2007 – JACM
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 the notion of a trade-off revealing LP ...
Jon Feldman, Aranyak Mehta, Seyed Vahab Mirrokni, S. Muthu Muthukrishnan
50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, 2009 – FOCS
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 and Vazirani gives an approximation ratio of ...
Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou
Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007 – EC
It is known [5] that an additively ε-approximate Nash equilibrium (with supports of size at most two) can be computed in polynomial time in any 2-player game with ε=.5. It is also known that no approximation better than .5 is possible unless ...
Chinmay Karande, Aranyak Mehta, Pushkar Tripathi
Proceedings of the 43rd annual ACM Symposium on Theory of Computing, STOC 2011, 2011 – STOC
We consider the online bipartite matching problem in the unknown distribution input model. We show that the Ranking algorithm of [KVV90] achieves a competitive ratio of at least 0.653. This is the first analysis to show an algorithm which breaks the ...
Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
Internet and Network Economics, First International Workshop, WINE 2005, vol. 3828,2005 – Workshop on Internet and Network Economics
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 players (i.e., the social welfare). In the case ...
Deeparnab Chakrabarty, Aranyak Mehta, Viswanath Nagarajan
Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005 – EC
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 approximate to any factor, we give simple algorithms for ...
Aranyak Mehta, Vijay V. Vazirani
Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004 – EC
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 auctions. By equivalent auctions we mean auctions in ...