# online_posted_pricing_with_unknown_timediscounted_valuations__3020b035.pdf

Online Posted Pricing with Unknown Time-Discounted Valuations

Giulia Romano, Gianluca Tartaglia, Alberto Marchesi, Nicola Gatti Politecnico di Milano, Piazza Leonardo da Vinci 32, I-20133, Milan, Italy giulia.romano@polimi.it, gianluca.tartaglia@mail.polimi.it, alberto.marchesi@polimi.it, nicola.gatti@polimi.it

We study the problem of designing posted-price mechanisms in order to sell a single unit of a single item within a finite period of time. Motivated by real-world problems, such as, e.g., long-term rental of rooms and apartments, we assume that customers arrive online according to a Poisson process, and their valuations are drawn from an unknown distribution and discounted over time. We evaluate our mechanisms in terms of competitive ratio, measuring the worst-case ratio between their revenue and that of an optimal mechanism that knows the distribution of valuations. First, we focus on the identical valuation setting, where all the customers value the item for the same amount. In this setting, we provide a mechanism MC that achieves the best possible competitive ratio, discussing its dependency on the parameters in the case of linear discount. Then, we switch to the random valuation setting. We show that, if we restrict the attention to distributions of valuations with a monotone hazard rate, then the competitive ratio of MC is lower bounded by a strictly positive constant that does not depend on the distribution. Moreover, we provide another mechanism, called MPC, which is defined by a piecewise constant pricing strategy and reaches performances comparable to those obtained with MC. This mechanism is useful when the seller cannot change the posted price too often. Finally, we empirically evaluate the performances of our mechanisms in a number of experimental settings.

Introduction Posted-price mechanisms try to sell an item by proposing a take-it-or-leave-it price to each arriving agent, who then decides whether to buy the item or not (Chawla et al. 2010). If an agent opts for purchasing the item, then the mechanism terminates; otherwise, the agent leaves without any further possibility of buying the item, and the mechanism goes on by proposing prices to upcoming agents. Over the last years, growing attention has been devoted to the analysis of posted-price mechanisms, both in the classical economic literature (Seifert 2006) and in computer science (Babaioff et al. 2015, 2017; Adamczyk et al. 2017; Correa et al. 2017), within artificial intelligence and machine learning in particular (Kleinberg and Leighton 2003; Shah, Johari, and Blanchet 2019). This is mainly motivated by the overwhelming number of online economic transactions carried out by

Copyright c 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

posted-price mechanisms. This happens, for example, in online travel agencies (e.g., Expedia), accommodation websites (e.g., Booking.com), and e-commerce platforms (e.g., Amazon, e Bay). As studied by Einav et al. (2018), an increasing number of e Bay users prefer buying goods via posted prices rather than participating in auctions. Posted-price mechanisms provide many advantages over traditional auction-style mechanisms. From the designer s perspective, posting prices requires a much lower effort than running an auction, since it avoids the burden of first eliciting information (the bids) from the agents, and then collecting the payments. At the same time, posted-price mechanisms retain most of the desirable properties of classical auctions, such as truthfulness. Indeed, even though the agents are not required to report their valuations for the item, they are always better off deciding whether to buy the item or not on the basis of their true valuations, without acting strategically (Babaioff et al. 2017). From the agents perspective, participating in a posted-price mechanism is preferable over competing in an auction, for several reasons. For instance, agents may prefer revealing minimal information about their true preferences if they plan to participate in similar markets in the future. Moreover, in some real-world settings, requiring the agents to figure out their true valuations for the item might need some additional efforts on their behalf, while answering a take-it-or-leave-it offer is usually much easier. In this work, we study posted-price mechanisms for selling a single unit of a single item within a finite period of time, when the value of the item is discounted over time according to an arbitrary continuous and non-increasing discount function. Discounting is common in many real-world applications and widely studied for a number of economic situations, such, e.g., bargaining (Rubinstein 1982; Gatti, Di Giunta, and Marino 2008) and auctions (Mao et al. 2018). We tackle settings in which agents arrive sequentially a common assumptions in online mechanism design (Lavi and Nisan 2004; Parkes 2007) and the number of agents is unknown a priori. In particular, following a mainstream approach in economics (see, e.g., (Mason and V alim aki 2011; Rosenthal 2011)), we assume that agents arrivals are governed by a Poisson process. Remarkably, posted pricing with Poisson arrivals has been previously investigated by Wang (1993) and Rong, Qin, and An (2018) for undiscounted settings, though without providing any theoretical result.

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

