<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><p class="gmail-m_1224414253470676018gmail-m_-2152759526496696495gmail-m_6990773674929763255gmail-m_3947158569005651454gmail-m_-6060531980912436720gmail-m_-5698796270993385318m_6700458045820563854gmail-m_427904505759088481gmail-m_496884293731504483gmail-m_4528131826496012784gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_5987474974647831651gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_9103776001042077600gmail-p1" style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Monday, July 29th at 11:00 am</font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>       </font></font>Hedyeh </font>Beyhaghi, Cornell University</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p></div><div class="gmail_default"><div><b>Title:        </b>Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items</div><div><br></div><div><b>Abstract: </b>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.</div><div><b><br></b></div><div><b>Host:</b> <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a></div><div><br></div><div><br></div><div><br></div></div></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Jul 22, 2019 at 4:10 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div style="font-size:small"><p class="gmail-m_1224414253470676018gmail-m_-2152759526496696495gmail-m_6990773674929763255gmail-m_3947158569005651454gmail-m_-6060531980912436720gmail-m_-5698796270993385318m_6700458045820563854gmail-m_427904505759088481gmail-m_496884293731504483gmail-m_4528131826496012784gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_5987474974647831651gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_9103776001042077600gmail-p1" style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Monday, July 29th at 11:00 am</font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>       </font></font>Hedyeh </font>Beyhaghi, Cornell University</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p></div><div style="font-size:small"><div><b>Title:        </b>Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items</div><div><br></div><div><b>Abstract: </b>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.</div><div><b><br></b></div><div><b>Host:</b> <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a></div><div><br></div><div><br></div><div><br></div><div><br></div></div><div><div dir="ltr" class="gmail-m_1224414253470676018gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div></div>