论文标题
正规化在线分配问题：公平及以后
Regularized Online Allocation Problems: Fairness and Beyond
论文作者
论文摘要
在线分配问题与资源约束有关，在运营研究中具有丰富的历史。在本文中，我们介绍了\ emph {正规化在线分配问题}，该变体包括对总资源消耗作用的非线性正规化程序。在此问题中，请求随着时间的推移反复到达，对于每个请求，决策者需要采取一项行动来产生奖励并消耗资源。目的是同时最大程度地提高可分离的奖励，并且受资源约束的不可分割的正常化程序的价值。我们的主要动机是允许决策者权衡可分离的目标，例如分配的经济效率，该目标是通过辅助，不可分割的目标（例如分配的公平性或公平性）进行的。我们设计了一种简单，快速且具有随机的I.I.D.和对抗输入的算法，并且可以获得良好的性能。特别是，在随机I.I.D.下，我们的算法在渐近上是最佳的。输入模型并达到固定的竞争比率，该比率取决于正常化的对手。此外，算法和分析不需要奖励功能和消耗功能的凸度或凹度，这允许更大的模型灵活性。数值实验证实了互联网广告应用程序中提出的算法和正则化的有效性。
Online allocation problems with resource constraints have a rich history in operations research. In this paper, we introduce the \emph{regularized online allocation problem}, a variant that includes a non-linear regularizer acting on the total resource consumption. In this problem, requests repeatedly arrive over time and, for each request, a decision maker needs to take an action that generates a reward and consumes resources. The objective is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer subject to the resource constraints. Our primary motivation is allowing decision makers to trade off separable objectives such as the economic efficiency of an allocation with ancillary, non-separable objectives such as the fairness or equity of an allocation. We design an algorithm that is simple, fast, and attains good performance with both stochastic i.i.d.~and adversarial inputs. In particular, our algorithm is asymptotically optimal under stochastic i.i.d. input models and attains a fixed competitive ratio that depends on the regularizer when the input is adversarial. Furthermore, the algorithm and analysis do not require convexity or concavity of the reward function and the consumption function, which allows more model flexibility. Numerical experiments confirm the effectiveness of the proposed algorithm and of regularization in an internet advertising application.
