Guanting Chen (ICME): Online Resource Allocation with Unknown Demand

Title:
Online Resource Allocation with Unknown Demand: Bounded Regret and Fair Algorithm

Abstract:
We study the online resource allocation problem where the decision-maker aims to maximize the total reward subject to budget constraints on multiple types of resources over a finite horizon. At each time, the reward and resource consumption of the arriving order is revealed, and the decision-maker needs to accept or reject the order. We consider a stochastic setting where the reward and resource consumption of arriving orders follow an i.i.d. distribution with finite support. Without the knowledge of distribution parameters, we propose an adaptive LP(Linear Program)-based algorithm and show that the regret, defined as the performance gap between the reward of the online algorithm and the optimal reward in the offline problem, is bounded and not dependent on the length of time horizon. The algorithm also features a fair allocation rule in two aspects: (i) fairness across time and (ii) individual fairness. In (i), we require that the treatment of the same type of order is fair relative to the past and future; In (ii), we require that similar orders should be treated similarly. To achieve these criteria, we identify the offline fair solution that is fair across order types, and define cumulative unfairness as the cumulative distance from the online allocation rule to the offline fair solution. We ensure fairness by showing that the cumulative unfairness has a logarithmic upper bound with respect to the time horizon.

Bio:
Guanting Chen is a Ph.D. Candidate at the Institute for Computational and Mathematical Engineering at Stanford University. His research lies at the intersection of sequential decision making, stochastic modeling, and optimization. With a focus on understanding how an agent interacting with an unknown environment can learn over time to make better decisions, he designs and analyzes algorithms that are effective in terms of revenue loss, and fair across time and individuals. He also develops simulation algorithms for stochastic models to solve the associated computational problems that arise in finance and risk analysis. 

Website:

http://web.stanford.edu/~guanting/index.html