Samuel Taggart

Ph.D Candidate
Department of Electrical Engineering and Computer Science
Northwestern University
email: <First Name>p<Last Name>@gmail.com

Curriculum Vitae

I'm a fifth-year PhD student in Northwestern University's Theory Group, advised by Jason Hartline. I graduated from Oberlin College in 2012 with bachelor's degrees in Mathematics and Violin Performance. I try to keep the latter up to snuff while I pursue my love for the former professionally.

Research Interests

I'm most excited by problems that combine microeconomic theory with algorithms. This includes, but is certainly not limited to, auctions, pricing, and voting. Some current projects are below. I'm also an enthusiastic student of the pedagogy of mathematics, algorithms, and computer science.

Working Papers

Non-Revelation Mechanism Design. (arXiv) (with Jason Hartline) We consider mechanism design and redesign for markets like Internet advertising where many frequent, small transactions are organized by a principal. Mechanisms for these markets rarely have truthtelling equilibria. We identify a family of winner-pays-bid mechanisms for such markets that exhibit three properties. First, equilibria in these mechanisms are simple. Second, the mechanisms' parameters are easily reoptimized from the bid data that the mechanism generates. Third, the performance of mechanisms in the family are near the optimal performance possible by any mechanism (not necessarily within the family). Our mechanisms are based on batching across multiple iterations of an auction environment, and our approximation bound is asymptotically optimal, with loss inversely proportional to the cube root of the number of iterations batched.

Repeated Sales with Multiple Strategic Buyers. In a market with repeated sales of a single item to a single buyer, prior work has established the existence of a zero-revenue perfect Bayesian equilibrium in the absence of a commitment device for the seller. We show, via a folk-theorem style argument, that in fact almost any revenue can be achieved in equilibrium, and that the zero revenue equilibrium uniquely survives natural refinements. This establishes that single-buyer markets without commitment are subject to market failure. Our main result shows this market failure depends crucially on the assumption of a single buyer; the presence of multiple buyers allows the seller to approximate the revenue that is possible with commitment. In a setting with multiple buyers, we construct an intuitive equilibrium that survives our refinements in which the seller learns from purchasing behavior and obtains a constant factor of the per-round Myerson optimal revenue. Moreover, we describe a simple and computationally tractable pricing algorithm for the seller that achieves this approximation when buyers best-respond.


Price of Anarchy for Auction Revenue. with J. Hartline and D. Hoy. EC 2014. arXiv

The Complexity of Pebbling in Diameter Two Graphs. with C. Cusack, T. Lewis, and D. Simpson. SIAM J. Discrete Math 2012. PDF

The Price of Civil Society. with R. Buehler, Z. Goldman, D. Libben-Nowell, Y. Pei, J Quadri, A. Sharp, T. Wexler, and K. Woods. WINE 2011. PDF