• Previous Article
    A survey: Reward distribution mechanisms and withholding attacks in Bitcoin pool mining
  • MFC Home
  • This Issue
  • Next Article
    Relay selection based on social relationship prediction and information leakage reduction for mobile social networks
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

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

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

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

[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.  Google Scholar

[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.  Google Scholar

[1]

Robert Stephen Cantrell, King-Yeung Lam. Competitive exclusion in phytoplankton communities in a eutrophic water column. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020361

[2]

Riccarda Rossi, Ulisse Stefanelli, Marita Thomas. Rate-independent evolution of sets. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 89-119. doi: 10.3934/dcdss.2020304

[3]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117

[4]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[5]

Yantao Wang, Linlin Su. Monotone and nonmonotone clines with partial panmixia across a geographical barrier. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 4019-4037. doi: 10.3934/dcds.2020056

[6]

Mengyu Cheng, Zhenxin Liu. Periodic, almost periodic and almost automorphic solutions for SPDEs with monotone coefficients. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021026

[7]

Kohei Nakamura. An application of interpolation inequalities between the deviation of curvature and the isoperimetric ratio to the length-preserving flow. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1093-1102. doi: 10.3934/dcdss.2020385

[8]

Lateef Olakunle Jolaoso, Maggie Aphane. Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020178

[9]

Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106

[10]

Patrick Martinez, Judith Vancostenoble. Lipschitz stability for the growth rate coefficients in a nonlinear Fisher-KPP equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 695-721. doi: 10.3934/dcdss.2020362

[11]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101

[12]

Fang-Di Dong, Wan-Tong Li, Shi-Liang Wu, Li Zhang. Entire solutions originating from monotone fronts for nonlocal dispersal equations with bistable nonlinearity. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1031-1060. doi: 10.3934/dcdsb.2020152

[13]

Dorothee Knees, Chiara Zanini. Existence of parameterized BV-solutions for rate-independent systems with discontinuous loads. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 121-149. doi: 10.3934/dcdss.2020332

[14]

Xueli Bai, Fang Li. Global dynamics of competition models with nonsymmetric nonlocal dispersals when one diffusion rate is small. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3075-3092. doi: 10.3934/dcds.2020035

[15]

Xing Wu, Keqin Su. Global existence and optimal decay rate of solutions to hyperbolic chemotaxis system in Besov spaces. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021002

 Impact Factor: 

Metrics

  • PDF downloads (107)
  • HTML views (806)
  • Cited by (1)

[Back to Top]