北京科学与工程计算研究院学术报告之七十七

报告人/Speaker: 张涌(中国科学院深圳先进技术研究院)


报告题目/Title: Onthe Power and Limitation of Algorithmic Analysis for Online Pricing


时间/Date & Time:20181025日,15:30—16:30


地点/Location: 理科楼M842,BISEC


报告摘要/Abstract:

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:
张涌,深圳先进技术研究院副研究员,IEEE高级会员,ACM会员,CCF会员。2007年,博士毕业于复旦大学计算机系。之后在德国柏林工业大学数学系做博士后,香港大学计算机系任职高级研究员。张涌博士的研究方向包括算法优化、无线网络,分布式计算等,近年来在本领域中国际知名会议和期刊上发表文章超过80 篇。张涌博士近年来承担了多项国家和省部级科研项目,包括国家自然科学基金,科技部国家重点研发计划,中科院重点部署项目等。