Gagan Goel

Gagan Goel

Authored Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    Preview abstract In this survey, we summarize recent developments in research fueled by the growing adoption of automated bidding strategies in online advertising. We explore the challenges and opportunities that have arisen as markets embrace this autobidding and cover a range of topics in this area, including bidding algorithms, equilibrium analysis and efficiency of common auction formats, and optimal auction design. View details
    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 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