UC Berkeley

This dissertation focuses on two main areas: 1) data-driven stochastic modeling and applied probability, with applications to the sharing economy and networks; 2) machine learning, with a focus on sequential decision making for recommender systems and revenue management. Using tools from probability, statistics, and learning theory, this dissertation emphasizes fundamental contributions to both theory and methodology.

Chapter 2 focuses on the design of stochastic models and mechanisms to increase efficiency of urban transportation and logistics systems. Trends in global urbanization require innovation, especially in the area of urban transportation networks. At the same time, the sharing economy provides opportunities to enhance efficient resource utilization. This Chapter addresses the new operational challenges that arise from emerging technologies within smart cities, focusing on last-mile delivery and smart mobility. Last-mile delivery may take up to 28% of the total transportation costs, and is arguably one of the biggest challenges in logistics management. We propose a new business model for optimizing the last-mile delivery of packages, using a strategy that combines the use of ride-sharing platforms (e.g. Uber or Lyft) with traditional in-house van delivery systems. To make the proposed solution tractable, we develop new theoretical results by approaching the problem from a probabilistic perspective. Our approach of determining the optimal reward to private drivers for delivering packages is computationally efficient. Using synthetic and real data, we show that our approach reduces cost by as much as 30% compared with the van-only strategy.

In Chapter 3, motivated by the observation that overexposure to unwanted marketing activities can lead to customer dissatisfaction, we consider a setting where a platform offers a sequence of messages to its users and is penalized when users abandon the platform due to marketing fatigue. We propose a novel sequential choice model to capture multiple interactions taking place between the platform and its users: upon receiving a message, a user decides on whether to accept or reject the message. If she chooses to reject, she would then decide to either receive the next message in the sequence or abandon the platform. Based on user feedback, the platform dynamically learns users' abandonment distribution and the relevance of the recommended content. With a goal to maximize the cumulative payoff over a time horizon, the platform dynamically adjusts the sequence of messages and the order in which the messages are shown to a user. We refer to this online learning task as the sequential choice bandit (SC-Bandit) problem. For the offline combinatorial optimization problem, we show a polynomial-time algorithm. For the online problem, we consider two variants, depending on whether contexts are included, and propose algorithms that balance exploration and exploitation. Lastly, we evaluate the performance of our algorithms with both synthetic and real-world datasets.

Complex networks appear in essentially all branches of science and engineering, and people from various fields have used random graphs to model, explain and predict some of the properties commonly observed in real-world networks. In Chapter 4, we study a family of directed random graphs whose arcs are sampled independently of each other, and are present in the graph with a probability that depends on the attributes of the vertices involved. In particular, this family of models includes as special cases the directed versions of the Erdos-Renyi model, graphs with given expected degrees, the generalized random graph, and the Poissonian random graph. We establish the phase transition for the existence of a giant strongly connected component and provide some other basic properties, including the limiting joint distribution of the degrees and the mean number of arcs. In particular, we show that by choosing the joint distribution of the vertex attributes according to a multivariate regularly varying distribution, one can obtain scale-free graphs with arbitrary in-degree/outdegree dependence.