[Theory] 7/29 Talks at TTIC: Hedyeh Beyhaghi, Cornell University

[Mary Marre]

*When:*      Monday, July 29th at 11:00 am



*Where:*     TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526



*Who: *       Hedyeh Beyhaghi, Cornell University



*Title:        *Optimal (and Benchmark-Optimal) Competition Complexity for
Additive Buyers over Independent Items

*Abstract: *The Competition Complexity of an auction setting refers to the
number of additional bidders necessary in order for the (deterministic,
prior-independent, dominant strategy truthful) Vickrey-Clarke-Groves
mechanism to achieve greater revenue than the (randomized, prior-dependent,
Bayesian-truthful) optimal mechanism without the additional bidders. We
prove that the competition complexity of n bidders with additive valuations
over m independent items is at most n(ln(1+m/n)+2), and also at most 9
sqrt(nm). When n<m, the first bound is optimal up to constant factors, even
when the items are i.i.d. and regular. When n>m, the second bound is
optimal for the benchmark introduced in [EdenFFTW17a] up to constant
factors, even when the items are i.i.d. and regular. We further show that,
while the Eden et al. benchmark is not necessarily tight in the n>m regime,
the competition complexity of n bidders with additive valuations over even
2 i.i.d. regular items is indeed ω(1). Our main technical contribution is a
reduction from analyzing the Eden et al. benchmark to proving stochastic
dominance of certain ransom variables.

*Host:* Avrim Blum <avrim at ttic.edu>




Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20190722/3f75b0c5/attachment.html>