pic of Bo


I am mainly a "theorist" -- I think about models and prove theorems.

I am mostly interested in theoretical computer science -- what are the possibilities and limitations of algorithms? -- and game theory -- how do groups of agents make decisions? -- and artificial intelligence -- how can algorithms solve complex tasks? -- and machine learning -- how can algorithms predict future events using the past?

My main focus is probably in eliciting useful information from strategic agents. But I also have interests in some other topics and curiosity about many more!
a gif

Contents: Papers, Talks


Multi-Observation Elicitation (COLT 2017)
Sebastian Casalaina-Martin, Rafael Frongillo, Tom Morgan, Bo Waggoner
In elicitation, we ask an expert to make a prediction about a random variable, then observe its outcome and score their prediction. This paper considers (from a mostly machine-learning perspective) an extension to where we can observe multiple i.i.d. observations. This can give drastic improvements for eliciting some statistics that have large "elicitation complexity".

The Complexity of Stable Matchings Under Substitutable Preferences (AAAI 2017)
Yuan Deng, Debmalya Panigrahi, and Bo Waggoner
When computing a many-to-one stable matching, e.g. doctors to hospitals in the NRMP, hospitals must solve this problem: Given a set of doctors, what is my most-preferred subset? We show that this is a computationally hard problem even with substitutable preferences, but there is a simple additional assumption -- that hospitals can "verify" whether a set of doctors is preferred to all of its subsets -- that makes it efficiently-solvable, hence making stable matchings efficiently findable.


Acquiring and Aggregating Data from Strategic Sources (PhD Thesis)
Bo Waggoner
Some investigations into how to accomplish the title objective. Some key themes are how we can improve by allowing aggregation (what we know so far) to influence acquistion (what we want to learn); different approaches needed when treating information as e.g. data points versus opinions or beliefs; and challenges posed by strategic information sources. The intro is not too technical and summarizes some ideas; the main content is redundant with some of the below papers.

Informational Substitutes (FOCS 2016)
Yiling Chen and Bo Waggoner
Introduces a definition for when two pieces of information, "signals", are substitutes or complements. The definitions are natural from several perspectives; the main result is that they turn out to capture (respectively) "good" and "bad" equilibria of prediction markets. Also has some algorithmic applications to information acquisition under constraints.

Descending Price Optimally Coordinates Search (EC 2016 and more recent working paper)
Robert Kleinberg, Bo Waggoner, and E. Glen Weyl
Proposes a descending-price auction for settings in which bidders have some cost they must incur to inspect the item and learn their valuation. The challenge for welfare in this setting is to encourage "enough" of the "right" bidders to spend the inspection cost, without wasting many useless inspections. Combines "smoothness" with optimal search theory to prove welfare guarantees.

A Market Framework for Eliciting Private Data (NIPS 2015)
Bo Waggoner, Rafael Frongillo, and Jacob Abernethy
Designs a prediction-market like mechanism for "purchasing" information or data from the crowd. Gives a contest-like structure where participants' contributions collaboratively update a single collective hypothesis. Preserves differential privacy of contributions.
Spin-off note on Differentially Private, Classic Prediction Markets.

Low-Cost Learning via Active Data Procurement (EC 2015)
Jacob Abernethy, Yiling Chen, Chien-Ju Ho, and Bo Waggoner
Designs mechanisms/learning algorithms to purchase data from agents who arrive one by one. The key idea is to actively change the prices we offer based on the current state of the learning algorithm. Proves learning guarantees as a function of the budget constraint.
Supplementary: simulation code.

Fair Information Sharing for Treasure Hunting. (AAAI 2015)
Yiling Chen, Kobbi Nissim, and Bo Waggoner
Designs a mechanism for the following problem: A group of agents (e.g. pirates) each hold private information about the solution to a search problem (e.g. location of buried treasure); we want them to truthfully report to the mechanism, which then assigns search tasks fairly.

lp Testing and Learning of Discrete Distributions (ITCS 2015)
Bo Waggoner
Examines uniformity testing and learning of discrete distributions, given access to independent samples, under ℓp metrics. One result is that a 6-sided die is easier to test for fairness than a 2-sided coin, and a 52-card shuffler easier than the die, if the measure of fairness is ℓp with p > 4/3. In general, gives upper and lower bounds on number of samples needed (tight everywhere for learning and in many cases for uniformity testing).

Online Stochastic Matching with Unequal Probabilities (SODA 2015)
Aranyak Mehta, Bo Waggoner, and Morteza Zadimoghaddam.
Designs an algorithm for online bipartite matching when edges are labeled with a probability of success and the goal is to maximize the expected number of matches. Prior work considered the case where all edge probabilities are equal; we consider the general case with unequal (but vanishing) edge probabilities. The approximation ratio is 0.534.

