Arrow Research search

Author name cluster

Aranyak Mehta

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.

20 papers
2 author rows

Possible papers

20

ICLR Conference 2025 Conference Paper

Linear Transformer Topological Masking with Graph Random Features

  • Isaac Reid
  • Avinava Dubey
  • Deepali Jain
  • William F. Whitney
  • Amr Ahmed 0001
  • Joshua Ainslie
  • Alex Bewley
  • Mithun George Jacob

When training transformers on graph-structured data, incorporating information about the underlying topology is crucial for good performance. Topological masking, a type of relative position encoding, achieves this by upweighting or downweighting attention depending on the relationship between the query and keys in the graph. In this paper, we propose to parameterise topological masks as a learnable function of a weighted adjacency matrix -- a novel, flexible approach which incorporates a strong structural inductive bias. By approximating this mask with graph random features (for which we prove the first known concentration bounds), we show how this can be made fully compatible with linear attention, preserving $\mathcal{O}(N)$ time and space complexity with respect to the number of input tokens. The fastest previous alternative was $\mathcal{O}(N \log N)$ and only suitable for specific graphs. Our efficient masking algorithms provide strong performance gains for image and point cloud data, including with $>30$k nodes.

Details

NeurIPS Conference 2022 Conference Paper

Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions

  • Gagan Aggarwal
  • Kshipra Bhawalkar
  • Aranyak Mehta
  • Divyarthi Mohan
  • Alexandros Psomas

Internet ad auctions have evolved from a few lines of text to richer informational layouts that include images, sitelinks, videos, etc. Ads in these new formats occupy varying amounts of space, and an advertiser can provide multiple formats, only one of which can be shown. The seller is now faced with a multi-parameter mechanism design problem. Computing an efficient allocation is computationally intractable, and therefore the standard Vickrey-Clarke-Groves (VCG) auction, while truthful and welfare-optimal, is impractical. In this paper, we tackle a fundamental problem in the design of modern ad auctions. We adopt a ``Myersonian'' approach and study allocation rules that are monotone both in the bid and set of rich ads. We show that such rules can be paired with a payment function to give a truthful auction. Our main technical challenge is designing a monotone rule that yields a good approximation to the optimal welfare. Monotonicity doesn't hold for standard algorithms, e. g. the incremental bang-per-buck order, that give good approximations to ``knapsack-like'' problems such as ours. In fact, we show that no deterministic monotone rule can approximate the optimal welfare within a factor better than $2$ (while there is a non-monotone FPTAS). Our main result is a new, simple, greedy and monotone allocation rule that guarantees a $3$ approximation. In ad auctions in practice, monotone allocation rules are often paired with the so-called \emph{Generalized Second Price (GSP)} payment rule, which charges the minimum threshold price below which the allocation changes. We prove that, even though our monotone allocation rule paired with GSP is not truthful, its Price of Anarchy (PoA) is bounded. Under standard no-overbidding assumptions, we prove bounds on the a pure and Bayes-Nash PoA. Finally, we experimentally test our algorithms on real-world data.

PDF Details

AAAI Conference 2021 Conference Paper

Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions

  • Zhe Feng
  • Guru Guruganesh
  • Christopher Liaw
  • Aranyak Mehta
  • Abhishek Sethi

The connection between games and no-regret algorithms has been widely studied in the literature. A fundamental result is that when all players play no-regret strategies, this produces a sequence of actions whose time-average is a coarsecorrelated equilibrium of the game. However, much less is known about equilibrium selection in the case that multiple equilibria exist. In this work, we study the convergence of no-regret bidding algorithms in auctions. Besides being of theoretical interest, bidding dynamics in auctions is an important question from a practical viewpoint as well. We study repeated game between bidders in which a single item is sold at each time step and the bidder’s value is drawn from an unknown distribution. We show that if the bidders use any mean-based learning rule then the bidders converge with high probability to the truthful pure Nash Equilibrium in a second price auction, in VCG auction in the multi-slot setting and to the Bayesian Nash equilibrium in a first price auction. We note mean-based algorithms cover a wide variety of known no-regret algorithms such as Exp3, UCB, ε-Greedy etc. Also, we analyze the convergence of the individual iterates produced by such learning algorithms, as opposed to the time-average of the sequence. Our experiments corroborate our theoretical findings and also find a similar convergence when we use other strategies such as Deep Q-Learning.