We assume that each agent arriving at the mechanism has a different initial (i.e., undiscounted) valuation for the item, which is independently drawn according to a common probability distribution. This leads to a fundamental trade-off between setting high prices so as to achieve high revenue and, on the other side, progressively lowering posted prices so as to increase the probability of selling the item. Our assumption is that the mechanism is only aware of the range of valuations, while it does not know anything about the shape of the distribution. This is reasonable since, differently from the actual distribution, the range of valuations can be estimated from previous data or market surveys. Lavi and Nisan (2004) and Babaioff et al. (2017) provide the main state-of-the-art results on posted-price mechanisms for single-item single-unit scenarios. However, their models do not fit to our setting, since the agents valuations are not discounted over time and the number of agents is known a priori. As a result, these models do not embed an explicit time representation and the proposed pricing strategies are only driven by the number of agents arrived. Our model encompasses many real-world scenarios, such as, e.g., long-term rental of rooms and apartments. Think of a website renting rooms to students for fixed periods of one year. The value of a room naturally decreases over time, reflecting the fact that a future tenant will benefit from the room for a period shorter than one year. Moreover, the potential customers arrive at the renting website according to a stochastic process, which can be reasonably modeled by a Poisson process whose rate parameter can be easily estimated by looking at traffic logs of the website.

Original Contributions We adopt the perspective of competitive analysis (Borodin and El-Yaniv 2005) and evaluate our mechanisms in terms of competitive ratio, measuring the worst-case ratio between their revenue and that of an optimal mechanism that knows the distribution of valuations. As it is customary in the literature (see, e.g., (Babaioff et al. 2017; Kleinberg and Leighton 2003)), we first focus on the identical valuation setting in which all the agents share the same initial valuation for the item. Then, we extend our results to the random valuation setting where the agents valuations are drawn i.i.d. from the same distribution satisfying the monotone hazard rate condition (when the distributions of valuations are unrestricted, Lavi and Nisan (2004) and Babaioff et al. (2017) show that then there is no algorithm with good performances). In the identical valuation setting, we design a posted-price mechanism MC and prove that it is optimal, i.e., it provides the best possible competitive ratio. In order to derive the ratio, we first identify two crucial properties that characterize optimal mechanisms: their undiscounted price is non-increasing in time and they always guarantee the same fraction of the expected revenue of an optimal mechanism that knows the agents valuation, independently of its actual value. For the specific case of linear discount, we discuss how the competitive ratio depends on the parameters. In the random valuation setting, we first show that mechanism MC still provides good performances by proving that its competitive ratio is lower

bounded by a constant, which does not depend on the distribution of agents valuations. Then, motivated by real-world scenarios in which the seller is constrained not to change the posted prices too often, we propose a new mechanism MPC defined by a piecewise constant pricing strategy and prove that its performances in terms of competitive ratio are comparable with those obtained by MC. In conclusion, we empirically compare MC with a natural adaption of the mechanism proposed by Babaioff et al. (2017) to our setting, showing that the latter is inefficient even without time discounting. We also empirically evaluate the performances of MC and MPC as the frequency with which prices are allowed to change decreases, showing that, when this is not too low, then the performances of MPC and MC are comparable.

Other Related Works As showed by Hajiaghayi, Kleinberg, and Sandholm (2007) for single-item settings, posted pricing is strictly related to the secretary problem and to prophet inequalities; see also the work by Babaioff et al. (2009) for single-item settings and that of Lucier (2017) for multi-item scenarios. Differently from our model, these works assume that the mechanism knows the probability distribution of agents valuations and that the agents reveal their actual valuation for the item upon arrival. When multiple units of the same item are available, learning approaches based on bandit techniques are customarily adopted. In particular, Kleinberg and Leighton (2003) study an unlimitedsupply setting where the number of buyers is fixed, and derive upper bounds on the regret. Several recent works extend the results in (Kleinberg and Leighton 2003). Shah, Johari, and Blanchet (2019) study a contextual setting, providing a semi-parametric model that learns from the observation of a binary outcome which stands for acceptance or rejection of the offered price. Mohri and Munoz (2014) study revenue-maximizing learning algorithms for posted pricing with strategic buyers. They consider a repeated game in which, at each round, the seller offers the item at a certain price and a strategic buyer accepts or rejects it. In that work, the goal is to learn the buyers valuation for the item by minimizing the strategic-regret of the algorithm.

Preliminaries We study a model in which a seller is interested in selling a single unit of an item within a finite time period of length T. The seller implements a posted-price mechanism by setting a take-it-or-leave-it price at each time t [0, T]. We denote by p : [0, T] R+ the pricing strategy adopted by the seller, with p(t) being the price offered at time t [0, T]. The agents (i.e., the buyers) arrive sequentially over time, according to a Poisson process with rate parameter λ > 0. We label agents according to their order of arrival (i.e., agent i is the i-th agent arriving in [0, T]). Each agent i has a private valuation Vi for the item, drawn from a distribution F with finite support [vmin, vmax], where vmax > vmin > 0 denote the maximum and minimum valuation, respectively. In the following, for the ease of presentation, we normalize agents valuations in the range [1, h], where h := vmax

vmin . Accordingly, we scale the support of F to [1, h]. Then, we

