Regularized Online Allocation Problems: Fairness and Beyond

• URL: http://arxiv.org/abs/2007.00514v4
• Date: Fri, 5 Nov 2021 00:40:05 GMT
• Title: Regularized Online Allocation Problems: Fairness and Beyond
• Authors: Santiago Balseiro, Haihao Lu, Vahab Mirrokni
• Abstract summary: We introduce the emphregularized 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.
• Score: 7.433931244705934
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Online Fair Allocation of Perishable Resources [1.4952056744888913]
  We consider a practically motivated variant of the canonical online fair allocation problem. A decision-maker has a budget of perishable resources to allocate over a fixed number of rounds. The goal is to construct a sequence of allocations that is envy-free and efficient.
  arXiv  Detail & Related papers  (2024-06-04T15:14:10Z)
• Switchable Decision: Dynamic Neural Generation Networks [98.61113699324429]
  We propose a switchable decision to accelerate inference by dynamically assigning resources for each data instance. Our method benefits from less cost during inference while keeping the same accuracy.
  arXiv  Detail & Related papers  (2024-05-07T17:44:54Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  We consider an online allocation problem subject to lower and upper resource constraints, where the requests arrive sequentially. We propose a new algorithm that obtains $1-O(fracepsilonalpha-epsilon)$ -competitive ratio for the offline problems that know the entire requests ahead of time.
  arXiv  Detail & Related papers  (2021-12-28T02:21:06Z)
• Fairer LP-based Online Allocation [13.478067250930101]
  We consider a Linear Program (LP)-based online resource allocation problem where a decision maker accepts or rejects incoming customer requests irrevocably. We propose a fair algorithm that uses an interior-point LP solver and dynamically detects unfair resource spending. Our approach do not formulate the fairness requirement as a constrain in the optimization instance, and instead we address the problem from the perspective of algorithm design.
  arXiv  Detail & Related papers  (2021-10-27T17:45:20Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  We propose falSe COrrelation REduction (SCORE) for offline RL, a practically effective and theoretically provable algorithm. We empirically show that SCORE achieves the SoTA performance with 3.1x acceleration on various tasks in a standard benchmark (D4RL)
  arXiv  Detail & Related papers  (2021-10-24T15:34:03Z)
• Contingency-Aware Influence Maximization: A Reinforcement Learning Approach [52.109536198330126]
  influence (IM) problem aims at finding a subset of seed nodes in a social network that maximize the spread of influence. In this study, we focus on a sub-class of IM problems, where whether the nodes are willing to be the seeds when being invited is uncertain, called contingency-aware IM. Despite the initial success, a major practical obstacle in promoting the solutions to more communities is the tremendous runtime of the greedy algorithms.
  arXiv  Detail & Related papers  (2021-06-13T16:42:22Z)
• Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
  We consider a general online optimization problem with multiple budget constraints over a horizon of finite time periods. The objective of the decision maker is to maximize the cumulative reward subject to the budget constraints. This formulation captures a wide range of applications including online linear programming and network revenue management.
  arXiv  Detail & Related papers  (2020-12-13T04:47:37Z)
• The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems [7.433931244705934]
  We consider a data-driven setting in which the reward and resource consumption of each request are generated using an input model unknown to the decision maker. We design general class of algorithms that attain good performance in various input models without knowing which type of input they are facing. Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online mirror descent.
  arXiv  Detail & Related papers  (2020-11-18T18:39:17Z)
• Coordinated Online Learning for Multi-Agent Systems with Coupled Constraints and Perturbed Utility Observations [91.02019381927236]
  We introduce a novel method to steer the agents toward a stable population state, fulfilling the given resource constraints. The proposed method is a decentralized resource pricing method based on the resource loads resulting from the augmentation of the game's Lagrangian.
  arXiv  Detail & Related papers  (2020-10-21T10:11:17Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  The paper investigates the general problem of resource allocation for mitigating channel fading effects in Free Space Optical (FSO) communications. Under this framework, we propose two algorithms that solve FSO resource allocation problems.
  arXiv  Detail & Related papers  (2020-07-27T17:38:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.