Research Area
Year Published

20 Results

November 10, 2019

Adversarial Bandits with Knapsacks

Symposium on Foundations of Computer Science (FOCS)

We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling.

By: Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, Aleksandrs Slivkins

July 1, 2019

Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent

International Conference on Very Large Databases (VLDB)

Motivated by performance optimization of large-scale graph processing systems that distribute the graph across multiple machines, we consider the balanced graph partitioning problem. Compared to most of the previous work, we study the multi-dimensional variant in which balance according to multiple weight functions is required.

By: Dmitrii Avdiukhin, Sergey Pupyrev, Grigory Yaroslavtsev

June 26, 2019

Pacing Equilibrium in First-Price Auction Markets

ACM Conference on Economics and Computation (EC)

In the isolated auction of a single item, second price is often preferable to first price in properties of theoretical interest. Unfortunately, single items are rarely sold in true isolation, so considering the broader context is critical when adopting a pricing strategy. In this paper, we show that this context is important in a model centrally relevant to Internet advertising: when items (ad impressions) are individually auctioned within the context of a larger system that is managing budgets, theory offers surprising support for using a first price auction to sell each individual item.

By: Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Eric Sodomka, Nicolas Stier, Chris Wilkens

June 13, 2019

Discovering Context Effects from Raw Choice Data

International Conference on Machine Learning (ICML)

Many applications in preference learning assume that decisions come from the maximization of a stable utility function. Yet a large experimental literature shows that individual choices and judgements can be affected by “irrelevant” aspects of the context in which they are made. An important class of such contexts is the composition of the choice set. In this work, our goal is to discover such choice set effects from raw choice data.

By: Arjun Seshadri, Alexander Peysakhovich, Johan Ugander

May 14, 2019

Online Learning for Measuring Incentive Compatibility in Ad Auctions

The Web Conference

In this paper we investigate the problem of measuring end-to-end Incentive Compatibility (IC) regret given black-box access to an auction mechanism. Our goal is to 1) compute an estimate for IC regret in an auction, 2) provide a measure of certainty around the estimate of IC regret, and 3) minimize the time it takes to arrive at an accurate estimate.

By: Zhe Feng, Okke Schrijvers, Eric Sodomka

April 3, 2019

Learning Existing Social Conventions via Observationally Augmented Self-Play

Conference on Artificial Intelligence, Ethics, and Society (AIES)

In order for artificial agents to coordinate effectively with people, they must act consistently with existing conventions (e.g. how to navigate in traffic, which language to speak, or how to coordinate with teammates). A group’s conventions can be viewed as a choice of equilibrium in a coordination game. We consider the problem of an agent learning a policy for a coordination game in a simulated environment and then using this policy when it enters an existing group.

By: Adam Lerer, Alexander Peysakhovich

February 21, 2019

Improving Treatment Effect Estimators Through Experiment Splitting

The Web Conference (WWW)

We present a method for implementing shrinkage of treatment effect estimators, and hence improving their precision, via experiment splitting.

By: Dominic Coey, Tom Cunningham

December 15, 2018

Multiplicative Pacing Equilibria in Auction Markets

The 14th Conference on Web and Internet Economics (WINE)

Budgets play a significant role in real-world sequential auction markets such as those implemented by Internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions so budgets are used for the best opportunities. This paper considers a smoothing procedure that relies on pacing multipliers: for each bidder, the platform applies a factor between 0 and 1 that uniformly scales the bids across all auctions.

By: Vincent Conitzer, Christian Kroer, Eric Sodomka, Nicolas Stier

November 7, 2018

Social Connectedness: Measurement, Determinants, and Effects

Journal of Economic Perspectives

Social networks can shape many aspects of social and economic activity: migration and trade, job-seeking, innovation, consumer preferences and sentiment, public health, social mobility, and more. In turn, social networks themselves are associated with geographic proximity, historical ties, political boundaries, and other factors.

By: Michael Bailey, Rachel Cao, Theresa Kuchler, Johannes Stroebel, Arlene Wong

October 9, 2018

Trajectory Optimization of Solar-Powered High-Altitude Long Endurance Aircraft

Solar-powered high-altitude long endurance aircraft that harvest and store solar energy can fly indefinitely if they are able to close a 24-hour energy cycle. Perpetual endurance is possible when energy consumption does not exceed energy storage.

By: Jack Marriott, Birce Tezel, Zhang Liu, Nicolas Stier