# 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.
## Publications

**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