denote by f the probability density function of F. The value of the item for sale decreases over time. In particular, Vi is agent i s initial valuation at time t = 0. We model decreasing values by introducing a continuous nonincreasing discount function ξ : [0, T] [0, 1] such that ξ(0) = 1 and ξ(T) = 0. By letting Wi be the random variable representing the arrival time of agent i, we define the agent i s discounted valuation as Di := Vi ξ(Wi), which represents how much agent i is willing to pay upon her arrival. As a result, whenever agent i arrives, she buys the item if and only if Di p(Wi), i.e., her discounted valuation is at least as large as the price offered by the mechanism. We introduce the following additional notation. We denote by Is,τ := [s, s + τ] [0, T] the time interval of length τ [0, T] starting from time s [0, T τ]. The number of agents arriving in Is,τ is a random variable denoted by Ns,s+τ. Given τ [0, T], the random variables Ns,s+τ are equally distributed for all s [0, T τ], as the arrivals are generated by a Poisson process. For the sake of presentation, we omit s in Ns,s+τ, denoting by Nτ the random variable of the number of agents arriving in any time interval of length τ, which follows a Poisson distribution with parameter λτ. 1 Thus, NT is the random variable of the total number of agents arriving in the overall time period. In the following, we sometimes focus on the linear discount function, denoted as ξlin : [0, T] [0, 1] with ξlin(t) := 1 t

T . In this case, each agent i s discounted valuation is Di := Vi 1 Wi

Performances of Posted-Price Mechanisms Given a deterministic posted-price mechanism M defined by a price function p M : [0, T] R+, we denote by EF [R(M)] the expected revenue that the mechanism provides to the seller. The expectation is calculated with respect to both the Poisson arrivals and the distribution F of agents initial valuations. We made explicit the dependence on F, as we will frequently refer to it along the paper. We adopt the perspective of competitive analysis and measure the performances of a mechanism M by comparing the seller s expected revenue with that of a benchmark mechanism M , which is optimal having knowledge of the distribution F. Notice that the benchmark has no information on the actual realizations of agents initial valuations, but only on their distribution, whereas the mechanisms we propose operate having knowledge of their range only. Our goal is to bound the performances of our mechanisms w.r.t. those of the benchmark M by looking at the worst case over the set F of possible distributions F, i.e., all those with support [1, h]. This is captured by the following:

Definition 1. The competitive ratio of a deterministic posted-price mechanism M is defined as:

ρ(M) := min F F ρF (M), where ρF (M) := EF [R(M)]

EF [R(M )].

Moreover, we say that a mechanism is optimal when its competitive ratio is the highest possible among all the deterministic posted-price mechanisms.

1By definition of Poisson distribution, P {Nτ=j}= (λτ)je λτ

Notice that ρ(M) [0, 1] and, for every possible distribution F F, we are guaranteed that the seller s expected revenue EF [R(M)] provided by mechanisms M is at least a fraction ρ(M) of that achieved by M , i.e., it holds EF [R(M)] ρ(M) EF [R(M )]. As previously showed by Babaioff et al. (2017) in similar settings, we can safely restrict our analysis to mechanisms maintaining the bottom price for a non-negligible period of time. Indeed, in the case in which F places all the probability mass on 1, then any mechanism providing a non-null seller s expected revenue must set the minimum price during some time interval, otherwise no agent would buy the item.

Proposition 1. Every deterministic posted-price mechanism M such that ρ(M) > 0 must set the minimum price p M(t) = ξ(t) for every t in a time interval of length τ > 0.

Identical Valuation Setting We start studying the identical valuation (IV) setting, where all the agents share the same initial valuation v [1, h] for the item, i.e., it holds Vi = v and Di = v ξ(Wi) for every agent i. The IV setting is a special case of the general random valuation model where one restricts the attention to distributions F placing all the probability mass on a single valuation in [1, h]. In the following, we adjust notation for expected revenues and competitive ratios accordingly, writing Ev[R(M)] and ρv(M) instead of EF [R(M)] and ρF (M). Our main result (Theorem 1) is to provide a deterministic posted-price mechanism, called MC, which is optimal for the IV setting for every discount function ξ. We also study the specific case of a linear discount function ξlin, where we design an optimal mechanism MC,lin (Theorem 2) that enjoys an easily interpretable analytical description. All the proofs are in (Romano et al. 2020). First, we describe the shape of the benchmark mechanism M for the IV setting. Indeed, since M knows the actual initial valuation v, its price function p M : [0, T] R+ is such that p M (t) = v ξ(t) for t [0, T]. Therefore, we can compute the expected revenue of M as follows:

Ev [R(M )] := Z T

0 p M (t) λ e λt dt =

0 v ξ(t) λ e λt dt = v k , (1)

where k := R T 0 ξ(t) λ e λt dt does not depend on v, but only on the problem parameters T, λ, and the discount function ξ. Let us remark that the expected revenue of the benchmark M defined in Equation (1) is expressed as a linear function of v.

Optimal Mechanism for a General Discount We start proving two lemmas that highlight two crucial properties which characterize optimal posted-price mechanisms for the IV setting. Lemma 1 implies that the pricing strategy of an optimal mechanism must be such that the undiscounted price defined as p(t)

ξ(t) is non-increasing in t, whereas Lemma 2 shows that any mechanism which always provides

