UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Probabilistic design in the operation of service systems Han, Jiangze

Abstract

The design of probabilistic mechanisms in service systems is a key challenge in operations management. This thesis explores three applications where service providers must design or control probability distributions, which may be non-parametric and infinite-dimensional. Chapter 2 examines customer partitioning to optimize a quantitative criterion, relevant to clustering and user grouping. This involves decomposing a customer distribution into sub-distributions to optimize operational targets. We analyze optimal sub-distribution structures and propose a gradient-based algorithm using the Wasserstein gradient flow. Our algorithm finds a feasible decomposition that satisfies our optimality condition, with numerical results demonstrating its practicality and insights. Chapter 3 studies an online convex optimization problem where the decision variable is a probability measure, motivated by matching spatial supply with demand in a geographical setting. Using optimal transport theory, we propose an online Wasserstein gradient descent algorithm, extending classical gradient descent in Euclidean space. We establish sublinear static regret under geodesic convexity and sublinear dynamic regret with bounded variation. When decisions are probability densities, we provide conditions ensuring the algorithm remains within the space of densities while maintaining regret bounds. When loss functionals are strongly geodesic convex, dynamic regret is further controlled by path length, implying sublinear growth if the path length is sublinear. Chapter 4 focuses on probabilistic selling in the video game industry, specifically loot box mechanisms, a major revenue source. Loot boxes randomly drop items of varying value, with sellers choosing prices and drop rates. We show that loot box design is generally NP-hard but solvable in polynomial time under fixed item numbers and restricted player utilities. We also develop polynomial-time approximation algorithms with fixed precision. Our findings link loot box design to direct item pricing, leveraging the relationship between prices and drop rates. An extension considers a more generalized model, offering approximations with polynomial runtime when the number of items is fixed.

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International