# Gagan Goel

### Research Areas

Authored Publications

Google Publications

Other Publications

Sort By

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 ﬁrst 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 speciﬁes 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 ﬁrst principles.
View details

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

Chinmay Karande

Proceedings of ACM-SIAM Symposium on Discrete Algorithms (2011)

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 ﬁrst 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

Preview
Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, SIAM, San Francisco (2008), pp. 982-991

Adwords Auctions with Decreasing Valuation Bids

Preview
Internet and Network Economics (WINE), Springer, San Diego (2007), pp. 335-340

A Perfect Price Discrimination Market Model with Production, and a (Rational) Convex Program for it.

Budget constrained auctions with heterogeneous items

Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions

Efficiency, Fairness and Competitiveness in Nash Bargaining Games

Towards Topology Aware Networks