Jump to Content
Gagan Goel

Gagan Goel

Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, desc
  • Year
  • Year, desc
    Preview abstract Constraints on agent's ability to pay play a major role in auction design for any setting where the magnitude of financial transactions is sufficiently large. Those constraints have been traditionally modeled in mechanism design as hard budget, i.e., mechanism is not allowed to charge agents more than a certain amount. Yet, real auction systems (such as Google AdWords) allow more sophisticated constraints on agents' ability to pay, such as average budgets. In this work, we investigate the design of Pareto optimal and incentive compatible auctions for agents with constrained quasi-linear utilities, which captures more realistic models of liquidity constraints that the agents may have. Our result applies to a very general class of allocation constraints known as polymatroidal environments, encompassing many settings of interest such as multi-unit auctions, matching markets, video-on demand and advertisement systems. Our design is based Ausubel's clinching framework. Incentive compatibility and feasibility with respect to ability-to-pay constraints are direct consequences of the clinching framework. Pareto-optimality, on the other hand, is considerably more challenging, since the no-trade condition that characterizes it depends not only on whether agents have their budgets exhausted or not, but also on prices {at} which the goods are allocated. In order to get a handle on those prices, we introduce novel concepts of dropping prices and saturation. These concepts lead to our main structural result which is a characterization of the tight sets in the clinching auction outcome and its relation to dropping prices. View details
    Preview abstract Auctions for perishable goods such as internet ad inventory need to make real-time allocation and pricing decisions as the supply of the good arrives in an online manner, without knowing the entire supply in advance. These allocation and pricing decisions get complicated when buyers have some global constraints. In this work, we consider a multi-unit model where buyers have global {\em budget} constraints, and the supply arrives in an online manner. Our main contribution is to show that for this setting there is an individually-rational, incentive-compatible and Pareto-optimal auction that allocates these units and calculates prices on the fly, without knowledge of the total supply. We do so by showing that the Adaptive Clinching Auction satisfies a {\em supply-monotonicity} property. We also analyze and discuss, using examples, how the insights gained by the allocation and payment rule can be applied to design better ad allocation heuristics in practice. Finally, while our main technical result concerns multi-unit supply, we propose a formal model of online supply that captures scenarios beyond multi-unit supply and has applications to sponsored search. We conjecture that our results for multi-unit auctions can be extended to these more general models. View details
    Preview abstract We revisit the classic problem of fair division from a mechanism design perspective, using Proportional Fairness as a benchmark. In particular, we aim to allocate a collection of divisible items to a set of agents while incentivizing the agents to be truthful in reporting their valuations. For the very large class of homogeneous valuations, we design a truthful mechanism that provides every agent with at least 0.368 fraction of her Proportionally Fair valuation. To complement this result, we show that no truthful mechanism can guarantee more than a 0.5 fraction, even for the restricted class of additive linear valuations. We also propose another mechanism for additive linear valuations that works really well when every item is highly demanded. To guarantee truthfulness, our mechanisms discard a carefully chosen fraction of the allocated resources; we conclude by uncovering interesting connections between our mechanisms and known mechanisms that use money instead. View details
    Budget-Constrained Auctions with Heterogeneous Items
    Sayan Bhattacharya
    Sreenivas Gollapudi
    Kamesh Munagala
    Theory of Computing, vol. 8 (2012), pp. 429-460
    Preview abstract We present the first approximation algorithms for designing revenue-optimal incentive-compatible mechanisms in the following setting: There are multiple (heterogeneous) items, and bidders have arbitrary demand and budget constraints (and additive valuations). Furthermore, the type of a bidder (which specifies her valuations for each item) is private knowledge, and the types of different bidders are drawn from publicly known mutually independent distributions. Our mechanisms are surprisingly simple. First, we assume that the type of each bidder is drawn from a discrete distribution with polynomially bounded support size. This restriction on the type-distribution, however, allows the random variables corresponding to a bidder’s valuations for different items to be arbitrarily correlated. In this model, we describe a sequential all-pay mechanism that is truthful in expectation and Bayesian incentive compatible. The outcome of our all-pay mechanism can be computed in polynomial time, and its revenue is a 4-approximation to the revenue of the optimal truthful-in-expectation Bayesian incentive-compatible mechanism. Next, we assume that the valuations of each bidder for different items are drawn from mutually independent discrete distributions satisfying the monotone hazard-rate condition. In this model, we present a sequential posted-price mechanism that is universally truthful and incentive compatible in dominant strategies. The outcome of the mechanism is computable in polynomial time, and its revenue is a O(1)-approximation to the revenue of the optimal truthful-in-expectation Bayesian incentive-compatible mechanism. If the monotone hazard-rate condition is removed, then we show a logarithmic approximation, and we complete the picture by proving that no sequential posted-price scheme can achieve a sub-logarithmic approximation. Finally, if the distributions are regular, and if the space of mechanisms is restricted to sequential posted-price schemes, then we show that there is a O(1)-approximation within this space. Our results are based on formulating novel LP relaxations for these problems, and developing generic rounding schemes from first principles. View details
    Preview abstract 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 these 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 multiunit auctions with decreasing marginal utilities in the presence of budget constraints. 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
    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
    A Perfect Price Discrimination Market Model with Production, and a (Rational) Convex Program for it.
    Vijay Vazirani
    SAGT (2010)
    Budget constrained auctions with heterogeneous items
    Sayan Bhattacharya
    Sreenivas Gollapudi
    Kamesh Munagala
    STOC (2010), pp. 379-388
    Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions
    Pushkar Tripathi
    Lei Wang
    FSTTCS (2010)
    On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
    Deeparnab Chakrabarty
    SIAM J. Comput., vol. 39 (2010), pp. 2189-2211
    Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
    Chinmay Karande
    Pushkar Tripathi
    Lei Wang
    FOCS, IEEE (2009), pp. 755-764
    Efficiency, Fairness and Competitiveness in Nash Bargaining Games
    Deeparnab Chakrabarty
    Vijay V. Vazirani
    Lei Wang
    Changyuan Yu
    WINE (2008), pp. 498-505
    On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
    Deeparnab Chakrabarty
    FOCS (2008), pp. 687-696
    Towards Topology Aware Networks
    Christos Gkantsidis
    Milena Mihail
    Amin Saberi
    INFOCOM (2007), pp. 2591-2595