a constant fraction of the expected revenue of the benchmark, independently of the agents initial valuation v, is an optimal mechanism. Lemma 1. In the IV setting, given any deterministic postedprice mechanism M, there always exists a deterministic posted-price mechanism M with undiscounted price p M (t)

ξ(t) non-increasing in t such that Ev[R(M)] Ev[R(M )] for every possible agents initial valuation v [1, h]. Notice that, since ξ is continuous and non-increasing by definition, Lemma 1 also shows that there is always an optimal mechanism whose pricing strategy is non-increasing. Moreover, by recalling Proposition 1, we can conclude that any optimal mechanism must set the minimum price at the end of the overall time period, i.e., during a time interval [t0, T] [0, T] defined for some t0 [0, T). This result is exploited to prove the following lemma. Lemma 2. In the IV setting, let M be a deterministic posted-price mechanism whose pricing strategy p M satisfies p M(t) = ξ(t) for t [t0, T] with t0 [0, T). If the ratio ρv(M) = Ev[R(M)] Ev[R(M )] for M does not depend on the agents initial valuation v, then M is an optimal mechanism. By Lemma 2, in order to find an optimal mechanism for the IV setting, we can restrict the attention to mechanisms M whose ratios ρv(M) do not depend on the initial valuation v. Therefore, since the expected revenue of the benchmark M is a linear function of v (see Equation (1)), we can search for an optimal mechanism among those having an expected revenue which linearly depends on v. This crucial observation allows us to design the optimal mechanism MC in Theorem 1 by leveraging the condition Ev[R(MC)] = k v for every v [1, h], with k being a suitably defined constant independent of v. The key insight that allows us to derive an expression for MC is that we can always find the desired pricing strategy p MC among the continuous price functions such that p MC (t)

ξ(t) is non-increasing in t [0, T). Intuitively, using Lemma 1, we can always express the expected revenue Ev[R(MC)] as a function of the time t := sup{t [0, t0] | p MC(t) > v ξ(t)}, which is the first time in which p MC intersects v ξ(t). The reason is that it holds p MC(t) v ξ(t) if and only if t t , and, thus, only agents arriving after t are willing to buy the item. By using the relation among Ev[R(MC)] and t , we can find the desired pricing strategy p MC as a solution to a suitably defined differential equation. This leads to the following theorem. Theorem 1. In the IV setting, there exists an optimal deterministic posted-price mechanism MC whose pricing strategy p MC is defined as follows:

p MC(t) := a e R b(t)dt if t [0, t0) ξ(t) if t [t0, T] ,

where b is a function such that b(t) := λ λ kζ(t) ζ (t)

ζ(t) with ζ(t) := 1 ξ(t), whereas a, k, t0 are suitably defined constants that do not depend on the agents initial valuation v. As a byproduct of the proof of Theorem 1, we also get an expression for the competitive ratio of the mechanism MC, as stated by the following corollary.

T λ h t0 Θ(

T/λ) Θ(T) ρ(MC,lin) Θ 1 1

Θ 1 log2(h)

lim ρ(MC,lin) 1 1 0

Table 1: Values of t0 and ρ(MC,lin) as T, λ, h go to infinity.

Corollary 1. In the IV setting, mechanism MC achieves:

R T t0 0 ξ(t) λ e λt dt R T 0 ξ(t) λ e λt dt .

Optimal Mechanism for a Linear Discount The pricing strategy p MC of the optimal mechanism defined in Theorem 1 still depends on some parameters, namely a, k, and t0, which do not admit an easy analytical formula for a general discount function ξ. Nevertheless, they can be expressed analytically if we restrict the attention to functions ξ having a particular shape. In the following Theorem 2 and Corollary 2, we analyze the case of a linear discount function ξlin, defining an optimal mechanism MC,lin for such setting. Theorem 2. In the IV setting with linear discount function ξlin, there exists an optimal deterministic posted-price mechanism MC,lin whose pricing strategy p MC,lin is defined as:

p MC,lin(t) := h 1 t

k)t+ λ 2k T t2 if t [0, t0) 1 t

T if t [t0, T] ,

where k := λ t0 2 T t0 2 T (λ t0+ln h) and the time t0 [0, T) is defined as the unique positive real root of the following equation: 1 1 λT 1 + λ t0 e λ(T t0) = k. The prices posted by MC,lin decrease as a linearly discounted exponential function until t = t0, starting, at time t = 0, by setting the price equal to the maximum agents initial valuations h. Then, during the time interval [t0, T], the price function linearly decreases and equals zero in t = T. Corollary 2. In the IV setting with linear discount function ξlin, MC,lin achieves a competitive ratio:

ρ(MC,lin) = 1 1 λT 1 + λt0 e λ(T t0)

1 1 λT (1 e λT ) .

