报告题目/Title: Onthe Power and Limitation of Algorithmic Analysis for Online Pricing
时间/Date & Time:2018年10月25日，15:30—16:30
A seller has some productto be sold to a sequence of buyers u1, u2, . . . arriving online and he needsto decide, for each ui, the amount of product to be sold to ui at thethen-prevailing market price pi. The objective is to maximize the seller’srevenue. All previous algorithms for the problem need to impose some artificialupper bound M and lower bound m on the market prices, and the seller needs toknow either the values of M and m, or their ratio M/m, at the outset.
In this talk, wegive an algorithm that does not impose any bounds on market prices and whoseperformance guarantee depends directly on the input. In particular, we give aclass of algorithms such that for any positive integer h and any positive numberϵ, we have an algorithm Ah,ϵ with good competitive ratio. We alsoprove that our algorithms are near optimal by showing that given any positiveinteger h and any algorithm A, we can construct a sequence of buyers σ suchthat the ratio between the optimal revenue and the revenue obtained by A islower bounded by some value which is very close to the upper bound.
Moreover, weassume that the highest prices of buyers follow some distribution with monotonehazard rate, which is a well-adopted assumption. We investigate two variants,(1) the distribution is on the highest price among all buyers, and (2) thedistribution of the highest price of each buyer is independent and identicallydistributed. To measure the performance of the algorithms, the expected competitiveratios, E[OPT]/E[ALG] and E[OPT/ALG], are considered. If the distributionssatisfy the monotone hazard rate, for both of the above two variants, constant-competitivealgorithms can be achieved.
报告人简介/About the speaker: