The IID Prophet Inequality with Limited Flexibility Sebastian Perez-Salazar Mohit SinghAlejandro Toriello August 15 2023

2025-04-24 0 0 614.02KB 49 页 10玖币

侵权投诉

The IID Prophet Inequality with Limited Flexibility

Sebastian Perez-Salazar*Mohit Singh†Alejandro Toriello‡

August 15, 2023

Abstract

In online sales, sellers usually offer each potential buyer a posted price in a take-it-or-leave

fashion. Buyers can sometimes see posted prices faced by other buyers, and changing the price

frequently could be considered unfair. The literature on posted price mechanisms and prophet

inequality problems has studied the two extremes of pricing policies, the ﬁxed price policy

and fully dynamic pricing. The former is suboptimal in revenue but is perceived as fairer than

the latter. This work examines the middle situation, where there are at most kdistinct prices

over the selling horizon. Using the framework of prophet inequalities with independent and

identically distributed random variables, we propose a new prophet inequality for strategies

that use at most kthresholds. We present asymptotic results in kand results for small values of

k. For k=2 prices, we show an improvement of at least 11% over the best ﬁxed-price solution.

Moreover, k=5 prices sufﬁce to guarantee almost 99% of the approximation factor obtained

by a fully dynamic policy that uses an arbitrary number of prices. From a technical standpoint,

we use an inﬁnite-dimensional linear program in our analysis; this formulation could be of

independent interest to other online selection problems.

1 Introduction

Pricing is one of the elements of a business operation with the highest impact on proﬁtability [44].

A recent survey by McKinsey [9] shows that a 1% improvement in pricing can yield a 6% increase

in proﬁts, while in contrast a 1% reduction in variable costs can produce up to a 3.8% increase

in proﬁts. Strategic and dynamic pricing is as old as business and widely studied. Nevertheless,

the deregulation of airline prices in the US in 1978 and the development of revenue management

generated signiﬁcant interest in pricing from the research community [50]. Despite the success

of dynamic pricing from a proﬁtability viewpoint, in many businesses changing prices too often

could be considered unfair from the customers’ standpoint, particularly when customers can learn

the prices faced by others [25, 45, 46]. Therefore, ﬁxed-price policies are often preferred over

dynamic pricing, particularly in retail transactions [44]. Although a ﬁxed price is considered fairer

than its dynamic counterpart, it can lead to suboptimal revenues; this generates a natural tension

between revenue and customer goodwill. Particularly for products that will perish over time,

such as food, airplane seats [2] and sponsored ads [3], it is natural to consider price variation. In

*Rice University, sperez@rice.edu

†Georgia Institute of Technology, mohit.singh@isye.gatech.edu

‡Georgia Institute of Technology, atoriello@isye.gatech.edu

arXiv:2210.05634v3 [cs.GT] 14 Aug 2023

this work we explore a middle ground, dynamic pricing with limited prices, using the context of

Bayesian online selection and, more precisely, the prophet inequality problem.

We use the prophet inequality problem as an underlying model for online selection. The prophet

inequality problem is one of the classical problems in stopping theory, and has recently gained

increasing attention for its deep connections with pricing problems [14, 18, 27]. In the classi-

cal formulation of the prophet inequality problem, there are nnonnegative independent random

variables (r.v.) X1, . . . , Xn, and a decision-maker (DM) observes their values sequentially. Upon

observing a value, the DM must immediately decide whether to accept or reject the value. Accept-

ing stops the process, and the DM gets the observed value as a reward, while rejecting the value

is irrevocable and allows the DM to observe the next random variable’s value. The DM’s goal

is to maximize their expected value. To benchmark the DM’s strategy, the value obtained by the

DM is compared against the maximum value in hindsight, E[maxiXi]– the so-called prophet value

– and the goal is to obtain a lower bound on the ratio between the DM’s value and the prophet

value. It is known that a simple threshold strategy that computes a value xusing the distributions

and accepts the ﬁrst observed value that surpasses xattains a ratio of 1/2, and this result is tight;

see e.g. [37, 49]. This simple threshold solution is appealing for pricing mechanism design in on-

line sales, as we can interpret the threshold as a price [14]. A posted-price mechanism (PPM) is

a method to sell items where a seller offers a menu of prices to each buyer in a take-it-or-leave-it

fashion. The solution to the classical prophet inequality problem exhibits this posted pricing form:

Xirepresents the valuation of the i-th buyer, the prophet’s value E[maxiXi]is the social welfare

and xdenotes the posted price. Recent works have established the equivalence between PPMs

and prophet inequalities in several settings [14, 18, 27].

In massive markets, assuming identical valuations is reasonable when granular information about

buyers’ valuations is hard to come by. In this case, the prophet inequality problem corresponds

to the observation of independent and identically distributed (i.i.d.) random variables X1, . . . , Xn.

Hill & Kertz [29] were the ﬁrst to show that a prophet inequality with an approximation ratio

better than 1/2 can be obtained in the i.i.d. setting, with an impossibility result showing that no

ratio better than ¯

γ≈0.745 can be attained, where ¯

