Function Design for Improved Competitive Ratio in Online Resource Allocation with Procurement Costs

• URL: http://arxiv.org/abs/2012.12457v1
• Date: Wed, 23 Dec 2020 02:32:47 GMT
• Title: Function Design for Improved Competitive Ratio in Online Resource Allocation with Procurement Costs
• Authors: Mitas Ray, Omid Sadeghi, Lillian J. Ratliff, Maryam Fazel
• Abstract summary: We study the problem of online resource allocation, where multiple customers arrive the seller must allocate resources to each incoming customer while also facing a procurement cost for the total allocation.
• Score: 16.68130648568593
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of online resource allocation, where multiple customers arrive sequentially and the seller must irrevocably allocate resources to each incoming customer while also facing a procurement cost for the total allocation. Assuming resource procurement follows an a priori known marginally increasing cost function, the objective is to maximize the reward obtained from fulfilling the customers' requests sans the cumulative procurement cost. We analyze the competitive ratio of a primal-dual algorithm in this setting, and develop an optimization framework for synthesizing a surrogate function for the procurement cost function to be used by the algorithm, in order to improve the competitive ratio of the primal-dual algorithm. Our first design method focuses on polynomial procurement cost functions and uses the optimal surrogate function to provide a more refined bound than the state of the art. Our second design method uses quasiconvex optimization to find optimal design parameters for a general class of procurement cost functions. Numerical examples are used to illustrate the design techniques. We conclude by extending the analysis to devise a posted pricing mechanism in which the algorithm does not require the customers' preferences to be revealed.

Related papers

• Robust personalized pricing under uncertainty of purchase probabilities [2.9061423802698565]
  We propose a robust optimization model for personalized pricing that accounts for the uncertainty of predicted purchase probabilities. We also develop a Lagrangian decomposition algorithm combined with line search to efficiently find high-quality solutions for large-scale optimization problems.
  arXiv  Detail & Related papers  (2024-07-22T02:36:19Z)
• Cost-Sensitive Multi-Fidelity Bayesian Optimization with Transfer of Learning Curve Extrapolation [55.75188191403343]
  We introduce utility, which is a function predefined by each user and describes the trade-off between cost and performance of BO. We validate our algorithm on various LC datasets and found it outperform all the previous multi-fidelity BO and transfer-BO baselines we consider.
  arXiv  Detail & Related papers  (2024-05-28T07:38:39Z)
• An adaptive approach to Bayesian Optimization with switching costs [0.8246494848934447]
  We investigate modifications to Bayesian Optimization for a resource-constrained setting of sequential experimental design. We adapt two process-constrained batch algorithms to this sequential problem formulation, and propose two new methods: one cost-aware and one cost-ignorant.
  arXiv  Detail & Related papers  (2024-05-14T21:55:02Z)
• Rethinking and Benchmarking Predict-then-Optimize Paradigm for Combinatorial Optimization Problems [62.25108152764568]
  Many web applications rely on solving optimization problems, such as energy cost-aware scheduling, budget allocation on web advertising, and graph matching on social networks. We consider the performance of prediction and decision-making in a unified system. We provide a comprehensive categorization of current approaches and integrate existing experimental scenarios.
  arXiv  Detail & Related papers  (2023-11-13T13:19:34Z)
• Refined Mechanism Design for Approximately Structured Priors via Active Regression [50.71772232237571]
  We consider the problem of a revenue-maximizing seller with a large number of items for sale to $n$ strategic bidders. It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute.
  arXiv  Detail & Related papers  (2023-10-11T20:34:17Z)
• Approaching Collateral Optimization for NISQ and Quantum-Inspired Computing [0.0]
  Collateral optimization refers to the systematic allocation of financial assets to satisfy obligations or secure transactions. One of the common objectives is to minimise the cost of collateral required to mitigate the risk associated with a particular transaction or a portfolio of transactions.
  arXiv  Detail & Related papers  (2023-05-25T18:01:04Z)
• Multi-objective robust optimization using adaptive surrogate models for problems with mixed continuous-categorical parameters [0.0]
  Robust design optimization is traditionally considered when uncertainties are mainly affecting the objective function. The resulting nested optimization problem may be solved using a general-purpose solver, herein the non-dominated sorting genetic algorithm (NSGA-II) The proposed approach consists of sequentially carrying out NSGA-II while using an adaptively built Kriging model to estimate the quantiles.
  arXiv  Detail & Related papers  (2022-03-03T20:23:18Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  We casting online learning problems in which a decision maker wants to maximize their expected reward without violating a finite set of $m$m resource constraints. Our framework allows the decision maker to handle its evidence flexibility and costoretic functions.
  arXiv  Detail & Related papers  (2022-02-28T12:10:48Z)
• Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions [74.00030431081751]
  We formalize the notion of user-specific cost functions and introduce a new method for identifying actionable recourses for users. Our method satisfies up to 25.89 percentage points more users compared to strong baseline methods.
  arXiv  Detail & Related papers  (2021-11-01T19:49:35Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  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.
  arXiv  Detail & Related papers  (2020-07-01T14:24:58Z)

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.