Gagan Goel

AAAI Conference 2019 Conference Paper

Pareto Efficient Auctions with Interest Rates

• Gagan Goel
• Vahab Mirrokni
• Renato Paes Leme

We consider auction settings in which agents have limited access to monetary resources but are able to make payments larger than their available resources by taking loans with a certain interest rate. This setting is a strict generalization of budget constrained utility functions (which corresponds to infinite interest rates). Our main result is an incentive compatible and Pareto-efficient auction for a divisible multi-unit setting with 2 players who are able to borrow money with the same interest rate. The auction is an ascending price clock auction that bears some similarities to the clinching auction but at the same time is a considerable departure from this framework: allocated goods can be de-allocated in future and given to other agents and prices for previously allocated goods can be raised.

FOCS Conference 2014 Conference Paper

Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets

• Nima Anari
• Gagan Goel
• Afshin Nikzad

In this paper we consider a mechanism design problem in the context of large-scale crowdsourcing markets such as Amazon's Mechanical Turk mturk, ClickWorker clickworker, CrowdFlower crowdflower. In these markets, there is a requester who wants to hire workers to accomplish some tasks. Each worker is assumed to give some utility to the requester on getting hired. Moreover each worker has a minimum cost that he wants to get paid for getting hired. This minimum cost is assumed to be private information of the workers. The question then is -- if the requester has a limited budget, how to design a direct revelation mechanism that picks the right set of workers to hire in order to maximize the requester's utility? We note that although the previous work (Singer (2010) chen et al. (2011)) has studied this problem, a crucial difference in which we deviate from earlier work is the notion of large-scale markets that we introduce in our model. Without the large market assumption, it is known that no mechanism can achieve a competitive ratio better than 0. 414 and 0. 5 for deterministic and randomized mechanisms respectively (while the best known deterministic and randomized mechanisms achieve an approximation ratio of 0. 292 and 0. 33 respectively). In this paper, we design a budget-feasible mechanism for large markets that achieves a competitive ratio of 1 - 1/e ≃ 0. 63. Our mechanism can be seen as a generalization of an alternate way to look at the proportional share mechanism, which is used in all the previous works so far on this problem. Interestingly, we can also show that our mechanism is optimal by showing that no truthful mechanism can achieve a factor better than 1 - 1/e, thus, fully resolving this setting. Finally we consider the more general case of submodular utility functions and give new and improved mechanisms for the case when the market is large.

SODA Conference 2013 Conference Paper

Clinching Auction with Online Supply

• Gagan Goel
• Vahab Mirrokni
• Renato Paes Leme

AAMAS Conference 2013 Conference Paper

Positive Results for Mechanism Design without Money

• Richard Cole
• Vasilis Gkatzelis
• Gagan Goel

Consider the problem of allocating multiple divisible goods to two agents in a strategy-proof fashion without the use of payments or priors. Previous work [1, 2] has aimed at implementing allocations that are competitive with respect to an appropriately defined measure of social welfare. These results have mostly been negative, proving that no dictatorial mechanism can achieve an approximation factor better than 0. 5, and leaving open the question of whether there exists a non-dictatorial mechanism that outperforms this bound. We provide a positive answer to this question by presenting an interesting non-dictatorial mechanism that achieves an approximation factor of 2/3 for this measure of social welfare. In proving this bound we also touch on the issue of fairness: we show that the proportionally fair solution, a well known fairness concept for money-free settings, is highly competitive with respect to social welfare. We then show how to use the proportionally fair solution to design our non-dictatorial strategy-proof mechanism.

FOCS Conference 2012 Conference Paper

Matching with Our Eyes Closed

• Gagan Goel
• Pushkar Tripathi

Motivated by an application in kidney exchange, we study the following query-commit problem: we are given the set of vertices of a non-bipartite graph G. The set of edges in this graph are not known ahead of time. We can query any pair of vertices to determine if they are adjacent. If the queried edge exists, we are committed to match the two endpoints. Our objective is to maximize the size of the matching. This restriction in the amount of information available to the algorithm constraints us to implement myopic, greedy-like algorithms. A simple deterministic greedy algorithm achieves a factor 1/2 which is tight for deterministic algorithms. An important open question in this direction is to give a randomized greedy algorithm that has a significantly better approximation factor. This question was first asked almost 20 years ago by Dyer and Frieze [9] where they showed that a natural randomized strategy of picking edges uniformly at random doesn't help and has an approximation factor of 1/2 + o(1). They left it as an open question to devise a better randomized greedy algorithm. In subsequent work, Aronson, Dyer, Frieze, and Suen [2] gave a different randomized greedy algorithm and showed that it attains a factor 0. 5 + o where o is 0. 0000025. In this paper we propose and analyze a new randomized greedy algorithm for finding a large matching in a general graph and use it to solve the query commit problem mentioned above. We show that our algorithm attains a factor of at least 0. 56, a significant improvement over 0. 50000025. We also show that no randomized algorithm can have an approximation factor better than 0. 7916 for the query commit problem. For another large and interesting class of randomized algorithms that we call vertex-iterative algorithms, we show that no vertex iterative algorithm can have an approximation factor better than 0. 75.

STOC Conference 2012 Conference Paper

Polyhedral clinching auctions and the adwords polytope

• Gagan Goel
• Vahab Mirrokni
• Renato Paes Leme

A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting the budget constraints. Achieving this goal is particularly challenging in the presence of nontrivial combinatorial constraints over the set of feasible allocations. Toward this goal and motivated by AdWords auctions, we present an auction for polymatroidal environments satisfying the above properties. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots. We show that it is impossible to extend this result to generic polyhedral constraints. This also implies an impossibility result for multi-unit auctions with decreasing marginal utilities in the presence of budget constraints.

SODA Conference 2011 Conference Paper

Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations

• Gagan Aggarwal
• Gagan Goel
• Chinmay Karande
• Aranyak Mehta

STOC Conference 2010 Conference Paper

Budget constrained auctions with heterogeneous items

• Sayan Bhattacharya
• Gagan Goel
• Sreenivas Gollapudi
• Kamesh Munagala

In this paper, we present the first approximation algorithms for the problem of designing revenue optimal Bayesian incentive compatible auctions when there are multiple (heterogeneous) items and when bidders have arbitrary demand and budget constraints (and additive valuations). Our mechanisms are surprisingly simple: We show that a sequential all-pay mechanism is a 4 approximation to the revenue of the optimal ex-interim truthful mechanism with a discrete type space for each bidder, where her valuations for different items can be correlated. We also show that a sequential posted price mechanism is a O(1) approximation to the revenue of the optimal ex-post truthful mechanism when the type space of each bidder is a product distribution that satisfies the standard hazard rate condition. We further show a logarithmic approximation when the hazard rate condition is removed, and complete the picture by showing that achieving a sub-logarithmic approximation, even for regular distributions and one bidder, requires pricing bundles of items. Our results are based on formulating novel LP relaxations for these problems, and developing generic rounding schemes from first principles.

FOCS Conference 2009 Conference Paper

Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions

• Gagan Goel
• Chinmay Karande
• Pushkar Tripathi
• Lei Wang 0010

Applications in complex systems such as the Internet have spawned recent interest in studying situations involving multiple agents with their individual cost or utility functions. In this paper, we introduce an algorithmic framework for studying combinatorial problems in the presence of multiple agents with submodular cost functions. We study several fundamental covering problems (Vertex Cover, Shortest Path, Perfect Matching, and Spanning Tree) in this setting and establish tight upper and lower bounds for the approximability of these problems.

FOCS Conference 2008 Conference Paper

On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP

• Deeparnab Chakrabarty
• Gagan Goel

In this paper we consider the following maximum budgeted allocation (MBA) problem: Given a set of m indivisible items and n agents; each agent i willing to pay b ij on item j and with a maximum budget of B i, the goal is to allocate items to agents to maximize revenue. The problem naturally arises as auctioneer revenue maximization in budget-constrained auctions and as winner determination problem in combinatorial auctions when utilities of agents are budgeted-additive. We give a 3/4-approximation algorithm for MBA improving upon the previous best of sime0. 632[2, 10]. Our techniques are based on a natural LP relaxation of MBA and our factor is optimal in the sense that it matches the integrality gap of the LP. We prove it is NP-hard to approximate MBA to any factor better than 15/16, previously only NP-hardness was known [21, 17]. Our result also implies NP- hardness of approximating maximum submodular welfare with demand oracle to a factor better than 15/16, improving upon the best known hardness of 275/276[10]. Our hardness techniques can be modified to prove that it is NP-hard to approximate the Generalized Assignment Problem (GAP) to any factor better than 10/11. This improves upon the 422/423 hardness of [7, 9]. We use iterative rounding on a natural LP relaxation of MBA to obtain the 3/4-approximation. We also give a (3/4 - epsiv) -factor algorithm based on the primal-dual schema which runs in O(nm) time, for any constant epsiv > 0.

SODA Conference 2008 Conference Paper

Online budgeted matching in random input models with applications to Adwords

• Gagan Goel
• Aranyak Mehta