Bo Waggoner

Maxwell-Dworkin 219
33 Oxford Street
Cambridge, MA 02138

I am a Ph.D. candidate at Harvard University in Computer Science (what is Computer Science?).

My research interests are mainly in theoretical CS, artificial intelligence, and mechanism design. I am a part of Harvard's EconCS group (what is EconCS?), advised by Yiling Chen. I graduated from Duke University in 2011 studying math and computer science. I'm an avid runner.
Page last modified: 2015-01-20.
Contents: Research Interests, Teaching, Publications, Talks, Writeups

See also: Running page, Misc page

Research Interests

Mostly in theoretical CS and microeconomics, especially mechanism design (from an algorithmic perspective).

Specific topics: algorithmic auction design, information elicitation (particularly in crowdsourcing settings, from both game-theoretic and machine-learning perspectives), online algorithms (particularly online bipartite matching problems), differential privacy, computational social choice (e.g. fair division, voting), computational learning theory (e.g. testing of discrete distributions).


Fall 2013:
CS 284r, Incentives and Information in Networks. with Professor Yaron Singer.
Teaching Fellow.

Fall 2012: CS 121, Intro to Theory of Computation. with Professor Salil Vadhan.
Teaching Fellow.


Fair Information Sharing for Treasure Hunting
Yiling Chen, Kobbi Nissim, and Bo Waggoner.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15).
    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
Bo Waggoner.
Proceedings of the Sixth Conference on Innovations in Theoretical Computer Science (ITCS-15).
    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).
    Also available on arxiv.

Online Stochastic Matching with Unequal Probabilities
Aranyak Mehta, Bo Waggoner, and Morteza Zadimoghaddam.
Proceedings of the Twenty-Sixth ACM-SIAM Symposium on Discrete Algorithms (SODA-15).
    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 unqual (but vanishing) edge probabilities. The approximation ratio is 0.534.

Output Agreement Mechanisms and Common Knowledge
Bo Waggoner and Yiling Chen.
Proceedings of the Second AAAI Conference on Human Computation (HCOMP-14).
    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.
Yang Cai, Mohammad Mahdian, Aranyak Mehta, and Bo Waggoner.
Proceedings of the Ninth Conference on Web and Internet Economics (WINE-13).
    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.
    Also available on arxiv.

Evaluating Resistance to False-Name Manipulations in Elections.
Bo Waggoner, Lirong Xia, and Vincent Conitzer.
Proceedings of the Twenty-Sixth AAAI Conference on Artifical Intelligence (AAAI-12).
    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.


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

2015-01-06. Online Stochastic Matching with Unequal Probabilities.
SODA 2015, San Diego, CA.
    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.
    slides (pdf), slides and notes (pdf).

2013-12-13. Designing Markets for Daily Deals.
The 9th Conference on Web and Internet Economics (WINE-13), Cambridge, MA.
    slides (Google presentation, with notes), slides (pdf), slides and notes (pdf).

2013-06-16. Information Elicitation Sans Verification.
The 3rd Workshop on Social Computing and User-Generated Content (SCUGC), at EC-13, Philadelphia, PA.
    slides (pdf).

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


Useful Tips, Tricks, and Techniques. A list-in-progress I am compiling of some of the most common and useful approximations, inequalities, bounds, proof techniques, etc. for theoretical computer science.

Jumpstart GLPK. Intro by examples to the GNU Linear Programming Kit's stand-alone LP solver, glpsol.
    Supplementary: example0.mod, example1.mod.

Jumpstart Flex/Bison. Basic examples and how-to for flex and bison, the lexing and parsing tools for writing compilers using C or C++ (the free versions of lex and yacc).
    Supplementary: all example files (zip), example0.l, example0.y, example1.l, example1.y.

Jumpstart LaTeX. Intro by examples to LaTeX.
    Supplementary: all example files (zip), example0.tex, example1.tex, example2.tex, bibexample.tex, bibexample.bib.

Jumpstart Linux. Quick intro to Linux and the command line for the absolute beginner.

Possible misspellings of my name include "Bo Wagner" and "Bo Wagoner".