β=1/ ¯

γis the (unique) solution of the equation

0(β−1+y(log y−1))−1dy=1. Recently, Correa et al. [17] showed an algorithm that attains a

prophet inequality of ¯

γfor any number of random variables n.

As opposed to the solution of the prophet inequality problem for general independent random

variables, which we can solve by computing a single threshold (for instance, the median of max{Xi:

i∈[n]}), the optimal solution for the i.i.d. prophet inequality problem consists of ndecreasing

thresholds, computed via dynamic programming [29] or by sampling nthresholds from a tailored

distribution [17]. These solutions are fully dynamic, as they change the thresholds of acceptance

as time progresses. In the pricing language, this is equivalent to every buyer observing a new

posted price. On the other hand, the best ﬁxed threshold policy for the i.i.d. prophet inequality

guarantees a fraction (1−1/e)of the prophet value [17]. In this work, we ﬁll the gap between

these two extremes. Using the lens of optimization, we provide near-optimal solutions for the

problem of selecting at most kthresholds over a time horizon of length n.

1.1 Problem Formulation and Summary of Contributions

The inputs of the problem are (1) a distribution Dwith nonnegative support, (2) ni.i.d. random

variables X1, . . . , Xn∼ D drawn from this distribution, and (3) a ﬁxed integer k≥1. A decision-

maker (DM) observes the realizations of X1, . . . , Xnsequentially and needs to decide whether to

Time horizon

Threshold

i1i2i3ik−1n

···

Accepted

value

Figure 1: Illustration of a k-dynamic policy, with thresholds plotted over the time horizon. For each

interval It= [it−1+1, it], we have an associated threshold ¯

xt. The ﬁrst outcome of the random

variables with index in Itthat surpasses ¯

xtis accepted. In the picture, this occurs at the second

value observed in the third interval I3.

accept the observed value and stop the process, or irrevocably move on to the next value; the goal

is to maximize the expected accepted value. If the DM implements an algorithm or policy A, we

denote the value collected by Aas E[XA]. The algorithm Ais said to attain a γ-approximation (of the

prophet value) if E[XA]≥γE[maxi∈[n]Xi]for any input distribution D. The prophet inequality

literature has focused on ﬁnding an algorithm A∗that maximizes γ.

In this work, we are interested in k-dynamic algorithms (or policies), which choose at most ktime

intervals [1, i1],[i1+1, i2], . . . , [ik−1+1, n]and compute a static threshold in each window ¯

x1, . . . , ¯

such that the ﬁrst value Xiobserved in [it+1, it+1]that exceeds ¯

xtis accepted; see Figure 1.

Formally, we are interested in solving

γ∗

n,k=sup

k-dynamic

inf

Ddistr.

X1,...,Xn∼D

E[XA]

E[maxi∈[n]Xi].

For k=1, we obtain the static solution that guarantees γ∗

n,1 ≈1−1/efor nlarge. For k=nwe

obtain the fully dynamic solution that guarantees γ∗

n,n=¯

γ≈0.745. Our goal is to understand

γ∗

n,kfor intermediate values of kand provide new prophet inequalities for the i.i.d. problem under

k-dynamic algorithms.

Summary of Contributions We present an extensive study of k-dynamic algorithms and new

prophet inequalities. We propose an inﬁnite-dimensional linear program that encodes optimal

k-dynamic algorithms and their approximation ratio γ∗

n,k. We use this formulation to analyti-

cally compute γ∗

n,1 =1−(1−1/n)n≈1−1/e, and to numerically calculate γ∗

n,2 ≈0.708. In

other words, allowing one additional threshold over the time horizon improves the approxima-

tion ratio by 11%. For larger values of k, analyzing this inﬁnite-dimensional formulation becomes

increasingly difﬁcult; hence, we employ a relaxation. Moreover, we restrict our attention to so-

lutions where the sizes of the intervals [1, i1],[i1+1, i2], . . . , [ik−1+1, n]are ﬁxed up front. The

relaxation of our inﬁnite linear program provides a universal lower bound for γ∗

n,k; the dual of

Prophet

Inequality

12 3 45··· Large k

1−1/e

0.708

0.723

0.732

0.736

0.745

Upper bound [29, 34]

This paper

Best static policy [17, 29]

Best dynamic policy [17]

Figure 2: Asymptotic approximations obtained by our method. The plot represents the values

computed via γ∗

n,kfor k=1, 2 in Theorems 1 and 2 and v∗

∞,kfor k∈ {3, 4, 5}in Theorem 3 below.

this new formulation is oblivious to the input distribution and its solution yields distributions for

each interval, from which we can reconstruct k-dynamic algorithms as follows. For each distribu-

tion obtained from the program, we compute a quantile value q∈[0, 1], from which we obtain a

threshold xtvia the equation q=1−F(xt), where Fis the CDF of the input distribution D. Fur-

thermore, we fully characterize the optimal primal and dual solutions as functions of n; hence, we

can avoid solving a complex formulation. Since the optimal solution is difﬁcult to analyze for ﬁ-

nite n, we study its asymptotic behavior when n→∞and kis ﬁxed. We show that the asymptotic

behavior of the objective of the inﬁnite linear program is ¯

γ(1−Clog k/k), for klarge but constant.

This shows that as kgrows, k-dynamic algorithms obtain the optimal ratio of a fully dynamic so-

lution. We also provide numerical results for k≤10, which empirically show that γ∗

n,kis already

close to optimal for k≥5. In Figure 2, we present some of the approximations computed for small

kusing our methodologies.

1.2 Technical Results

Our ﬁrst technical result characterizes the optimal approximation factor for k-dynamic algorithms.

We utilize a quantile-based approach similar to the one proposed in [17]. The idea is to make

decisions based on the quantile qgiven by the value xsuch that P(X≥x) = q, instead of directly

computing the optimal policy in the xvalues.

Theorem 1 (Optimal Approximation Factor).The optimal approximation ratio for k-dynamic algo-

rithms is

γ∗

n,k=max

τ1,...,τk∈Z+

τ1+···+τk=n

γ∗

n,k(τ1, . . . , τk),

where γ∗

n,k(τ1, . . . , τk)is the optimal value of

inf

d∈Rk

f:[0,1]→R+

(D)n,ks.t. dt≥1−(1−q)τt

qZq

0fudu+ (1−q)τtdt+1,∀t∈[k],∀q∈[0, 1](1a)

0n(1−u)n−1fudu=1, (1b)

fu≥fu′,∀u≤u′. (1c)

The theorem follows directly once we show that γ∗

n,k(τ1, . . . , τk)is the best approximation ratio

that a k-dynamic algorithm can attain using ﬁxed windows of size τ1, . . . , τk. To show this, ﬁrst,

we note that for f:[0, 1]→R+satisfying Constraints (1b) and (1c), we can construct a non-

negative random variable Xwith CDF Fgiven by F−1(1−u) = fu. A calculation shows that

E[maxi∈[n]Xi] = R1

0n(1−u)n−1fudu=1. From here, we prove that for any feasible solution (d,f)

to (D)n,kand any k-dynamic algorithm Ausing windows of size τ1, . . . , τk, we get E[XA]≤d1, im-

plying that the approximation ratio of Ais at most d1. Moreover, from the optimal k-dynamic

algorithm Afor windows of size τ1, . . . , τk, we can generate a feasible solution (d,f)to (D)n,k

such that d1≤E[XA]. From here, the proof follows. We present the details in Appendix A.

Our next result shows that the optimal value of (D)n,k,γ∗

n,k(τ1, . . . , τk), equals the value of a max-

imization problem that we interpret as the dual of (D)n,k. This technical result is crucial for the

design and analysis of optimal algorithms, since from this dual problem we can extract optimal

k-dynamic algorithms.

Theorem 2 (Optimal Policy).For any integers τ1, . . . , τk≥0such that τ1+··· +τk=n, the value

γ∗

n,k(τ1, . . . , τk)equals

sup

α:[k]×[0,1]→R+

η:[0,1]→R+,η∈C

(P)n,ks.t.Z1

0α1,qdq≤1, (2a)

0αt+1,qdq≤Z1

0(1−q)τtαt,qdq,∀t∈[k−1], (2b)

vn(1−u)n−1+dηu

du≤

∑

t=1Z1

u1−(1−q)τt

qαt,qdq,[0, 1]−a.e., (2c)

η0=0, η1=0, (2d)

where a.e. stands for “almost everywhere with respect to the Lebesgue measure in [0, 1].”

Functions α={αt}tare dual variables associated with Constraints (1a), variable vis associated

with Constraint (1b), and function ηis the dual variable associated with Constraints (1c). As usual

in proving duality, we split the proof into weak and strong duality. The inﬁnite dimensions of the

primal and dual make the proof more technical; we defer it to Appendix B.

From a solution of (P)n,kwe can obtain a k-dynamic algorithm as follows. Given a feasible so-

lution (α={αt}t,v,η)of (P)n,k, we sample qtaccording to the probability mass distribution

αt,q/R1

0αt,qdqand set the threshold xtin the t-th window to satisfy qt=P(X≥xt). We can show

that this algorithm guarantees an approximation of at least vfraction of the value of the prophet

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

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

10 玖币 0人已下载

立即下载

摘要：

TheIIDProphetInequalitywithLimitedFlexibilitySebastianPerez-Salazar*MohitSingh†AlejandroToriello‡August15,2023AbstractInonlinesales,sellersusuallyoffereachpotentialbuyerapostedpriceinatake-it-or-leavefashion.Buyerscansometimesseepostedpricesfacedbyotherbuyers,andchangingthepricefrequentlycouldbecons...

展开>> 收起<<

The IID Prophet Inequality with Limited Flexibility Sebastian Perez-Salazar Mohit SinghAlejandro Toriello August 15 2023.pdf

共49页,预览5页

还剩页未读，继续阅读

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

The IID Prophet Inequality with Limited Flexibility Sebastian Perez-Salazar Mohit SinghAlejandro Toriello August 15 2023

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: