Title: First Price Auction is 1 - 1/e^2 Efficient
Speaker: Prof. Pinyan Lu, ITCS@SUFE, China
Date/Time: Oct. 22, 2022
Abstract: In this talk, I will present my recent joint work with Yaonan Jin which settles the tight PoA for First Price auction. We prove that the price of anarchy (PoA) of First Price Auctions is 1−1/e^2 ≈0.8647, closing the gap between the best-known bounds [0.7430,0.8689].
Bio: Pinyan Lu is a professor and the founding director of Institute for Theoretical Computer Science at Shanghai University of Finance and Economics (ITCS@SUFE). Before joining SUFE, he was a researcher at Microsoft Research. He studied in Tsinghua University (BS (2005) and PhD (2009) both in Computer Science). He is interested in theoretical computer science, including complexity theory, algorithms design and algorithmic game theory. Currently, his research is mainly focused on complexity and approximability of counting problems, and algorithmic mechanism design. Pinyan is the recipient of a number of awards including ICCM Silver Medal of Mathematics, Distinguished Membership of ACM and CCF, CCF Young Scientist award, Best Paper Award from ICALP 2007, FAW 2010, ISAAC 2010 and so on. He is the PC chairs for FAW-AAIM 2012, WINE 2017, FAW 2018, ISAAC 2019 and so on, and PC members for STOC, FOCS, SODA and a dozen of international conferences. He is an Editorial Board Member of the “Information and Computation” and “Theoretical Computer Science”.
Title: Instability of backoff protocols with arbitrary arrival rates
Speaker: Professor Leslie Ann Goldberg, University of Oxford, UK
Date/Time: Oct. 22, 2022
Abstract: In contention resolution, multiple processors are trying to coordinate to send discrete messages through a shared channel with sharply limited communication. If two processors inadvertently send at the same time, the messages collide and are not transmitted successfully. A contention-resolution protocol is a randomised algorithm that the processors use to decide when to send (and when to wait because the channel is too busy). A famous example is a “backoff protocol”. A backoff protocol is associated with a sequence p = p_0, p_1, p_2,… of real numbers in the range (0,1]. If a processor is trying to send a message, and that message has already collided k times, then on the next step it sends with probability p_k and it instead waits with probability 1-p_k. The Ethernet protocol is roughly based on binary exponential backoff, which is the backoff protocol with p_k = 2^(-k). The operation of a multiple-access channel is modelled as a stochastic process in discrete time --- messages arrive according to a probability distribution with an arrival rate lambda. An acknowledgement-based protocol is a contention-resolution protocol (such as a backoff protocol) where the only feedback that a processor gets is whether or not its own message got through --- it does not listen to the channel except when it sends. These protocols are suitable for applications such as cloud computing. In this setting, the assumption is that processors arrive according to a Poisson distribution, each with a single message to send to the channel. A contention-resolution protocol is “stable” if the corresponding process is positive recurrent (informally, this means that there is a stationary distribution, so the accumulation of messages over time is controlled, at least in expectation). It is widely conjectured that there is no stable acknowledgement-based protocol for any positive arrival rate. Towards this, Aldous proved (IEEE Trans Inf Theory 1987) that binary exponential backoff is not stable for any positive arrival rate. Despite exciting recent results for full-sensing protocols which assume greater listening capabilities of the processors (see e.g. Bender et al. STOC 2020 or Chen et al. PODC 2021), this foundational question remains open even for backoff protocols unless the arrival rate is at least 0.42 (Goldberg et al. SICOMP 2004). In this talk, I describe new work with John Lapinskas where we prove the conjecture for all backoff protocols outside of a tightly-constrained special case. I will also set out the remaining technical obstacles to a full proof of the conjecture.
Bio: Leslie Ann Goldberg is a professor of computer science at the University of Oxford and a Fellow of St Edmund Hall, Oxford. Her research concerns the design and analysis of algorithms for random sampling and approximate combinatorial enumeration. Prior to working at Oxford, her employers have included Sandia National Laboratories, the University of Warwick, and the University of Liverpool. Goldberg serves as editor-in-chief of the Journal of Discrete Algorithms, and has served as program chair of the algorithms track of the International Colloquium on Automata, Languages and Programming (ICALP) in 2008. She is a member of the Academia Europaea (MAE) and was awarded the Suffrage Science award in 2016.