The asymptotic values of t0 and ρ(MC,lin) as T, λ, h go to infinity are in Table 1 (see (Romano et al. 2020) for more details). In particular, ρ(MC,lin) goes asymptotically to 1 as λ or T increases. This corresponds to having an infinite number of agents and, thus, selling the item with certainty. Instead, ρ(MC,lin) decreases as h increases, going asymptotically to 0 as 1 log2(h). The range [1, h] represents the degree of uncertainty that the mechanism has on the agents valuation. Therefore, ρ(MC,lin) decreases as the uncertainty increases and it cannot be lower bounded by any strictly positive constant if no finite upper bound on h is known (i.e., when h + ). However, the dependency of ρ(MC,lin) on the degree of uncertainty is logarithmic. Instead, notice that a trivial mechanism setting the price equal to ξlin(t) for t [0, T] would have a competitive ration of 1

h, which depends linearly on the degree of uncertainty.

Random Valuation Setting We now switch to the random valuation (RV) setting, where agents initial valuations Vi are i.i.d. random variables defined by a cumulative distribution function F with support [1, h]. We focus on distributions F satisfying the monotone hazard rate (MHR) condition. Formally, a distribution F is MHR if the hazard rate H(x) := f(x) 1 F (x) is nondecreasing in x. This assumption is common when studying posted-price mechanisms that operate without knowing the shape of the distribution of valuations (see (Babaioff et al. 2015, 2017)) and many distributions used in practice satisfy it (such as, e.g., uniform, normal, and exponential distributions). Moreover, the MHR condition is necessary for proving our main results (Theorems 3 and 4). Indeed, when the family of possible distributions is unrestricted, one cannot design posted-price mechanisms guaranteeing a constant fraction of the revenue of M independently of the distribution F, as shown by Babaioff et al. (2017) for the easier setting in which agents do not arrive stochastically. All the proofs are provided in (Romano et al. 2020).

Auxiliary Definitions and Results We introduce the random variable Xλτ as the maximum initial valuation of agents arriving in an interval of length τ (0, T]. Formally:

Xλτ := max i {1,...,Nτ } Vi. 2

Xλτ is the first order statistic of Nτ samples drawn from F and, since agents arrivals are governed by a Poisson process, its cumulative distribution function FXλτ is defined as:

FXλτ (x) :=

j=1 P {Nτ = j} FXλτ |Nτ =j(x) =

j! [F(x)]j = e λτ(1 F (x)).

We also define Ys,λτ as the random variable representing the maximum discounted valuation of agents arriving in an interval Is,τ of length τ (0, T] starting at s [0, T τ]:

Ys,λτ := max i {1,...,Nτ } Di.

The cumulative distribution function FYs,λτ of Ys,λτ is:

FYs,λτ (x) :=

j=1 P {Nτ = j} FYs,λτ |Nτ =j(x) =

j! FYs,λτ |Nτ =j(x),

where FYs,λτ |Nτ =j is the cumulative distribution function of Ys,λτ conditioned on the event Nτ = j. Let us remark that,

2In the definition of Xλτ and Ys,λτ, overloading the notation, we assume that the agents arriving in the considered time interval of length τ are labeled from 1 to Nτ according to their order. Their actual labels referred to the overall period [0, T] may be different.

by definition, FYs,λτ depends on distribution F. In the following, we also let YλT := Y0,λT be the random variable representing the maximum discounted valuation of agents arriving in the overall time period [0, T]. In the Supplemental Material, for the specific case of a linear discount function, we show how to exploit some useful properties of Poisson processes so as to find an analytical expression for FYλT . In particular, by letting Z := V U, where V and U are independent random variables distributed according to F and U(0, 1), respectively, we obtain:

FYλT (x) :=

j! [FZ(x)]j ,

