[Theory] REMINDER: 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>*


On Sun, Jul 28, 2019 at 8:24 PM Mary Marre <mmarre at ttic.edu> wrote:

> *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>*
>
>
> On Mon, Jul 22, 2019 at 4:10 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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/20190729/bd68c637/attachment-0001.html>