PDF Details

NeurIPS Conference 2020 Conference Paper

Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics

  • Aranyak Mehta
  • Uri Nadav
  • Alexandros Psomas
  • Aviad Rubinstein

We consider the fundamental problem of selecting $k$ out of $n$ random variables in a way that the expected highest or second-highest value is maximized. This question captures several applications where we have uncertainty about the quality of candidates (e. g. auction bids, search results) and have the capacity to explore only a small subset due to an exogenous constraint. For example, consider a second price auction where system constraints (e. g. , costly retrieval or model computation) allow the participation of only $k$ out of $n$ bidders, and the goal is to optimize the expected efficiency (highest bid) or expected revenue (second highest bid). We study the case where we are given an explicit description of each random variable. We give a PTAS for the problem of maximizing the expected highest value. For the second-highest value, we prove a hardness result: assuming the Planted Clique Hypothesis, there is no constant factor approximation algorithm that runs in polynomial time. Surprisingly, under the assumption that each random variable has monotone hazard rate (MHR), a simple score-based algorithm, namely picking the $k$ random variables with the largest $1/\sqrt{k}$ top quantile value, is a constant approximation to the expected highest and second highest value, \emph{simultaneously}.

PDF Details

SODA Conference 2015 Conference Paper

Online Stochastic Matching with Unequal Probabilities

  • Aranyak Mehta
  • Bo Waggoner
  • Morteza Zadimoghaddam

The online stochastic matching problem is a variant of online bipartite matching in which edges are labeled with probabilities. A match will “succeed” with the probability along that edge; this models, for instance, the click of a user in search advertisement. The goal is to maximize the expected number of successful matches. This problem was introduced by Mehta and Panigrahi (FOCS 2012), who focused on the case where all probabilities in the graph are equal. They gave a 0. 567-competitive algorithm for vanishing probabilities, relative to a natural benchmark, leaving the general case as an open question. This paper examines the general case where the probabilities may be unequal. We take a new algorithmic approach rather than generalizing that of Mehta and Panigrahi: Our algorithm maintains, at each time, the probability that each offline vertex has succeeded thus far, and chooses assignments so as to maximize marginal contributions to these probabilities. When the algorithm does not observe the realizations of the edges, this approach gives a 0. 5-competitive algorithm, which achieves the known upper bound for such “non-adaptive” algorithms. We then modify this approach to be “semi-adaptive: ” if the chosen target has already succeeded, choose the arrival's “second choice” instead (while still updating the probabilities non-adaptively). With one additional tweak to control the analysis, we show that this algorithm achieves a competitive ratio of 0. 534 for the unequal, vanishing probabilities setting. A “fully-adaptive” version of this algorithm turns out to be identical to an algorithm proposed, but not analyzed, in Mehta and Panigrahi (2012); we do not manage to analyze it either since it introduces too many dependencies between the stochastic processes. Our semi-adaptive algorithm thus can be seen as allowing analysis of competitive ratio while still capturing the power of adaptivity.

Details

FOCS Conference 2012 Conference Paper

Online Matching with Stochastic Rewards

  • Aranyak Mehta
  • Debmalya Panigrahi

The online matching problem has received significant attention in recent years because of its connections to allocation problems in Internet advertising, crowd-sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations, rather it is to maximize the number of successful allocations, where success of an allocation is governed by a stochastic process which follows the allocation. To address such applications, we propose and study the online matching problem with stochastic rewards (called the ONLINE STOCHASTIC MATCHING problem) in this paper. Our problem also has close connections to the existing literature on stochastic packing problems, in fact, our work initiates the study of online stochastic packing problems. We give a deterministic algorithm for the ONLINE STOCHASTIC MATCHING problem whose competitive ratio converges to (approximately) 0. 567 for uniform and vanishing probabilities. We also give a randomized algorithm which outperforms the deterministic algorithm for higher probabilities. Finally, we complement our algorithms by giving an upper bound on the competitive ratio of any algorithm for this problem. This result shows that the best achievable competitive ratio for the ONLINE STOCHASTIC MATCHING problem is provably worse than that for the (non-stochastic) online matching problem.

Details

STOC Conference 2011 Conference Paper

Online bipartite matching with unknown distributions

  • Chinmay Karande
  • Aranyak Mehta
  • Pushkar Tripathi

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 natural 1 - 1/e -barrier' in the unknown distribution model (our analysis in fact works in the stricter, random order model) and answers an open question in [GM08]. We also describe a family of graphs on which Ranking does no better than 0.727 in the random order model. Finally, we show that for graphs which have k > 1 disjoint perfect matchings, Ranking achieves a competitive ratio of at least 1 - √(1/k - 1/k 2 + 1/n) -- in particular Ranking achieves a factor of 1 - o(1) for graphs with ω(1) disjoint perfect matchings.

Details

TCS Journal 2011 Journal Article

Pricing commodities

  • Robert Krauthgamer
  • Aranyak Mehta
  • Atri Rudra

How should a seller price her 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 provide efficient algorithms that compute near-optimal prices for this problem, focusing on a commodity market, where the range of buyer budgets is small. We also show that our LP rounding based technique easily extends to a different scenario, in which the buyers want to buy all the desired goods, as long as they are within budget.

Details DOI

TCS Journal 2009 Journal Article

A note on approximate Nash equilibria

  • Constantinos Daskalakis
  • Aranyak Mehta
  • Christos Papadimitriou

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 [Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Playing large games using simple strategies, in: EC, 2003], and no approximation better than 1 4 is possible by any algorithm that examines equilibria involving fewer than log n strategies [Ingo Althöfer, On sparse approximations to randomized strategies and convex combinations, Linear Algebra and its Applications (1994) 199]. We give a simple, linear-time algorithm examining just two strategies per player and resulting in a 1 2 -approximate Nash equilibrium in any 2-player game. For the more demanding notion of approximately well supported Nash equilibrium due to [Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, SIAM Journal on Computing (in press) Preliminary version appeared in STOC (2006)] no nontrivial bound is known; we show that the problem can be reduced to the case of win-lose games (games with all utilities 0 or 1 ), and that an approximation of 5 6 is possible, contingent upon a graph-theoretic conjecture. Subsequent work extends the 1 4 impossibility result of Ingo Althöfer’s paper, as mentioned above, to 1 2 [Tomás Feder, Hamid Nazerzadeh, Amin Saberi, Approximating nash equilibria using small-support strategies, in: EC, 2007], making our 1 2 -approximate Nash equilibrium algorithm optimal among the algorithms that only consider mixed strategies of sublogarithmic size support. Moreover, techniques similar to our techniques for approximately well supported Nash equilibria are used in [Spyros Kontogiannis, Paul G. Spirakis, Efficient algorithms for constant well supported approximate equilibria in bimatrix games, in: ICALP, 2007] for obtaining an efficient algorithm for 0. 658-approximately well supported Nash equilibria, unconditionally.

Details DOI

FOCS Conference 2009 Conference Paper

Online Stochastic Matching: Beating 1-1/e

  • Jon Feldman
  • Aranyak Mehta
  • Vahab Mirrokni
  • S. Muthukrishnan 0001

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 1- 1/e ¿ 0. 632, a very familiar bound that holds for many online problems; further, the bound is tight in this case. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the 1 - 1/e bound. Our main result is a 0. 67-approximation online algorithm for stochastic bipartite matching, breaking this 1 - ¿ barrier. Furthermore, we show that no online algorithm can produce a 1 - ¿ approximation for an arbitrarily small e for this problem. Our algorithms are based on computing an optimal offline solution to the expected instance, and using this solution as a guideline in the process of online allocation. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-)matchings. In addition to guiding the online decision making, these two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution. At the end, we discuss extensions of our results to more general bipartite allocations that are important in a display ad application.

Details

TCS Journal 2007 Journal Article

An auction-based market equilibrium algorithm for a production model

  • Sanjiv Kapoor
  • Aranyak Mehta
  • Vijay Vazirani

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 utility functions. We provide algorithms for both the Fisher and Arrow–Debreu versions of the problem.

Details DOI

FOCS Conference 2005 Conference Paper

AdWords and Generalized On-line Matching

  • Aranyak Mehta
  • Amin Saberi
  • Umesh V. Vazirani
  • Vijay V. 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 the notion of a tradeoff revealing LP and use it to derive two optimal algorithms achieving competitive ratios of 1-1/e for this problem.

Details