( x R h 1 1 zf(z)dz if x [0, 1) F(x) + x R h x 1 zf(z)dz if x [1, h] .

Bounding ρ(MC) in the RV Setting We show that mechanism MC (see definition in Theorem 1), which is optimal in the IV setting, provides good performances also in the RV setting. Our main result (Theorem 3) is a lower bound on the competitive ratio of the mechanism, which is obtained by showing that MC always provides at least a constant fraction of the seller s expected revenue achieved by the benchmark M , independently of the distribution of agents initial valuations F. 3 This is surprising since, differently from M , our mechanism works without having knowledge about F (except for its range). We first need some definitions and lemmas. Definition 2. Let Is,τ be any interval of length τ (0, T] starting at s [0, T τ]. Then, the ratio between the prices posted by MC at the endpoints of Is,τ is defined as:

κτ(s) := p MC(s) p MC(s + τ).

Intuitively, κτ(s) bounds the slope of the price function of MC in the time interval Is,τ, which depends on both the starting time s and the length τ of the interval. Moreover, notice that κτ(s) 1 since p MC is non-increasing by Lemma 1. Next, we introduce an upper bound on the price ratios of all the time intervals of length τ, which is useful in deriving our main result. Definition 3. The maximum price ratio of MC over intervals of length τ (0, T] is denoted by: κτ := max s [0,T τ] κτ(s).

The following lemma establishes a relation between the price function p MC of MC and the expected value of the random variable XλT representing the maximum initial valuation of agents arriving in the overall time period. This is crucial to prove Theorem 3.

3To prove the lower bound, we follow an approach similar to that used by Babaioff et al. (2017) to bound the competitive ratio of their Equal-Sample-of-Every-Scale mechanism. However, our setting introduces additional challenges, since the agents arrivals are stochastic and the valuations are discounted. Thus, our proofs require different techniques w.r.t. those of Babaioff et al. (2017).

Lemma 3. In the RV setting with agents initial valuations drawn from a distribution F, given τ (0, T] and 0 < ϵ < 1, there exists at least an interval Is,τ of length τ (0, T] starting at s [0, T τ] such that the prices p MC(t) posted by mechanism MC during the time instants t Is,τ lie in

the range h E[XλT ]ξ(s+τ)(1 ϵ)

κτ , E[XλT ]ξ(s + τ)(1 ϵ) i .

The following two lemmas are the final pieces that we need to prove Theorem 3. Lemma 4 establishes that, if the distribution F is MHR, then the same holds for the distribution FXλτ of Xλτ. Lemma 5, given two intervals of length τ and τ with τ τ , provides a lower bound on the expected value of Xλτ which depends on the expected value of Xλτ and the logarithms of the expected number of agents arrivals in the two intervals, respectively λτ and λτ .

Lemma 4. FXλτ has non-decreasing monotone hazard rate.

Lemma 5. For every τ, τ (0, T] with τ τ , it holds:

E[Xλτ] E[Xλτ ] ln (λτ)

Theorem 3. Consider the RV setting with λτ = (λT)1 ϵ 1 ln(e 1) for some τ (0, T] and 0 < ϵ < 1. Then, restricted to the set F of distributions F satisfying the MHR condition, mechanism MC has a competitive ratio that can be lower bounded as follows:

ρ(MC) ξ(t0 + T 1 ϵλ ϵ)(1 ϵ)

The idea of the proof is to use ρF (MC) EF [R(MC)]

E[YλT ] , following from the fact that EF [R(M )] cannot be larger than E[YλT ], which is the expected revenue achieved by an optimal mechanism that knows the realization of agents initial valuations and arrivals. Then, EF [R(MC)] is lower bounded by the revenue that MC achieves in a suitably defined interval Is,τ, whose existence is guaranteed by Lemma 3. Moreover, Lemmas 3, 4, and 5, together with the properties of MHR distributions, allow us to write EF [R(MC)] E[XλT ]ξ(t0+τ)(1 ϵ)

κτ e , giving the result as E[YλT ] E[XλT ].

A Mechanism with a Piecewise Constant Price

We introduce a new mechanism MPC whose pricing strategy p MPC is a piecewise constant function. This turns out to be useful in all the situations in which the seller is constrained not to change the posted price too often, e.g., when the mechanism is required to set prices for time intervals having a given minimum length. Our main result (Theorem 4) is a lower bound on the competitive ratio of MPC in the RV setting, which is comparable to that obtained for MC in Theorem 3. Thus, we show that, even in presence of constraints on the allowed pricing strategies, we are still able to design mechanisms with good performances in terms of competitive ratio. Clearly, MPC depends on the minimum length requirement, which influences the resulting lower bound. In particular, MPC is tuned by a parameter δ related to the number of time intervals in which the price must be constant.

(b) τ = 0.25

Figure 1: Prices of mechanisms MC,lin (blue) and MPC,lin (black) when h = 2.8, λ = 10, and T = 12.

Mechanism MPC works by evenly partitioning the time interval [0, t0] into logδ h sub-intervals of length τ, where δ (1, h] and t0 [0, T] are suitably defined parameters. Then, the remaining time [t0, T] is organized in other subintervals of length τ. As a result, [0, T] is partitioned into T

τ sub-intervals, which, overloading notation, we denote by Ii := [(i 1)τ, min{iτ, T}] for i = 1, . . . , T

τ . Notice that τ = t0 logδ h , and, thus, parameters t0 and δ can be tuned to match the required minimum length τ. The pricing strategy p MPC of MPC is defined in such a way that the price is constant in each interval Ii. By letting p MPC(Ii) be the price posted during Ii, we define the function p MPC as follows: 4

p MPC(Ii) :=

h δi ξ(iτ) if i = 1, . . . , logδ h ξ(iτ) if i = logδ h , . . . , T

τ 1. ξ((i 1)τ) if i = T

We compare in Figure 1 the prices of MC,lin and MPC,lin (i.e., MPC with a linear discount) in a specific setting for two values of τ. Notice that MPC can be thought of as an extension of the Equal-Sample-of-Every-Scale (ESo ES) mechanism by Babaioff et al. (2017) to the more general setting in which agents arrive stochastically according to a Poisson process and agents valuations are discounted over time. Before proving our main result, we need the following lemma, which is the analogous of Lemma 3 working for mechanism MPC instead of MC. Lemma 6. In the RV setting with agents initial valuations drawn from a distribution F, given 0 < ϵ < 1, there exists i = 1, . . . , logδ h such that the price p MPC(Ii) posted by MPC during the interval Ii lies in the range ν

δ ξ(iτ), νξ(iτ) , where ν := max{1, E[XλT ](1 ϵ)}. Now, we provide our main result. The idea behind its proof is similar to the one used for Theorem 3. Theorem 4. Consider the RV setting with λτ = (λT)1 ϵ 1 ln(e 1) for some τ (0, T] and 0 < ϵ < 1. Then, restricted to the set F of distributions F satisfying the MHR condition, mechanism MPC has a competitive ratio that can be lower bounded as follows:

ρ(MPC) ξ(( logδ h + 1)T 1 ϵλ ϵ)(1 ϵ)

4Whenever T is not divisible by τ, then the last time interval is shorter than τ. Thus, in order to satisfy the minimum length constraint, we set its price equal to the one in the preceeding interval.

5 10 15 20 0.1

5 10 15 20 0.1

Figure 2: Average normalized revenue of MC, MPC, ESo ES-SS in a RV setting w. uniform distribution (h = 10).

Empirical Evaluation

We evaluate mechanisms MC, MPC, and a natural adaption of the ESo ES mechanism by Babaioff et al. (2017) to stochastic settings with no time discounting (called ESo ESSS). The pricing strategy of ESo ES-SS is defined as follows. First, we compute the prices of ESo ES by setting the number of agents equal to the expected number λT of agents arriving in [0, T] according to a Poisson process of parameter λ. Then, ESo ES-SS proposes the price that ESo ES would propose to the i-th agent arrived if i λT and 1 otherwise. We use the following parameters values for the experiments: λ {1, . . . , 20}, T {10, 20, 50, 100}, and h {2, . . . , 20}. The following results do not consider time discounting so as to have a fair comparison between our mechanisms and ESo ES-SS. Further results with a linear discount function are provided in (Romano et al. 2020).

Result #1 We study a RV setting with a uniform probability distribution over [1, h]. For every combination of values of λ, T, h, we run 1000 Monte Carlo simulations, evaluating the revenue provided by mechanisms ESo ES-SS, MC, and MPC. In particular, we analyze some variants of mechanisms MPC differing for the number of subintervals (i.e., Nsub) in which [0, t0] is partitioned. Furthermore, we normalize the revenue provided by the mechanisms in each simulation with respect to h. We report the results in Figure 2 for T = 10 and T = 50, when h = 10. The results obtained for different values of h are similar. MC and MPC with Nsub = 232 have overlapping performances that beat those of the other mechanisms. MPC with Nsub = 13 has a performance close to that of the previous two mechanisms, showing that mechanism MPC provides good performances even with few subintervals. MPC with Nsub = 4 and ESo ES-SS have almost overlapping performances, showing that very few subintervals are sufficient to MPC to match the performances of ESo ES-SS. The worst mechanism is MPC with Nsub = 2. The loss of ESo ES-SS w.r.t. MC averaged over the values of λ is about 0.3 h when T = 10, and 0.4 h when T = 50. Surprisingly, the performances of ESo ES-SS seem to do not strictly depend on λ and T.

5 10 15 20 0

5 10 15 20 0

Figure 3: Maximum difference between the normalized revenues of MC and ESo ES-SS in an IV setting (h = 10).

Result #2 We study an IV setting. For every combination of values of λ, T, h, and for every v {1.0, 1.5, 2.0, . . . , h}, we run 1000 Monte Carlo simulations, evaluating the normalized revenue provided by mechanisms ESo ES-SS and MC. For every combination of values of λ, T, h, we calculate maxv Ev[R(MC)] Ev[R(ESo ES-SS)]

h , corresponding to the maximum normalized loss of ESo ES-SS w.r.t. MC over all valuations v, and maxv Ev[R(ESo ES-SS)] Ev[R(MC)]

h , corresponding to the maximum normalized loss of MC w.r.t. ESo ES-SS over all valuations v. These two indexes are shown in Figure 3 for T = 10 and T = 50, when h = 10. The results obtained for different values of h are similar. The loss of ESo ES-SS w.r.t. MC is always larger than 0.5 h except when both λ and T assume small values, while the loss of MC w.r.t. ESo ES-SS is negligible. Furthermore, the two losses converge to two constants as λ and T increase. This shows that, even if there are some special settings where ESo ES-SS performs better than MC, the improvement is negligible. Instead, mechanism MC, which is designed to deal with stochastic arrivals, provides a very significant improvement. In particular, we observe that the difference between the revenue provided by ESo ES-SS and that provided by MC is maximized for small values of v close to 1, while between MC and ESo ES-SS for large values of v close to h.

Conclusion and Future Works We study distribution-free posted-price mechanisms in order to sell a unique item within a finite time period. In our model, the agents arrive online according to a Poisson process, and their valuations for the item are discounted over time. Following a worst-case competitive analysis, we design a mechanism MC providing an optimal competitive ratio in the identical valuation setting. Then, as for the random valuation setting, we analyze the performances of MC and of a new mechanism MPC that is constrained to set constant prices during time intervals having a given minimum length. We prove that both mechanisms achieve a competitive ratio that is constant with respect to the actual valuation when the distribution of the valuations has a monotone hazard rate. This shows that our mechanisms are robust even in nonstationary markets subject to arbitrary distribution changes preserving the same support. In future, we will investigate hybrid settings in which our robust mechanisms can be combined with machine learning tools. For instance, data could be used to learn a class of distributions, and we could design a mechanism robust with respect to all the distributions of that class.

Acknowledgments This work has been partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR Algorithms, Games, and Digital Market .

Ethics Statement Posted-price mechanisms are widely adopted in real-world economic transactions, thanks to their simplicity: a seller posts prices and buyers arrive sequentially, deciding whether to accept the offer or not. Nowadays, most e-commerce websites implement this form of interaction with their users. Our mechanisms apply to concrete scenarios where the probability distribution of buyers valuations is unknown, the value of item for sale may decrease over time, and buyers arrivals are stochastic. In these settings, our mechanisms can make economic transactions more efficient and robust, allowing agents (buyers and sellers) to find better economic agreements. As we argued in the paper, our mechanisms provide theoretical guarantees in terms of online worst-case performance. This could have an arguably positive societal impact when applied to real-world economic problems. However, further research in this direction is required to prevent scenarios with an unbalanced reward structure, where agreements may just award one side (buyers or sellers) with the largest utilities at the expense of the others.

References Adamczyk, M.; Borodin, A.; Ferraioli, D.; Keijzer, B. D.; and Leonardi, S. 2017. Sequential posted-price mechanisms with correlated valuations. ACM Transactions on Economics and Computation (TEAC) 5(4): 1 39.

Babaioff, M.; Blumrosen, L.; Dughmi, S.; and Singer, Y. 2017. Posting prices with unknown distributions. ACM Transactions on Economics and Computation (TEAC) 5(2): 1 20.

Babaioff, M.; Dinitz, M.; Gupta, A.; Immorlica, N.; and Talwar, K. 2009. Secretary problems: weights and discounts. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, 1245 1254. SIAM.

Babaioff, M.; Dughmi, S.; Kleinberg, R.; and Slivkins, A. 2015. Dynamic pricing with limited supply. ACM Transactions on Economics and Computation (TEAC) 3(1): 1 26.

Borodin, A.; and El-Yaniv, R. 2005. Online computation and competitive analysis. Cambridge University Press.

Chawla, S.; Hartline, J. D.; Malec, D. L.; and Sivan, B. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing, 311 320.

Correa, J.; Foncea, P.; Hoeksma, R.; Oosterwijk, T.; and Vredeveld, T. 2017. Posted price mechanisms for a random stream of customers. In Proceedings of the 2017 ACM Conference on Economics and Computation, 169 186.

Einav, L.; Farronato, C.; Levin, J.; and Sundaresan, N. 2018. Auctions versus posted prices in online markets. Journal of Political Economy 126(1): 178 215.

Gatti, N.; Di Giunta, F.; and Marino, S. 2008. Alternatingoffers bargaining with one-sided uncertain deadlines: an efficient algorithm. Artificial Intelligence 172(8-9): 1119 1157. Hajiaghayi, M. T.; Kleinberg, R.; and Sandholm, T. 2007. Automated online mechanism design and prophet inequalities. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, 58 65. Kleinberg, R.; and Leighton, T. 2003. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., 594 605. IEEE. Lavi, R.; and Nisan, N. 2004. Competitive analysis of incentive compatible on-line auctions. Theoretical Computer Science 310(1-3): 159 180. Lucier, B. 2017. An economic view of prophet inequalities. ACM SIGecom Exchanges 16(1): 24 47. Mao, W.; Zheng, Z.; Wu, F.; and Chen, G. 2018. Online Pricing for Revenue Maximization with Unknown Time Discounting Valuations. In Proceedings of the Twenty Seventh International Joint Conference on Artificial Intelligence, 440 446. Mason, R.; and V alim aki, J. 2011. Learning about the arrival of sales. Journal of Economic Theory 146(4): 1699 1711. Mohri, M.; and Munoz, A. 2014. Optimal regret minimization in posted-price auctions with strategic buyers. In Advances in Neural Information Processing Systems, 1871 1879. Parkes, D. C. 2007. Online mechanisms. Cambridge University Press. Romano, G.; Tartaglia, G.; Marchesi, A.; and Gatti, N. 2020. Online Posted Pricing with Unknown Time-Discounted Valuations. ar Xiv preprint ar Xiv:2012.05774 . Rong, J.; Qin, T.; and An, B. 2018. Dynamic pricing for reusable resources in competitive market with stochastic demand. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 4718 4726. Rosenthal, E. C. 2011. A Pricing Model for Residential Homes with Poisson Arrivals and a Sales Deadline. The Journal of Real Estate Finance and Economics 42(2): 143 161. Rubinstein, A. 1982. Perfect Equilibrium in a Bargaining Model. Econometrica 50(1): 97 109. Seifert, S. 2006. Posted price offers in internet auction markets, volume 580. Springer Science & Business Media. Shah, V.; Johari, R.; and Blanchet, J. 2019. Semi-Parametric Dynamic Contextual Pricing. In Advances in Neural Information Processing Systems, 2363 2373. Wang, R. 1993. Auctions versus posted-price selling. The American Economic Review 838 851.