Applied Probability Society Student Paper Competition: Abstracts of 2017 Finalists

The 2017 prize winners are:

First Prize

On the Euler Discretization Error of Brownian Motion About Random Times

Guido Lagos, University of Santiago

Finalists (in alphabetical order according to student’s last name):

Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework

Daniel Freund, Cornell University; Thodoris Lykouris, Cornell University

Learning Preferences with Side Information: Near Optimal Recovery of Tensors

Andrew Li, MIT

Multiagent Online Learning Under Imperfect Information: Algorithms, Theory, and Applications

Zhengyuan Zhou, Stanford University

On the Euler Discretization Error of Brownian Motion About Random Times

Guido Lagos

University of Santiago, [email protected]

Advisor: Ton Dieker, Columbia University

In this paper, we derive weak limits for the discretization errors of sampling barrier-hitting and extreme events of Brownian motion by using the Euler discretization simulation method. Specifically, we consider the Euler discretization approximation of Brownian motion to sample barrier-hitting events, that is, hitting for the first time a deterministic “barrier” function, and to sample extreme events, that is, attaining a minimum on a given compact time interval or unbounded closed-time interval. For each case, we study the discretization error between the actual time the event occurs versus the time the event occurs for the discretized path and also the discretization error on the position of the Brownian motion at these times. We show limits in distribution for the discretization errors normalized by their convergence rate and give closed-form analytic expressions for the limiting random variables. Additionally, we use these limits to study the asymptotic behaviour of Gaussian random walks in the following situations: (1) the overshoot of a Gaussian walk above a barrier that goes to infinity; (2) the minimum of a Gaussian walk compared with the minimum of the Brownian motion obtained when interpolating the Gaussian walk with Brownian bridges, both up to the same time horizon that goes to infinity; and (3) the global minimum of a Gaussian walk compared with the global minimum of the Brownian motion obtained when interpolating the Gaussian walk with Brownian bridges when both have the same positive drift decreasing to zero. In deriving these limits in distribution, we provide a unified framework to understand the relation between several papers in which the constant $-\zeta \left(1/2\right)/\sqrt{2\pi }$ has appeared, where $\zeta$ is the Riemann zeta function. In particular, we show that this constant is the mean of some of the limiting distributions we derive.

Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework

Daniel Freund

Cornell University, [email protected]

Thodoris Lykouris

Cornell University, [email protected]

Advisor: Siddhartha Banerjee, Cornell University

Optimizing shared vehicle systems (bike sharing/car sharing/ride sharing) is more challenging compared with traditional resource allocation settings because of the presence of complex network externalities—changes in the demand/supply at any location affect future supply throughout the system within short time scales. These externalities are well captured by steady-state Markovian models, which are, therefore, widely used to analyze such systems. However, using such models to design pricing/control policies is computationally difficult because the resulting optimization problems are high-dimensional and nonconvex. To this end, we develop a general approximation framework for designing pricing policies in shared vehicle systems based on a novel convex relaxation that we term elevated flow relaxation. Our approach provides the first efficient algorithms with rigorous approximation guarantees for a wide range of objective functions (throughput, revenue, welfare). For any shared vehicle system with $n$ stations and $m$ vehicles, our framework provides a pricing policy with an approximation ratio of $1+\left(n-1\right)/m$. This guarantee is particularly meaningful when $m/n$, the average number of vehicles per station is large as is often the case in practice. Further, the simplicity of our approach allows us to extend it to more complex settings: rebalancing empty vehicles, redirecting riders to nearby vehicles, multiobjective settings (such as Ramsey pricing), incorporating travel times, etc. Our approach yields efficient algorithms with the same approximation guarantees for all these problems and, in the process, obtains as special cases several existing heuristics and asymptotic guarantees.

Learning Preferences with Side Information: Near Optimal Recovery of Tensors

Andrew Li

MIT, [email protected]

Advisor: Vivek Farias, MIT

Product and content personalization is now ubiquitous in e-commerce. There is typically too little available transactional data for this task. As such, companies today seek to use a variety of information on the interactions between a product and a customer to drive personalization decisions. We formalize this problem as one of recovering a large-scale matrix with side information in the form of additional matrices of conforming dimension. Viewing the matrix we seek to recover and the side information we have as slices of a tensor, we consider the problem of slice recovery, which is to recover specific slices of “simple” tensors from noisy observations of the entire tensor. We propose a definition of simplicity that, on the one hand, elegantly generalizes a standard generative model for our motivating problem and, on the other, subsumes low-rank tensors for a variety of existing definitions of tensor rank. We provide an efficient algorithm for slice recovery that is practical for massive data sets and provides a significant performance improvement over state-of-the-art incumbent approaches to tensor recovery. Further, we establish near-optimal recovery guarantees that in an important regime represent an order improvement over the best available results for this problem. Experiments on data from a music-streaming service demonstrate the performance and scalability of our algorithm.

Multiagent Online Learning Under Imperfect Information: Algorithms, Theory, and Applications

Zhengyuan Zhou

Stanford University, [email protected]

Advisors: Nicholas Bambos, Stanford University;

Peter Glynn, Stanford University;

Panayotis Mertikopoulos, French National Center for Scientific Research;

Clair Tomlin, UC Berkeley

We consider a model of multiagent online learning under imperfect information, in which the reward structures of agents are given by a general continuous game. After introducing a general equilibrium stability notion for continuous games, called $\lambda$-variational stability, we examine the well-known online mirror descent (OMD) learning algorithm and show that the “last iterate” (that is, the actual sequence of actions) of OMD converges to variationally stable Nash equilibria provided that the feedback delays faced by the agents are synchronous and bounded. We then extend the result to almost sure convergence to variationally stable Nash equilibria under both unbiased noise and synchronous and bounded delays. Subsequently, to tackle fully decentralized, asynchronous environments with unbounded feedback delays, we propose a variant of OMD that we call delayed mirror descent (DMD), which relies on the repeated leveraging of past information. With this modification, the algorithm converges to variationally stable Nash equilibria with no feedback synchronicity assumptions even when the delays grow superlinearly relative to the game’s horizon. We then again extend it to the case in which there are both delays and noise. Finally, we present two applications that demonstrate the broad applicability of the theoretical framework and results: one to stochastic optimization and the other to power management in wireless networks.