Jump to Content
Aranyak Mehta

Aranyak Mehta

Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, desc
  • Year
  • Year, desc
    Incentive Compatibility in the Auto-bidding World
    Yeganeh Alimohammadi
    Andres Perlroth
    24th ACM Conference on Economics and Computation, EC 2023
    Preview abstract Auto-bidding has recently become a popular feature in ad auctions. This feature enables advertisers to simply provide high-level constraints and goals to an automated agent, which optimizes their auction bids on their behalf. These auto-bidding intermediaries interact in a decentralized manner in the underlying auctions, leading to new interesting practical and theoretical questions on auction design, for example, in understanding the bidding equilibrium properties between auto-bidder intermediaries for different auctions. In this paper, we examine the effect of different auctions on the incentives of advertisers to report their constraints to the auto-bidder intermediaries. More precisely, we study whether canonical auctions such as first price auction (FPA) and second price auction (SPA) are auto-bidding incentive compatible (AIC): whether an advertiser can gain by misreporting their constraints to the autobidder. View details
    Auctions without commitment in the autobidding world
    Andres Perlroth
    Proceedings of the ACM Web Conference, WWW 2023
    Preview abstract Advertisers in online ad auctions are increasingly using auto-bidding mechanisms to bid into auctions instead of directly bidding their value manually. One of the prominent auto-bidding formats is that of target cost-per-acquisition (tCPA) which maximizes the volume of conversions subject to a return-of-investment constraint. From an auction theoretic perspective however, this trend seems to go against foundational results that postulate that for profit-maximizing (aka quasi-linear) bidders, it is optimal to use a classic bidding system like marginal CPA (mCPA) bidding rather than using strategies like tCPA. In this paper we rationalize the adoption of such seemingly sub-optimal bidding within the canonical quasi-linear framework. The crux of the argument lies in the notion of commitment. We consider a multi-stage game where first the auctioneer declares the auction rules; then bidders select either the tCPA or mCPA bidding format (and submit bids accordingly); and then, if the auctioneer lacks commitment, it can revisit the rules of the auction (e.g., may readjust reserve prices depending on the bids submitted by the bidders). Our main result is that so long as a bidder believes that the auctioneer lacks commitment to follow the rule of the declared auction then the bidder will make a higher profit by choosing the tCPA format compared to the classic mCPA format. We then explore the commitment consequences for the auctioneer. In a simplified version of the model where there is only one bidder, we show that the tCPA subgame admits a credible equilibrium while the mCPA format does not. That is, when the bidder chooses the tCPA format the auctioneer can credibly implement the auction rules announced at the beginning of the game. We also show that, under some mild conditions, the auctioneer’s revenue is larger when the bidder uses the tCPA format rather than mCPA. We further quantify the value for the auctioneer to be able to commit to the declared auction rules. View details
    Efficiency of Non-Truthful Auctions in Auto-bidding: The Power of Randomization
    Christopher Liaw
    Andres Perlroth
    Proceedings of the ACM Web Conference, WWW 2023
    Preview abstract Auto-bidding is now widely adopted as an interface between advertisers and internet advertising as it allows advertisers to specify high-level goals, such as maximizing value subject to a value-per-spend constraint. Prior research has mainly focused on auctions that are truthful (such as a second-price auction) because these auctions admit simple (uniform) bidding strategies and are thus simpler to analyze. The main contribution of this paper is to characterize the efficiency across the spectrum of all auctions, including non-truthful auctions for which optimal bidding may be complex. For deterministic auctions, we show a dominance result: any uniform bidding equilibrium of a second-price auction (SPA) can be mapped to an equilibrium of any other auction – for example, first price auction (FPA) – with identical outcomes. In this sense, SPA with uniform bidding is an instance-wise optimal deterministic auction. Consequently, the price of anarchy (PoA) of any deterministic auction is at least the PoA of SPA with uniform bidding, which is known to be 2. We complement this by showing that the PoA of FPA without uniform bidding is 2. Next, we show, surprisingly, that truthful pricing is not dominant in the randomized setting. There is a randomized version of FPA that achieves a strictly smaller price of anarchy than its truthful counterpart when there are two bidders per query. Furthermore, this randomized FPA achieves the best-known PoA for two bidders, thus showing the power of non-truthfulness when combined with randomization. Finally, we show that no prior-free auction (even randomized, non-truthful) can improve on a PoA bound of 2 when there are a large number of advertisers per auction. These results should be interpreted qualitatively as follows. When the auction pressure is low, randomization and non-truthfulness is beneficial. On the other hand, if the auction pressure is intense, the benefits diminishes and it is optimal to implement a second-price auction. View details
    Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions
    Divyarthi Mohan
    Alex Psomas
    Advances in Neural Information Processing Systems 35 (NeurIPS 2022) Main Conference Track
    Preview abstract 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. View details
    Preview abstract Auto-bidding is an area of increasing importance in the domain of online advertising. We study the problem of designing auctions in an auto-bidding setting with the goal of maximizing welfare at system equilibrium. Previous results showed that the price of anarchy (PoA) under VCG is 2 and also that this is tight even with two bidders. This raises an interesting question as to whether VCG yields the best efficiency in this setting, or whether the PoA can be improved upon. We present a prior-free randomized auction in which the PoA is approx. 1.896 for the case of two bidders, proving that one can achieve an efficiency strictly better than that under VCG in this setting. We also provide a stark impossibility result for the problem in general as the number of bidders increases -- we show that no (randomized) anonymous truthful auction can have a PoA strictly better than 2 asymptotically as the number of bidders per query increases. While it was shown in previous work that one can improve on the PoA of 2 if the auction is allowed to use the bidder's values for the queries in addition to the bidder's bids, we note that our randomized auction is prior-free and does not use such additional information; our impossibility result also applies to auctions without additional value information. View details
    Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions
    Zhe Feng
    Guru Prashanth Guruganesh
    Chris Liaw
    Abhishek Sethi
    The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21) (2021)
    Preview abstract 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 coarse-correlated 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. View details
    Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics
    Alex Psomas
    Aviad Rubinstein
    Advances in Neural Information Processing Systems (2020)
    Preview abstract 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, simultaneously. View details
    A new dog learns old tricks: RL finds classic optimization algorithms
    Weiwei Kong
    Christopher Liaw
    D. Sivakumar
    Seventh International Conference on Learning Representations (ICLR) (2019)
    Preview abstract We ask whether reinforcement learning can find theoretically optimal algorithms for online optimization problems, and introduce a novel learning framework in this setting. To answer this question, we introduce a number of key ideas from traditional algorithms and complexity theory. Specifically, we introduce the concept of adversarial distributions (universal and high-entropy training sets), which are distributions that encourage the learner to find algorithms that work well in the worst case. We test our new ideas on the AdWords problem, the online knapsack problem, and the secretary problem. Our results indicate that the models have learned behaviours that are consistent with the optimal algorithms for these problems derived using the online primal-dual framework. View details
    Preview abstract Autobidding is becoming increasingly important in the domain of online advertising, and has become a critical tool used by many advertisers for optimizing their ad campaigns. We formulate fundamental questions around the problem of bidding for performance under very general affine cost constraints. We design optimal single-agent bidding strategies for the general bidding problem, in multi-slot truthful auctions. We show that there is an intimate connection between bidding and auction design, in that the bidding formula is optimal if and only if the underlying auction is truthful. We show how a MWU algorithm can be used to learn this optimal bidding formula. Next, we move from the single-agent view to taking a full-system view: What happens when all advertisers adopt optimal autobidding? We prove that in general settings, there exists an equilibrium between the bidding agents for all the advertisers. Further, we prove a Price of Anarchy result: For the general affine constraints, the total value (conversions) obtained by the advertisers in the bidding agent equilibrium is no less than 1/2 of what we could generate via a centralized ad allocation scheme, one which does not consider any auction incentives or provide any per-advertiser guarantee. View details
    Optimizing Ad Refresh In Mobile App Advertising
    Chris Harris
    Florin Constantin
    Sam Ieong
    Xi Tan
    WWW 2018
    Preview abstract In-app advertising is a complex market worth billions of dollars per year, yet it has been studied significantly less than traditional web display ads. In this paper we study an important but often overlooked feature of ads in mobile apps (mostly absent in traditional web ads), that of ad refreshes: A user is shown a stream of banner ads during the app session, in which each ad is displayed in the ad slot for a certain amount of time (the refresh rate) before the ad-slot is refreshed to the next ad. Data analysis on our large-scale experiments that vary refresh rates reveals a surprising result, that cannot be explained by existing user click models: Varying ads’ refresh almost preserves total number of clicks. We propose a new, natural, “two-phase” click model for this setting that explains this independence, as well as our measurements of the click-through rate as a function of the impression’s time-on-screen and of ad-repeat counts. The new click model leads to a clean formulation of the problem of auctioning the entire user-session: i.e., determining online, both the sequence of winning ads as well as the amount of time to display each one. We complement the theoretical auction design with results from a live-traffic experiment with its implementation. Our experiments and analysis provide the theoretical foundation for AdMob’s “Google-optimized refresh rate” feature, used by many mobile apps for better monetization of ads shown to millions of users. View details
    Biobjective Online Bipartite Matching
    Yang Cai
    George Pierrakos
    Workshop in Internet and Network Economics, Springer (2014), pp. 218-231
    Preview abstract Motivated by Online Ad allocation when there are multiple conflicting objectives, we introduce and study the problem of Biobjective Online Bipartite Matching, a strict generalization of the standard setting of Karp, Vazirani and Vazirani, where we are allowed to have edges of two colors, and the goal is to find a matching that is both large and balanced at the same time. We study both deterministic and randomized algorithms for this problem; after showing that the single color upper bounds of 1/2 and 1 − 1/e carry over to our biobjective setting as well, we show that a very natural, albeit hard to analyze, deterministic algorithm achieves a competitive ratio of 0.343. We next show how a natural randomized algorithm matches this ratio, through a simpler analysis, and how a clever – and perhaps not immediately obvious – generalization of Ranking can beat the 1/2 bound and get a competitive ratio of 0.573, coming close to matching the upper bound of 0.63. View details
    Online Matching and Ad Allocation
    Foundations and Trends in Theoretical Computer Science, vol. 8 (4) (2013), pp. 265-368
    Preview abstract Matching is a classic problem with a rich history and a significant impact, both on the theory of algorithms and in practice. Recently there has been a surge of interest in the online version of matching and its generalizations, due to the important new application domain of Internet advertising. The theory of online matching and allocation has played a critical role in designing algorithms for ad allocation. This monograph surveys the key problems, models and algorithms from online matchings, as well as their implication in the practice of ad allocation. The goal is to provide a classification of the problems in this area, an introduction into the techniques used, a glimpse into the practical impact, and to provide direction in terms of open questions. Matching continues to find core applications in diverse domains, and the advent of massive online and streaming data emphasizes the future applicability of the algorithms and techniques surveyed here. View details
    Designing Markets for Daily Deals
    Yang Cai
    Bo Waggoner
    Conference on Web and Internet Economics (WINE) (2013) (to appear)
    Preview
    Optimizing Budget Constrained Spend in Search Advertising
    Chinmay Karande
    Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013, ACM, pp. 697-706
    Preview abstract Search engine ad auctions typically have a significant fraction of advertisers who are budget constrained, i.e., if allowed to participate in every auction that they bid on, they would spend more than their budget. This yields an important problem: selecting the ad auctions in which these advertisers participate, in order to optimize different system objectives such as the return on investment for advertisers, and the quality of ads shown to users. We present a system and algorithms for optimizing such budget constrained spend. The system is designed be deployed in a large search engine, with hundreds of thousands of advertisers, millions of searches per hour, and with the query stream being only partially predictable. We have validated the system design by implementing it in the Google ads serving system and running experiments on live traffic. We have also compared our algorithm to previous work that casts this problem as a large linear programming problem limited to popular queries, and show that our algorithms yield substantially better results. View details
    Online Matching with Stochastic Rewards
    Debmalya Panigrahi
    Symposium on Foundations of Computer Science (FOCS), IEEE (2012)
    Preview abstract 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. View details
    Online Graph Edge-Coloring in the Random-Order Arrival Model
    Bahman Bahmani
    Rajeev Motwani
    Theory of Computing, vol. 8(1) (2012), pp. 567-595
    Preview abstract A classic theorem by Vizing asserts that if the maximum degree of a graph is ?, then it is possible to color its edges, in polynomial time, using at most ?+1 colors. However, this algorithm is offline, i.e., it assumes the whole graph is known in advance. A natural question then is how well we can do in the online setting, where the edges of the graph are revealed one by one, and we need to color each edge as soon as it is added to the graph. Online edge coloring has an important application in fast switch scheduling. A natural model is that edges arrive online, but in a random permutation. Even in the random permutation model, the best proven approximation factor for any algorithm is the factor 2 of the simple greedy algorithm (which holds even in the worst-case online model). The algorithm of Aggarwal et al. (FOCS'03) provides a 1+o(1) factor algorithm for the case of very dense multi-graphs, when ?=?(n2), where n is the number of vertices. In this paper, we show that for graphs with ?=?(logn), it is possible to color the graph with (1+ee2?1+o(1))??1.43? colors, with high probability, in the online random-order model. Our algorithm is inspired by a 1.6-approximate distributed offline algorithm of Panconesi and Srinivasan (PODC'92), which we extend by reusing failed colors online. Further, we show how we can extend the algorithm to reuse colors multiple times, which reduces the approximation factor below 1.43. We conjecture that the algorithm becomes nearly optimal (i.e., uses ?+o(?) colors) with O(log(?/logn)) reuses. We reduce the question to proving the non-negativity of a certain recursively defined sequence, which looks true in computer simulations. This non-negativity can be proved explicitly for a small number of reuses, giving improved algorithms: e.g., the algorithm which reuses colors 5 times uses 1.26? colors. View details
    Preview abstract We study the following vertex-weighted online bipartite matching problem: G(U, V, E) is a bipartite graph. The vertices in U have weights and are known ahead of time, while the vertices in V arrive online in an arbitrary order and have to be matched upon arrival. The goal is to maximize the sum of weights of the matched vertices in U. When all the weights are equal, this reduces to the classic online bipartite matching problem for which Karp, Vazirani and Vazirani gave an optimal (1 − 1/e)-competitive algorithm in their seminal work [KVV90]. Our main result is an optimal (1 − 1/e)-competitive randomized algorithm for general vertex weights. We use random perturbations of weights by appropriately chosen multiplicative factors. Our solution constitutes the first known generalization of the algorithm in [KVV90] in this model and provides new insights into the role of randomization in online allocation problems. It also effectively solves the problem of online budgeted allocations [MSVV05] in the case when an agent makes the same bid for any desired item, even if the bid is comparable to his budget - complementing the results of [MSVV05, BJN07] which apply when the bids are much smaller than the budgets. View details
    A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model.
    Bahman Bahmani
    Rajeev Motwani
    Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010,, SIAM, pp. 31-39
    Preview
    Online Stochastic Matching: Beating 1-1/e
    S. Muthukrishnan
    Symposium on the Foundations of Computer Science (FOCS) (2009)
    Preview abstract 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−1e≃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−1e bound.Our main result is a 0.67-approximation online algorithm for stochastic bipartite matching, breaking this 1−1e barrier. Furthermore, we show that no online algorithm can produce a 1−ϵ approximation for an arbitrarily small ϵ 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. View details
    On the Fourier spectrum of symmetric Boolean functions
    Mihail N. Kolountzakis
    Richard J. Lipton
    Evangelos Markakis
    Nisheeth K. Vishnoi
    Combinatorica, vol. 29 (2009), pp. 363-387
    Preview
    Efficiency of (Revenue-)Optimal Mechanisms
    Proceedings of the 10th ACM Conference on Electronic Commerce (2009)
    Preview abstract We compare the expected efficiency of revenue maximizing (or optimal) mechanisms with that of efficiency maximizing ones. We show that the efficiency of the revenue maximizing mechanism for selling a single item with (k + log_{e / e−1} k + 1) bidders is at least as much as the efficiency of the efficiency-maximizing mechanism with k bidders, when bidder valuations are drawn i.i.d. from a Monotone Hazard Rate distribution. Surprisingly, we also show that this bound is tight within a small additive constant of 5.7. In other words, Θ(log k) extra bidders suffice for the revenue maximizing mechanism to match the efficiency of the efficiency maximizing mechanism, while o(log k) do not. This is in contrast to the result of Bulow and Klemperer comparing the revenue of the two mechanisms, where only one extra bidder suffices. More precisely, they show that the revenue of the efficiency maximizing mechanism with k + 1 bidders is no less than the revenue of the revenue maximizing mechanism with k bidders. We extend our result for the case of selling t identical items and show that 2.2 log k + tΘ(log log k) extra bidders suffice for the revenue maximizing mechanism to match the efficiency of the efficiency maximizing mechanism. In order to prove our results, we do a classification of Monotone Hazard Rate (MHR) distributions and identify a family of MHR distributions, such that for each class in our classification, there is a member of this family that is point-wise lower than every distribution in that class. This lets us prove interesting structural theorems about distributions with Monotone Hazard Rate. View details
    Online budgeted matching in random input models with applications to Adwords
    Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, SIAM, San Francisco (2008), pp. 982-991
    Preview
    Adwords Auctions with Decreasing Valuation Bids
    Internet and Network Economics (WINE), Springer, San Diego (2007), pp. 335-340
    Preview
    AdWords and Generalized Online Matching
    Amin Saberi
    Umesh Vazirani
    Vijay Vazirani
    Journal of the ACM, vol. 54, no. 5 (2007)
    Preview
    Is Shapley Cost Sharing Optimal?
    Shahar Dobzinski
    Tim Roughgarden
    SAGT (2008), pp. 327-336
    Beyond moulin mechanisms
    T. Roughgarden
    M. Sundararajan
    Games and Economic Behavior (2008)
    Is Shapley Cost Sharing Optimal?
    S. Dobzinski
    T. Roughgarden
    M. Sundararajan
    Lecture Notes in Computer Science (SAGT), vol. 4997 (2008), pp. 327
    A note on approximate Nash equilibria
    C. Daskalakis
    C. Papadimitriou
    Theoretical Computer Science (2008)
    Inapproximability results for combinatorial auctions with submodular utility functions
    S. Khot
    R.J. Lipton
    E. Markakis
    Algorithmica, vol. 52 (2008), pp. 3-18
    Pricing commodities, or how to sell when buyers have restricted valuations
    R. Krauthgamer
    A. Rudra
    Lecture Notes in Computer Science (WAOA), vol. 4927 (2008), pp. 1
    Greedy list intersection
    R. Krauthgamer
    V. Raman
    A. Rudra
    IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008, pp. 1033-1042
    Beyond moulin mechanisms
    Tim Roughgarden
    ACM Conference on Electronic Commerce (2007), pp. 1-10
    An auction-based market equilibrium algorithm for a production model
    S. Kapoor
    V. Vazirani
    Theoretical Computer Science, vol. 378 (2007), pp. 153-164
    Some results on approximating the minimax solution in approval voting
    R. LeGrand
    E. Markakis
    Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems (2007)
    Progress in approximate Nash equilibria
    C. Daskalakis
    C. Papadimitriou
    Proceedings of the 8th ACM conference on Electronic commerce (2007), pp. 355-358
    Design is as easy as optimization
    D. Chakrabarty
    V.V. Vazirani
    Lecture Notes In Computer Science (ICALP), vol. 4051 (2006), pp. 477
    Posted price profit maximization for multicast by approximating fixed points
    S. Shenker
    V.V. Vazirani
    Journal of Algorithms (conference version in Electronic Commerce), vol. 58 (2006), pp. 150-164
    On earthmover distance, metric labeling, and 0-extension
    H. Karloff
    S. Khot
    Y. Rabani
    Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (2006), pp. 547-556
    Fairness and optimality in congestion games
    D. Chakrabarty
    V. Nagarajan
    Proceedings of the 6th ACM Conference on Electronic Commerce (2005), pp. 52-57
    A Simple Characterization for Truth-Revealing Single-Item Auctions
    Kamal Jain
    Kunal Talwar
    Vijay V. Vazirani
    WINE (2005), pp. 122-128
    Learning symmetric k-juntas in time n\^ o (k)
    M.N. Kolountzakis
    E. Markakis
    Arxiv preprint math.CO/0504246 (2005)
    On the fourier spectrum of symmetric boolean functions with applications to learning symmetric juntas
    RJ Lipton
    E. Markakis
    NK Vishnoi
    Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on, pp. 112-119
    Randomized truthful auctions of digital goods are randomizations over truthful auctions
    V.V. Vazirani
    Proceedings of the 5th ACM conference on Electronic commerce (2004), pp. 120-124
    Randomized time-space tradeoffs for directed graph connectivity
    P. Gopalan
    R.J. Lipton
    Lecture notes in computer science (FSTTCS) (2003), pp. 208-216
    Playing large games using simple strategies
    R.J. Lipton
    E. Markakis
    Proceedings of the 4th ACM conference on Electronic commerce (2003), pp. 36-41
    Caching with expiration times
    P. Gopalan
    H. Karloff
    M. Mihail
    N. Vishnoi
    Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (2002), pp. 540-547
    Keeping Track of the Latest Gossip in Shared Memory Systems
    B. Adsul
    M. Sohoni
    Lecture notes in computer science (FSTTCS) (2000), pp. 477-488