Output Agreement Mechanisms and Common Knowledge (HCOMP 2014)
Bo Waggoner and Yiling Chen.
Considers equilibria of "output agreement" games, where two people get the same input and are asked to answer a question about it, rewarded based on how closely their answers agree. Rather than fully truthful, such games elicit "common knowledge" (though some subtleties arise).
Preceded by the following workshop version, containing essentially the same results with different presentation: Information Elicitation Sans Verification. Bo Waggoner and Yiling Chen. The 3rd Workshop on Social Computing and User-Generated Content (SCUGC-13), at EC-13.

Designing Markets for Daily Deals (WINE 2013)
Yang Cai, Mohammad Mahdian, Aranyak Mehta, and Bo Waggoner.
Designs auctions for maximizing welfare when the bidders, like marketers on a Daily Deals site (e.g. Groupon), have private information about how valuable their deal is to consumers in the form of beliefs or predictions. We elicit this information truthfully, select an outcome, and assign payments to maximize a combination of bidder, auctioneer, and consumer welfare.

Evaluating Resistance to False-NameManipulations in Elections (AAAI 2012)
Bo Waggoner, Lirong Xia, and Vincent Conitzer.
Considers voting when voters might cast multiple votes ("false-name manipulation"). We consider how best to design a deterrent against such manipulation in order to maximize the probability that the outcome of the election matches the true population preference, and how to statistically test whether this occurred.
Supplementary: simulation code.


2017-07-09. Multi-Observation Elicitation.
COLT, Amsterdam. 10min.
slides (pdf)

2017-06-16. Bitcoin, blockchain, etc.
UPenn theory group, informal discussion. (Warning: I am not a Bitcoin expert, just wanted to describe some basics.)
slides (pdf).

2017-01-04. On Information Elicitation and Mechanism Design.
Young Researchers - EC. Tel Aviv, Israel. 30min.
slides (pdf).

2016-11-16. Prediction Market Equilibria via Substitutes and Complements.
INFORMS, Nashville, TN. 20min.
slides (pdf).

2016-11-09. Informational Substitutes.
TCS+ video series, The Internet. 60min.
Video (61min).
slides (pdf), slides (Google presentation).

2016-10-19. Some Aspects of Acquiring and Aggregating Information.
Career Networking Conference (CNC), Boston, MA. 15min.
slides (pdf).

2016-10-09. Informational Substitutes.
FOCS, New Brunswick, New Jersey. 20min.
slides (pdf).

2016-09-27. What Dice Are These?
University of Colorado - Boulder. 60min.
Chalk talk.

2016-07-26. Descending Price Optimally Coordinates Search.
EC, Maastricht, Netherlands. 20min.
slides (Google presentation), slides (pdf).

2016-07-24. Informational Substitutes: Definitions and Design.
GAMES, Maastricht, Netherlands. 20min.
slides (pdf).

2016-05-27. (Thesis Defense) Acquiring and Aggregating Information from Strategic Sources.
Harvard. 60min.
slides (Google presentation), slides (pdf).

2016-03-16. Some Approaches for Information Acquisition and Aggregation.
UPenn, Philadelphia PA. 60min.
slides (Google presentation), slides (pdf).

2015-10-14. Low-Cost Learning via Active Data Procurement.
Microsoft Research NYC.
slides (Google presentation), slides (pdf).
Almost identical to the version below.

2015-09-09. Low-Cost Learning via Active Data Procurement.
Duke CSEcon Group.
slides (Google presentation), slides (pdf).

2015-06-19. Low-Cost Learning via Active Data Procurement.
EC 2015, Portland, Oregon. 18min.
slides (Google presentation), slides (pdf).

2015-02-06. Fair Information Sharing for Treasure Hunting.
Harvard EconCS group. 60min.
slides and notes (Google presentation), slides (pdf).
12min version given at AAAI 2015, 29 January 2015, Austin, Texas.

2015-01-13. lp Testing and Learning of Discrete Distributions.
ITCS 2015, Rehovot, Israel. 20min.
slides (pdf), slides with notes (pdf).

2015-01-06. Online Stochastic Matching with Unequal Probabilities.
SODA 2015, San Diego, CA. 20min.
slides (Google presentation), slides (pdf).

2014-01-10. Toward Buying Labels from the Crowd.
Indo-US Lectures Week in Machine Learning, Game Theory, and Optimization, Bangalore. 20min.
slides (pdf), slides and notes (pdf).

2013-12-13. Designing Markets for Daily Deals.
WINE 2013, Cambridge, MA. 20min.
slides (Google presentation, with notes), slides (pdf), slides and notes (pdf).

2013-06-16. Information Elicitation Sans Verification.
Workshop on Social Computing and User-Generated Content (SCUGC), at EC 2013, Philadelphia, PA. 20min.
slides (pdf).
Different version given at HCOMP 2014, 4 November 2014, Pittsburgh, PA.

2012-03-26. Evaluating Resistance to False-Name Manipulations in Elections.
Harvard EconCS Group. 45min.
slides (pptx), slides (pdf), slides and notes (pdf).