• Previous Article
    Relay selection based on social relationship prediction and information leakage reduction for mobile social networks
  • MFC Home
  • This Issue
  • Next Article
    A survey: Reward distribution mechanisms and withholding attacks in Bitcoin pool mining
November 2018, 1(4): 383-392. doi: 10.3934/mfc.2018019

Constant competitive algorithms for unbounded one-Way trading under monotone hazard rate

1. 

Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, China

2. 

Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong

3. 

School of Computer Science and Technology, University of Science and Technology of China, China

Received  September 2018 Revised  September 2018 Published  December 2018

In the one-way trading problem, a seller has some product to be sold to a sequence of buyers in an online fashion, i.e., buyers come one after another. Each buyer has the accepted unit price which is known to the seller on his arrival. To maximize the total revenue, the seller has to carefully decide the amount of products to be sold to each buyer at the then-prevailing prices. In this paper, we study the unbounded one-way trading, i.e., the highest unit price among all buyers is positive and unbounded. We assume that the highest prices of buyers follow some distribution with monotone hazard rate, which is a well-adopted assumption. We investigate two variants, (1) the distribution is on the highest price among all buyers, and (2) the distribution of the highest price of each buyer is independent and identically distributed. To measure the performance of the algorithms, the expected competitive ratios, $ \mathrm{E}[OPT]/\mathrm{E}[ALG] $ and $ \mathrm{E}[OPT/ALG] $, are considered. If the distributions satisfy the monotone hazard rate, for both of the above two variants, constant-competitive algorithms can be achieved.

Citation: Yong Zhang, Francis Y. L. Chin, Francis C. M. Lau, Haisheng Tan, Hing-Fung Ting. Constant competitive algorithms for unbounded one-Way trading under monotone hazard rate. Mathematical Foundations of Computing, 2018, 1 (4) : 383-392. doi: 10.3934/mfc.2018019
References:
[1]

M. Babaioff, S. Dughmi, R. Kleinberg and A. Slivkins, Dynamic pricing with limited supply, In Proceedings of the 13th ACM Conference on Electronic Commerce (EC 2012), 3 (2015), 74–91. doi: 10.1145/2559152.

[2]

A. Badanidiyuru, R. Kleinberg and Y. Singer, Learning on a budget: posted price mechanisms for online procurement, In Proceedings of the 13th ACM Conference on Electronic Commerce (EC 2012), (2012), 128–145. doi: 10.1145/2229012.2229026.

[3]

M.-F. Balcan, A. Blum and Y. Mansour, Item pricing for revenue maximization, In Proceedings of the 9th ACM Conference on Electronic Commerce (EC 2008), (2018), 50–59. doi: 10.1145/1386790.1386802.

[4]

A. Blum and J. D. Hartline, Near-optimal online auctions, In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), 2005, 1156–1163.

[5]

A. Blum, A. Gupta, Y. Mansour and A. Sharma, Welfare and Profit Maximization with Production Costs, In Proceedings of 52th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), (2011), 77–86. doi: 10.1109/FOCS.2011.68.

[6]

T. Chakraborty, E. Even-Dar, S. Guha, Y. Mansour and S. Muthukrishnan., Approximation schemes for sequential posted pricing in multi-unit auctions, In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE 2010), 2010, 158–169. doi: 10.1007/978-3-642-17572-5_13.

[7]

T. Chakraborty, Z. Huang and S. Khanna, Dynamic and non-uniform pricing strategies for revenue maximization, In Proceedings of 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), 2009, 495–504. doi: 10.1109/FOCS.2009.43.

[8]

S. Chawla, J. D. Hartline and R. Kleinberg, Algorithmic pricing via virtual valuations, In Proceedings of the 8th ACM Conference on Electronic Commerce (EC 2007), 2007, 243–251. doi: 10.1145/1250910.1250946.

[9]

G.-H. ChenM.-Y. KaoY.-D. Lyuu and H.-K. Wong, Optimal buy-and-hold strategies for financial markets with bounded daily returns, SIAM J. Compt., 31 (2001), 447-459. doi: 10.1137/S0097539799358847.

[10]

F. Y. L. ChinB. FuJ. GuoS. HanJ. HuM. JiangG. LinH.-F. TingL. ZhangY. Zhang and D. Zhou, Competitive algorithms for unbounded one-way trading, Theor. Comput. Sci., 607 (2015), 35-48. doi: 10.1016/j.tcs.2015.05.034.

[11]

P. DhangwatnotaiT. Roughgarden and Q. Yan, Revenue maximization with a single sample, Games and Economic Behavior, 91 (2015), 318-333. doi: 10.1016/j.geb.2014.03.011.

[12]

R. El-Yaniv, A. Fiat, R. M. Karp and G. Turpin, Competitive analysis of financial games, In Proceedings of 33th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1992), 1992, 372–333. doi: 10.1109/SFCS.1992.267758.

[13]

R. El-YanivA. FiatR. M. Karp and G. Turpin, Optimal search and one-way trading online algorithms, Algorithmica, 30 (2001), 101-139. doi: 10.1007/s00453-001-0003-0.

[14]

H. FujiwaraK. Iwama and Y. Sekiguchi, Average-case competitive analyses for one-way trading, Journal of Combinatorial Optimization, 21 (2011), 83-107. doi: 10.1007/s10878-009-9239-4.

[15]

E. Koutsoupias and G. Pierrakos., On the Competitive Ratio of Online Sampling Auctions., In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE 2010), 2010, 327–338. doi: 10.1007/978-3-642-17572-5_27.

[16]

M. Mahdian, R. Preston McAfee and D. Pennock, The secretary problem with a hazard rate condition, In Proceedings of the 4th International Workshop on Internet and Network Economics (WINE 2008), 2008, 708–715. doi: 10.1007/978-3-540-92185-1_76.

[17]

R. B. Myerson, Optimal auction design, Mathematics of Operations Research, 6 (1981), 58-73. doi: 10.1287/moor.6.1.58.

[18]

Y. Zhang, F. Y. L. Chin and H.-F. Ting, Competitive algorithms for online pricing, In Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON 2011), 6842 (2011), 391–401. doi: 10.1007/978-3-642-22685-4_35.

[19]

Y. ZhangF. Y. L. Chin and H.-F. Ting, Online pricing for bundles of multiple items, Journal of Global Optimization, 58 (2014), 377-387. doi: 10.1007/s10898-013-0043-4.

show all references

References:
[1]

M. Babaioff, S. Dughmi, R. Kleinberg and A. Slivkins, Dynamic pricing with limited supply, In Proceedings of the 13th ACM Conference on Electronic Commerce (EC 2012), 3 (2015), 74–91. doi: 10.1145/2559152.

[2]

A. Badanidiyuru, R. Kleinberg and Y. Singer, Learning on a budget: posted price mechanisms for online procurement, In Proceedings of the 13th ACM Conference on Electronic Commerce (EC 2012), (2012), 128–145. doi: 10.1145/2229012.2229026.

[3]

M.-F. Balcan, A. Blum and Y. Mansour, Item pricing for revenue maximization, In Proceedings of the 9th ACM Conference on Electronic Commerce (EC 2008), (2018), 50–59. doi: 10.1145/1386790.1386802.

[4]

A. Blum and J. D. Hartline, Near-optimal online auctions, In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), 2005, 1156–1163.

[5]

A. Blum, A. Gupta, Y. Mansour and A. Sharma, Welfare and Profit Maximization with Production Costs, In Proceedings of 52th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), (2011), 77–86. doi: 10.1109/FOCS.2011.68.

[6]

T. Chakraborty, E. Even-Dar, S. Guha, Y. Mansour and S. Muthukrishnan., Approximation schemes for sequential posted pricing in multi-unit auctions, In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE 2010), 2010, 158–169. doi: 10.1007/978-3-642-17572-5_13.

[7]

T. Chakraborty, Z. Huang and S. Khanna, Dynamic and non-uniform pricing strategies for revenue maximization, In Proceedings of 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), 2009, 495–504. doi: 10.1109/FOCS.2009.43.

[8]

S. Chawla, J. D. Hartline and R. Kleinberg, Algorithmic pricing via virtual valuations, In Proceedings of the 8th ACM Conference on Electronic Commerce (EC 2007), 2007, 243–251. doi: 10.1145/1250910.1250946.

[9]

G.-H. ChenM.-Y. KaoY.-D. Lyuu and H.-K. Wong, Optimal buy-and-hold strategies for financial markets with bounded daily returns, SIAM J. Compt., 31 (2001), 447-459. doi: 10.1137/S0097539799358847.

[10]

F. Y. L. ChinB. FuJ. GuoS. HanJ. HuM. JiangG. LinH.-F. TingL. ZhangY. Zhang and D. Zhou, Competitive algorithms for unbounded one-way trading, Theor. Comput. Sci., 607 (2015), 35-48. doi: 10.1016/j.tcs.2015.05.034.

[11]

P. DhangwatnotaiT. Roughgarden and Q. Yan, Revenue maximization with a single sample, Games and Economic Behavior, 91 (2015), 318-333. doi: 10.1016/j.geb.2014.03.011.

[12]

R. El-Yaniv, A. Fiat, R. M. Karp and G. Turpin, Competitive analysis of financial games, In Proceedings of 33th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1992), 1992, 372–333. doi: 10.1109/SFCS.1992.267758.

[13]

R. El-YanivA. FiatR. M. Karp and G. Turpin, Optimal search and one-way trading online algorithms, Algorithmica, 30 (2001), 101-139. doi: 10.1007/s00453-001-0003-0.

[14]

H. FujiwaraK. Iwama and Y. Sekiguchi, Average-case competitive analyses for one-way trading, Journal of Combinatorial Optimization, 21 (2011), 83-107. doi: 10.1007/s10878-009-9239-4.

[15]

