Online Matching with Cancellation Costs Farbod Ekbatani University of Chicago Booth School of Business Chicago IL fekbatanchicagobooth.edu

2025-05-02 0 0 1.02MB 53 页 10玖币

侵权投诉

Online Matching with Cancellation Costs

Farbod Ekbatani

University of Chicago Booth School of Business, Chicago, IL, fekbatan@chicagobooth.edu

Yiding Feng

Microsoft Research New England, Cambridge, MA, yidingfeng@microsoft.com

Rad Niazadeh

University of Chicago Booth School of Business, Chicago, IL, rad.niazadeh@chicagobooth.edu

Motivated by applications in cloud computing spot markets and selling banner ads on popular websites, we

study the online resource allocation problem with overbooking and cancellation costs, also known as the

buyback setting. To model this problem, we consider a variation of the classic edge-weighted online matching

problem in which the decision maker can reclaim any fraction of an oﬄine resource that is pre-allocated

to an earlier online vertex; however, by doing so not only the decision maker loses the previously allocated

edge-weight, it also has to pay a non-negative constant factor fof this edge-weight as an extra penalty.

Parameterizing the problem by the buyback factor f, our main result is obtaining optimal competitive

algorithms for all possible values of fthrough a novel primal-dual family of algorithms. We establish the

optimality of our results by obtaining separate lower-bounds for each of small and large buyback factor

regimes, and showing how our primal-dual algorithm exactly matches this lower-bound by appropriately

tuning a parameter as a function of f. Interestingly, our result shows a phase transition: for small buyback

regime (f < e−2

2) the optimal competitive ratio is e

e−(1+f), and for large buyback regime (f≥e−2

2), the

competitive ratio is −W−1−1

e(1+f). We further study the lower and upper bounds on the competitive ratio

in variants of this model, such as matching with deterministic integral allocations or single-resource with

diﬀerent demand sizes. For deterministic integral matching, our results again show a phase transition: for

small buyback regime (f < 1

3), the optimal competitive ratio is 2

1−f, and for the large buyback regime

(f≥1

3), the competitive ratio is 1 + 2f+ 2pf(1 + f). We show how algorithms in our unifying family of

primal-dual algorithms can obtain the exact optimal competitive ratio in all of these variants — which,

in turn, demonstrates the power of our algorithmic framework for online resource allocations with costly

cancellations.

Key words : online resource allocation, overbooking, buyback problem, callable resources, online matching,

primal-dual analysis

arXiv:2210.11570v2 [cs.DS] 1 Aug 2023

Ekbatani, Feng and Niazadeh: Online Matching with Cancellation Costs

1. Introduction

Revenue management strategies play a pivotal role in driving proﬁtability and ensuring optimal

resource utilization. One such strategy that has garnered signiﬁcant attention is overbooking, a

prevalent practice in classic applications such as airline seat reservations (Rothstein,1971) and hotel

booking (Liberman and Yechiali,1978) where businesses intentionally accept more reservations or

orders than their available capacity as customers arrive. By doing so, businesses can hedge against

early commitments to low-paying customers by denying service after allocation, and also mitigate

losses from no-shows and cancellations, ultimately leading to increased revenue.

To address customer satisfaction upon service denial, one approach is to implement a buyback

contract. This contract allows the platform to reclaim any pre-allocated resource from a customer

during the allocation horizon, but only after providing full refund of the original fee along with an

additional compensation fee, often determined by a simple function of the original payment. With

the advent of modern online marketplaces, this paradigm has found intriguing applications. An

example is assigning servers to arriving jobs in cloud computing spot markets (e.g., AWS EC2 spot

instances), where the platform can recall servers after a full refund and an extra fee paid to the

owner of the revoked job.1Similarly, for negotiated yearly contracts selling banner advertisements

on popular websites (e.g., displayed ads on Microsoft Network), the platform must make online

admission and costly revocation decisions as advertisers with heterogeneous willingness-to-pay

arrive over the ad campaign horizon.2Adopting the buyback strategy enables such platforms to

eﬀectively manage overbooking, and optimize resource allocation in dynamic market environments.

Motivated by the above paradigm, we investigate the problem of online resource allocations

with buyback. Existing work has mainly focused on single-resource scenarios (Gallego et al.,2008;

Babaioﬀ et al.,2009), but modern applications involve richer environments with multiple resources

of diﬀerent types (e.g., servers with varying computational power). The objective is to ﬁnd a

matching between demand and supply. We model this as an edge-weighted online bipartite match-

ing problem, where online nodes arrive sequentially and reveal their edge-weights to the oﬄine

side (Karp et al.,1990;Feldman et al.,2009). The decision maker must determine how to match

each arriving online node to oﬄine nodes (with capacity constraints) either fractionally or inte-

grally. The decision maker is allowed to allocate more than the capacity to an oﬄine node, but

should revoke the overbooked allocations by paying a buyback cost. We consider a simple linear

model where the buyback cost is a non-negative constant ftimes the pre-allocated reward.3

1For more details on this application, see AWS’s website.

2For more details on this application, see MSN’s display ad website.

3The modeling choice of the ﬁxed linear compensation scheme is partially motivated by applications in which buyback

contracts cannot be personalized and should have simple and interpretable forms. More complicated compensation

schemes are still interesting to be studied, but are not captured by our simple model.

Ekbatani, Feng and Niazadeh: Online Matching with Cancellation Costs 3

The decision maker’s goal is to maximize the total weight of the matching minus the buyback

cost at the end. Our focus is on developing robust online algorithms to handle non-stationary

demand arrivals, motivated in part by relevant applications. Building on the seminal work of Karp

et al. (1990) in the computer science literature and Ball and Queyranne (2009) in the revenue

management literature, we adopt a framework that considers adversarial arrival for the online

nodes. Parameterizing the problem by the buyback factor f, we measure the performance of our

online algorithms by their competitive ratio, which is the worst-case ratio of the objective of an

omniscient oﬄine benchmark to that of the algorithm. We then ask the following research questions:

(i) Can we design simple (fractional) online algorithms for the above problem to achieve the

optimal competitive ratio for all the parameter choices of the buyback factor f? (ii) What if

we restrict our attention to the simpler class of deterministic integral online algorithms?

Our main contributions. We answer both of the above questions in aﬃrmative by hitting two

birds with one stone: we design and analyze a unifying parametric family of primal-dual online

algorithms that are optimal competitive in both settings with fractional allocations and with deter-

ministic integral allocations (after tuning their parameters). We also show by applying randomized

rounding techniques any fractional algorithm can be converted into a randomized integral algorithm

with almost no loss under large capacities — hence our set of results provide a complete picture

for designing optimal competitive online algorithms in the online resource allocation problem with

buyback under large capacities. To show these results, our contribution is two-fold:

(i) Lower-bounds in diﬀerent parameter regimes. We ﬁrst establish separate lower-bounds

of Γgen(f) and Γdet-int(f) on the optimal competitive ratios for the general setting and the deter-

ministic integral setting, respectively. These lower-bounds (below) are drawn in Figure 1; here,

W−1: [ −1/e,0) →(−∞,−1] is the non-principal branch of the Lambert W function:4

Γgen(f)≜









e−(1+f)if f≤e−2

−W−1−1

e(1+f)if f≥e−2

,Γdet-int(f)≜





1−fif f≤1

1+2f+ 2pf(1 + f) if f≥1

To obtain the above lower-bounds, we identify two sources of uncertainty preventing an online

algorithm to perform as well as the optimum oﬄine: the edge-wise uncertainty and the weight-wise

uncertainty. Intuitively speaking, the edge-wise uncertainty is related to the multi-resource aspect

of our model and captures the information-theoretic diﬃculty of identifying the right oﬄine node

to be matched to an arriving online node given the future uncertainty (hence it is still present

even when f= 0). On the contrary, the weight-wise uncertainty is related to the buyback aspect of

4In mathematics, the Lambert W function, also called the omega function or product logarithm, is the converse

relation of the function y(x) = x·ex. The non-principal branch x=W−1(y) is the inverse relation when x≤ −1.

Ekbatani, Feng and Niazadeh: Online Matching with Cancellation Costs

our model and captures the information-theoretic diﬃculty of identifying the edge with the largest

weight among all edges adjacent to an oﬄine node given the future uncertainty (hence it is still

present even in the special case with a single resource). Notably, as fincreases, the weight-wise

uncertainty starts playing a more important role than the edge-wise uncertainty, and vice versa.

We use novel constructions in our worst-case instances to exploit the trade-oﬀ between the above

two sources of uncertainty. Interestingly, we observe a phase transition in both fractional and

deterministic integral settings in terms of the behavior of the worst-case instance for the competitive

ratio: there is the small buyback cost regime where f < ˆ

fand the worst-case instance heavily relies

on the multi-resource aspect of the model, and the large buyback cost regime where f > ˆ

fand the

worst-case instance heavily relies on the buyback aspect of our model and is indeed exactly the

same as the worst-case instance of the single-resource environment. The phase transition thresholds

are diﬀerent for the two settings. Speciﬁcally, ˆ

f=e−2

2for the general setting and ˆ

f=1

3for the

deterministic integral setting. In the large buyback cost regime, our lower-bounds for the general

algorithms and deterministic integral algorithms match the bounds in Badanidiyuru and Kleinberg

(2009) and Babaioﬀ et al. (2009), respectively, established for the single-resource environment.

Moreover, as f→0 in the extreme case of the small buyback cost regime, the lower-bound Γgen(f)

converges to e

e−1and Γdet-int(f) converges to 2, which are indeed the worst-case competitive ratios

of the edge-weighted online bipartite matching with free-disposal (Karp et al.,1990;Feldman et al.,

2009) for general algorithms and deterministic integral algorithms, respectively. This problem is a

special case of our model when f= 0.

e−2

e−1

Figure 1 Competitive ratio as the function of buyback factor f: Black solid (dashed) curve is the optimal

competitive ratio Γgen(f)for the matching environment (single-resource environment). Gray solid (dashed) curve

is the optimal competitive ratio Γdet-int(f)of deterministic integral algorithms for the matching environment

(single-resource environment). Black solid curve and black dashed curve coincide for buyback factor

f≥e−2

2≈0.359. Gray solid curve and gray dashed curve coincide for buyback factor f≥1

Ekbatani, Feng and Niazadeh: Online Matching with Cancellation Costs 5

(ii) Upper-bounds via primal-dual in all parameter regimes. Second, we establish exact

matching upper-bounds by introducing a novel primal-dual family of online algorithms for this

problem. The primal-dual framework has demonstrated its eﬃcacy in designing and analyzing

online bipartite allocation algorithms with irrevocable allocations or free cancellations in various

contexts.5However, until now, this framework has not been applied to cases where cancellation is

costly, and it remained uncertain whether it could be beneﬁcial in such settings.

The main challenge arises from the fact that the optimal oﬄine benchmark does not involve

buybacks (incurring no buyback cost). Consequently, the linear program for the optimum oﬄine

solution does not capture any aspects of the buyback feature in our problem. Prior work on single-

resource buyback (Babaioﬀ et al.,2009;Badanidiyuru and Kleinberg,2009) does not propose

systematic approaches to address the problem; instead, they either rely on simple variations of the

naive greedy algorithm or adhoc randomized schemes (for rounding weights) to obtain competitive

online algorithms. It remains unclear whether any of these adhoc ideas can be extended to the

matching environment. This gap in understanding the buyback problem from prior literature makes

developing the optimal competitive online algorithm for edge-weighted online matching with costly

cancellation/buyback highly challenging.

In a nutshell, our main technical (and conceptual) contribution is bridging the gap in the existing

literature by establishing a new connection between the primal-dual framework for online bipartite

resource allocation problems and the buyback problem. This newfound understanding allows us to

derive optimal competitive algorithms for all the regimes of the buyback parameter f. We begin

our investigation by re-visiting the single-resource buyback problem through the systematic lens

of the primal-dual framework. Equipped with this systematic approach, we can recover a new

optimal competitive online algorithm for the fractional (and integral) single-resource buyback. More

interestingly, we show how to naturally extend our primal-dual fractional algorithm to the matching

environment to obtain our main result. We also show how natural adaptations of this approach to

the integral setting obtain optimal competitive ratios for deterministic integral algorithms.

Our techniques. We summarize our technical ﬁndings below. The complete technical story in

this paper is elaborate and we refer the reader for the details to Sections 3,4, and 5.

5Examples of such applications include the well-celebrated online bipartite matching problem with or without vertex

weights (Karp et al.,1990;Aggarwal et al.,2011), online budgeted allocation (Adwords) problem (Mehta et al.,

2007;Buchbinder et al.,2009), online assortment optimization with or without reusable resources (Golrezaei et al.,

2014;Feng et al.,2019;Goyal et al.,2020), and the special case of our problem when f= 0, which is the online

edge-weighted bipartite matching with free disposal (Feldman et al.,2009;Devanur et al.,2016).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

OnlineMatchingwithCancellationCostsFarbodEkbataniUniversityofChicagoBoothSchoolofBusiness,Chicago,IL,fekbatan@chicagobooth.eduYidingFengMicrosoftResearchNewEngland,Cambridge,MA,yidingfeng@microsoft.comRadNiazadehUniversityofChicagoBoothSchoolofBusiness,Chicago,IL,rad.niazadeh@chicagobooth.eduMotivat...

展开>> 收起<<

Online Matching with Cancellation Costs Farbod Ekbatani University of Chicago Booth School of Business Chicago IL fekbatanchicagobooth.edu.pdf

共53页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Online Matching with Cancellation Costs Farbod Ekbatani University of Chicago Booth School of Business Chicago IL fekbatanchicagobooth.edu

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: