An official website of the United States government
We study the problem of online resource allocation, where customers arrive sequentially, and the seller must irrevocably allocate resources to each incoming customer while also facing a prespecified procurement cost function over the total allocation. 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 designing a surrogate function for the procurement cost to be used by the algorithm to improve the competitive ratio of the primal-dual algorithm. We use the optimal surrogate function for polynomial procurement cost functions to improve on previous bounds. For general procurement cost functions, our design method uses quasiconvex optimization to find optimal design parameters. We then implement the design techniques and show the improved performance of the algorithm in numerical examples. Finally, we extend the analysis by devising a posted pricing mechanism in which the algorithm does not require the customersβ preferences to be revealed. Funding: M. Fazelβs work was supported in part by the National Science Foundation [Awards 2023166, 2007036, and 1740551]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2021.0012 .
more »
« less
Online Facility Assignment
We consider the online facility assignment problem, with a set of facilities F of equal capacity l in metric space and customers arriving one by one in an online manner. We must assign customer ci to facility fj before the next customer ci+1 arrives. The cost of this assignment is the distance between ci and fj. The total number of customers is at most |F|l and each customer must be assigned to a facility. The objective is to minimize the sum of all assignment costs. We first consider the case where facilities are placed on a line so that the distance between adjacent facilities is the same and customers appear anywhere on the line. We describe a greedy algorithm with competitive ratio 4|F| and another one with competitive ratio |F|. Finally, we consider a variant in which the facilities are placed on the vertices of a graph and two algorithms in that setting.
more »
« less
- Award ID(s):
- 1712119
- PAR ID:
- 10065742
- Date Published:
- Journal Name:
- Walcom
- ISSN:
- 1374-5379
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Given a set of facilities and clients, and costs to open facilities, the classic facility location problem seeks to open a set of facilities and assign each client to one open facility to minimize the cost of opening the chosen facilities and the total distance of the clients to their assigned open facilities. Such an objective may induce an unequal cost over certain socioeconomic groups of clients (i.e., total distance traveled by clients in such a group). This is important when planning the location of socially relevant facilities such as emergency rooms. In this work, we consider a fair version of the problem where we are given π clients groups that partition the set of clients, and the distance of a given group is defined as the average distance of clients in the group to their respective open facilities. The objective is to minimize the Minkowski π-norm of vector of group distances, to penalize high access costs to open facilities across π groups of clients. This generalizes classic facility location (π = 1) and the minimization of the maximum group distance (π = β). However, in practice, fairness criteria may not be explicit or even known to a decision maker, and it is often unclear how to select a specific "π" to model the cost of unfairness. To get around this, we study the notion of solution portfolios where for a fixed problem instance, we seek a small portfolio of solutions such that for any Minkowski norm π, one of these solutions is an π(1)-approximation. Using the geometric relationship between various π-norms, we show the existence of a portfolio of cardinality π(log π), and a lower bound of (\sqrt{log r}). There may not be common structure across different solutions in this portfolio, which can make planning difficult if the notion of fairness changes over time or if the budget to open facilities is disbursed over time. For example, small changes in π could lead to a completely different set of open facilities in the portfolio. Inspired by this, we introduce the notion of refinement, which is a family of solutions for each π-norm satisfying a combinatorial property. This property requires that (1) the set of facilities open for a higher π-norm must be a subset of the facilities open for a lower π-norm, and (2) all clients assigned to an open facility for a lower π-norm must be assigned to the same open facility for any higher π-norm. A refinement is πΌ-approximate if the solution for each π-norm problem is an πΌ-approximation for it. We show that it is sufficient to consider only π(log π) norms instead of all π-norms, π β [1, β] to construct refinements. A natural greedy algorithm for the problem gives a poly(π)-approximate refinement, which we improve to poly(r^1/\sqrt{log π})-approximate using a recursive algorithm. We improve this ratio to π(log π) for the special case of tree metric for uniform facility open cost. Our recursive algorithm extends to other settings, including to a hierarchical facility location problem that models facility location problems at several levels, such as public works departments and schools. A full version of this paper can be found at https://arxiv.org/abs/2211.14873.more » « less
-
Kumar, Amit; Ron-Zewi, Noga (Ed.)We consider the problem in which n points arrive online over time, and upon arrival must be irrevocably assigned to one of k clusters where the objective is the standard k-median objective. Lower-bound instances show that for this problem no online algorithm can achieve a competitive ratio bounded by any function of n. Thus we turn to a beyond worst-case analysis approach, namely we assume that the online algorithm is a priori provided with a predicted budget B that is an upper bound to the optimal objective value (e.g., obtained from past instances). Our main result is an online algorithm whose competitive ratio (measured against B) is solely a function of k. We also give a lower bound showing that the competitive ratio of every algorithm must depend on k.more » « less
-
In this paper, we consider a personalized assortment planning problem under inventory constraints, where each arriving customer type is defined by a primary item of interest. As long as that item is in stock, the customer adds it to the shopping cart, at which point the retailer can recommend to the customer an assortment of add-ons to go along with the primary item. This problem is motivated by the new βrecommendation at checkoutβ systems that have been deployed at many online retailers, and it also serves as a framework that unifies many existing problems in online algorithms (e.g., personalized assortment planning, single-leg booking, and online matching with stochastic rewards). In our problem, add-on recommendation opportunities are eluded when primary items go out of stock, which poses additional challenges for the development of an online policy. We overcome these challenges by introducing the notion of an inventory protection level in expectation and derive an algorithm with a 1/4-competitive ratio guarantee under adversarial arrivals. Funding: This work was supported by the Adobe Data Science Research Award and the Alibaba Innovation Research Award. L. Xin was partly supported by the National Science Foundation (NSF) [Award CMMI-1635160], X. Chen was supported by the NSF [CAREER Award IIS-1845444]. W. Ma and D. Simchi-Levi were supported by the Accenture and MIT Alliance in Business Analytics.more » « less
-
null (Ed.)In the online video game industry, a significant portion of the revenue is generated from microtransactions, where a small amount of real-world currency is exchanged for virtual items to be used in the game. One popular way to conduct microtransactions is via a loot box, which is a random allocation of virtual items whose contents are not revealed until after purchase. In this work, we consider how to optimally price and design loot boxes from the perspective of a revenue-maximizing video game company and analyze customer surplus under such selling strategies. Our paper provides the first formal treatment of loot boxes, with the aim to provide customers, companies, and regulatory bodies with insights into this popular selling strategy. We consider two types of loot boxes: a traditional one where customers can receive (unwanted) duplicates and a unique one where customers are guaranteed to never receive duplicates. We show that as the number of virtual items grows large, the unique box strategy is asymptotically optimal among all possible strategies, whereas the traditional box strategy only garners 36.7% of the optimal revenue. On the other hand, the unique box strategy leaves almost zero customer surplus, whereas the traditional box strategy leaves positive surplus. Further, when designing traditional and unique loot boxes, we show it is asymptotically optimal to allocate the items uniformly, even when the item valuation distributions are heterogeneous. We also show that, when the seller purposely misrepresents the allocation probabilities, their revenue may increase significantly, and thus, strict regulation is needed. Finally, we show that, even if the seller allows customers to salvage unwanted items, then the customer surplus can only increase by at most 1.4%. This paper was accepted by Victor Martinez-de-Albeniz, operations management.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