E. Koutsoupias and G. Pierrakos., On the Competitive Ratio of Online Sampling Auctions., In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE 2010), 2010, 327–338. doi: 10.1007/978-3-642-17572-5_27.

[16]

M. Mahdian, R. Preston McAfee and D. Pennock, The secretary problem with a hazard rate condition, In Proceedings of the 4th International Workshop on Internet and Network Economics (WINE 2008), 2008, 708–715. doi: 10.1007/978-3-540-92185-1_76.

[17]

R. B. Myerson, Optimal auction design, Mathematics of Operations Research, 6 (1981), 58-73. doi: 10.1287/moor.6.1.58.

[18]

Y. Zhang, F. Y. L. Chin and H.-F. Ting, Competitive algorithms for online pricing, In Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON 2011), 6842 (2011), 391–401. doi: 10.1007/978-3-642-22685-4_35.

[19]

Y. ZhangF. Y. L. Chin and H.-F. Ting, Online pricing for bundles of multiple items, Journal of Global Optimization, 58 (2014), 377-387. doi: 10.1007/s10898-013-0043-4.

[1]

C. Xiong, J.P. Miller, F. Gao, Y. Yan, J.C. Morris. Testing increasing hazard rate for the progression time of dementia. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 813-821. doi: 10.3934/dcdsb.2004.4.813

[2]

Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial & Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185

[3]

Lili Ding, Xinmin Liu, Yinfeng Xu. Competitive risk management for online Bahncard problem. Journal of Industrial & Management Optimization, 2010, 6 (1) : 1-14. doi: 10.3934/jimo.2010.6.1

[4]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[5]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057

[6]

Kevin Kuo, Phong Luu, Duy Nguyen, Eric Perkerson, Katherine Thompson, Qing Zhang. Pairs trading: An optimal selling rule. Mathematical Control & Related Fields, 2015, 5 (3) : 489-499. doi: 10.3934/mcrf.2015.5.489

[7]

Ying Li, Miyuan Shan, Michael Z.F. Li. Advance selling decisions with overconfident consumers. Journal of Industrial & Management Optimization, 2016, 12 (3) : 891-905. doi: 10.3934/jimo.2016.12.891

[8]

Miguel Atencia, Esther García-Garaluz, Gonzalo Joya. The ratio of hidden HIV infection in Cuba. Mathematical Biosciences & Engineering, 2013, 10 (4) : 959-977. doi: 10.3934/mbe.2013.10.959

[9]

Jingming Pan, Wenqing Shi, Xiaowo Tang. Pricing and ordering strategies of supply chain with selling gift cards. Journal of Industrial & Management Optimization, 2018, 14 (1) : 349-369. doi: 10.3934/jimo.2017050

[10]

Shuren Liu, Qiying Hu, Yifan Xu. Optimal inventory control with fixed ordering cost for selling by internet auctions. Journal of Industrial & Management Optimization, 2012, 8 (1) : 19-40. doi: 10.3934/jimo.2012.8.19

[11]

Joon Kwon, Panayotis Mertikopoulos. A continuous-time approach to online optimization. Journal of Dynamics & Games, 2017, 4 (2) : 125-148. doi: 10.3934/jdg.2017008

[12]

Robin Cohen, Alan Tsang, Krishna Vaidyanathan, Haotian Zhang. Analyzing opinion dynamics in online social networks. Big Data & Information Analytics, 2016, 1 (4) : 279-298. doi: 10.3934/bdia.2016011

[13]

Ruinian Li, Yinhao Xiao, Cheng Zhang, Tianyi Song, Chunqiang Hu. Cryptographic algorithms for privacy-preserving online applications. Mathematical Foundations of Computing, 2018, 1 (4) : 311-330. doi: 10.3934/mfc.2018015

[14]

Martin Fraas, David Krejčiřík, Yehuda Pinchover. On some strong ratio limit theorems for heat kernels. Discrete & Continuous Dynamical Systems - A, 2010, 28 (2) : 495-509. doi: 10.3934/dcds.2010.28.495

[15]

Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117

[16]

Dag Lukkassen, Annette Meidell, Peter Wall. Multiscale homogenization of monotone operators. Discrete & Continuous Dynamical Systems - A, 2008, 22 (3) : 711-727. doi: 10.3934/dcds.2008.22.711

[17]

Augusto VisintiN. On the variational representation of monotone operators. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 909-918. doi: 10.3934/dcdss.2017046

[18]

Yuhong Dai, Ya-xiang Yuan. Analysis of monotone gradient methods. Journal of Industrial & Management Optimization, 2005, 1 (2) : 181-192. doi: 10.3934/jimo.2005.1.181

[19]

Xiulan Wang, Yanfei Lan, Wansheng Tang. An uncertain wage contract model for risk-averse worker under bilateral moral hazard. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1815-1840. doi: 10.3934/jimo.2017020

[20]

Yinghui Dong, Kam Chuen Yuen, Guojing Wang. Pricing credit derivatives under a correlated regime-switching hazard processes model. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1395-1415. doi: 10.3934/jimo.2016079

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]