Darrell Hoy

STOC Conference 2018 Conference Paper

A tighter welfare guarantee for first-price auctions

• Darrell Hoy
• Samuel Taggart
• Zihe Wang 0001

This paper proves that the welfare of the first price auction in Bayes-Nash equilibrium is at least a .743-fraction of the welfare of the optimal mechanism assuming agents’ values are independently distributed. The previous best bound was 1−1/ e ≈.63, derived using smoothness, the standard technique for reasoning about welfare of games in equilibrium. In the worst known example, the first price auction achieves a ≈.869-fraction of the optimal welfare, far better than the theoretical guarantee. Despite this large gap, it was unclear whether the 1−1/ e bound was tight. We prove that it is not. Our analysis eschews smoothness, and instead uses the independence assumption on agents’ value distributions to give a more careful accounting of the welfare contribution of agents who win despite not having the highest value.

NeurIPS Conference 2017 Conference Paper

Welfare Guarantees from Data

• Darrell Hoy
• Denis Nekipelov
• Vasilis Syrgkanis

Analysis of efficiency of outcomes in game theoretic settings has been a main item of study at the intersection of economics and computer science. The notion of the price of anarchy takes a worst-case stance to efficiency analysis, considering instance independent guarantees of efficiency. We propose a data-dependent analog of the price of anarchy that refines this worst-case assuming access to samples of strategic behavior. We focus on auction settings, where the latter is non-trivial due to the private information held by participants. Our approach to bounding the efficiency from data is robust to statistical errors and mis-specification. Unlike traditional econometrics, which seek to learn the private information of players from observed behavior and then analyze properties of the outcome, we directly quantify the inefficiency without going through the private information. We apply our approach to datasets from a sponsored search auction system and find empirical results that are a significant improvement over bounds from worst-case analysis.

AAAI Conference 2015 Conference Paper

Approximately Optimal Risk-Averse Routing Policies via Adaptive Discretization

• Darrell Hoy
• Evdokia Nikolova

Mitigating risk in decision-making has been a longstanding problem. Due to the mathematical challenge of its nonlinear nature, especially in adaptive decisionmaking problems, finding optimal policies is typically intractable. With a focus on efficient algorithms, we ask how well we can approximate the optimal policies for the difficult case of general utility models of risk. Little is known about efficient algorithms beyond the very special cases of linear (risk-neutral) and exponential utilities since general utilities are not separable and preclude the use of traditional dynamic programming techniques. In this paper, we consider general utility functions and investigate efficient computation of approximately optimal routing policies, where the goal is to maximize the expected utility of arriving at a destination around a given deadline. We present an adaptive discretization variant of successive approximation which gives an -optimal policy in polynomial time. The main insight is to perform discretization at the utility level space, which results in a nonuniform discretization of the domain, and applies for any monotone utility function.

SODA Conference 2009 Conference Paper

Equilibria of atomic flow games are not unique

• Umang Bhaskar
• Lisa Fleischer
• Darrell Hoy
• Chien-Chung Huang 0001