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

• Procurement Auctions via Approximately Optimal Submodular Optimization [53.93943270902349]
  We study procurement auctions, where an auctioneer seeks to acquire services from strategic sellers with private costs. Our goal is to design computationally efficient auctions that maximize the difference between the quality of the acquired services and the total cost of the sellers.
  arXiv  Detail & Related papers  (2024-11-20T18:06:55Z)
• Deep Generative Demand Learning for Newsvendor and Pricing [7.594251468240168]
  We consider data-driven inventory and pricing decisions in the feature-based newsvendor problem. We propose a novel approach leveraging conditional deep generative models (cDGMs) to address these challenges. We provide theoretical guarantees for our approach, including the consistency of profit estimation and convergence of our decisions to the optimal solution.
  arXiv  Detail & Related papers  (2024-11-13T14:17:26Z)
• 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)
• 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)
• 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.