Timezone: »

 
Spotlight
Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues
Noga Alon · Moshe Babaioff · Yannai A. Gonczarowski · Yishay Mansour · Shay Moran · Amir Yehudayoff

Wed Dec 06 11:20 AM -- 11:25 AM (PST) @ Hall A
in Theory, Probabilistic Methods »

In this work we derive a variant of the classic Glivenko-Cantelli Theorem, which asserts uniform convergence of the empirical Cumulative Distribution Function (CDF) to the CDF of the underlying distribution. Our variant allows for tighter convergence bounds for extreme values of the CDF. We apply our bound in the context of revenue learning, which is a well-studied problem in economics and algorithmic game theory. We derive sample-complexity bounds on the uniform convergence rate of the empirical revenues to the true revenues, assuming a bound on the k'th moment of the valuations, for any (possibly fractional) k > 1. For uniform convergence in the limit, we give a complete characterization and a zero-one law: if the first moment of the valuations is finite, then uniform convergence almost surely occurs; conversely, if the first moment is infinite, then uniform convergence almost never occurs.

Author Information

Noga Alon (Tel Aviv University)
Moshe Babaioff (Microsoft Research)
Yannai A. Gonczarowski (The Hebrew University of Jerusalem and Microsoft Research)

Yannai Gonczarowski is a Ph.D. student at the Hebrew University of Jerusalem, where his advisors are Noam Nisan and Sergiu Hart. He holds an M.Sc. in Mathematics and a B.Sc. in Mathematics and Computer Science from the same institution. He is also a professionally trained opera singer, holding a master's as well as a bachelor's degree in classical singing. Yannai is also a research intern at Microsoft Research in Herzliya, Israel. His main research interests lie in Game Theory and Algorithmic Game Theory, spanning topics from mechanism design with and without money, to epistemic logic. He is an Adams Fellow of the Israel Academy of Sciences and Humanities.

Yishay Mansour (Tel Aviv University)
Shay Moran (IAS, Princeton)
Amir Yehudayoff (Technion - Israel institue of Technology)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors