Geometric convergence of algorithms in gambling theory

被引：1
|
作者：
Ramakrishnan, S [1 ]
Sudderth, W
机构：
[1] Univ Miami, Dept Math & Comp Sci, Coral Gables, FL 33124 USA
[2] Univ Minnesota, Sch Stat, Minneapolis, MN 55455 USA
来源：
MATHEMATICS OF OPERATIONS RESEARCH | 1998年 / 23卷 / 03期
关键词：
finite gambling problem; algorithm; geometric convergence;
D O I：
10.1287/moor.23.3.568
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In the Dubins and Savage theory of gambling, backward induction provides an algorithm for calculating the optimal return when the gambling problem is leavable. A relatively new algorithm works for nonleavable problems. We show that these algorithms converge geometrically fast for finite gambling problems. Our argument also provides a much simpler proof of convergence for the nonleavable case.
引用
收藏
页码：568 / 575
页数：8
相关论文
共 50 条
  • [21] Integrating geometric programming with rough set theory
    Shiraz, Rashed Khanjani
    Fukuyama, Hirofumi
    OPERATIONAL RESEARCH, 2018, 18 (01) : 1 - 32
  • [22] Rate of convergence for minimum power assignment algorithms in cellular radio systems
    Huang, CY
    Yates, RD
    WIRELESS NETWORKS, 1998, 4 (03) : 223 - 231
  • [23] Rate of convergence for minimum power assignment algorithms in cellular radio systems
    Ching‐Yao Huang
    Roy D. Yates
    Wireless Networks, 1998, 4 : 223 - 231
  • [24] Geometric computation theory for morphological filtering on freeform surfaces
    Lou, Shan
    Jiang, Xiangqian
    Scott, Paul J.
    PROCEEDINGS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 2013, 469 (2159):
  • [25] A new proof of geometric convergence for the adaptive generalized weighted analog sampling (GWAS) method
    Kong, Rong
    Spanier, Jerome
    MONTE CARLO METHODS AND APPLICATIONS, 2016, 22 (03): : 161 - 196
  • [26] DECIDABILITY AND UNIVERSALITY IN THE AXIOMATIC THEORY OF COMPUTABILITY AND ALGORITHMS
    Burgin, Mark
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2012, 23 (07) : 1465 - 1480
  • [27] Modem state of algorithms and systems complication theory
    Cherkaskyy, Mykola
    TCSET 2006: MODERN PROBLEMS OF RADIO ENGINEERING, TELECOMMUNICATIONS AND COMPUTER SCIENCE, PROCEEDINGS, 2006, : 5 - 10
  • [28] Packet Classification Algorithms: From Theory to Practice
    Qi, Yaxuan
    Xu, Lianghong
    Yang, Baohua
    Xue, Yibo
    Li, Jun
    IEEE INFOCOM 2009 - IEEE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-5, 2009, : 648 - +
  • [29] STRONG CONVERGENCE OF SOME ALGORITHMS FOR λ-STRICT PSEUDO-CONTRACTIONS IN HILBERT SPACE
    Yao, Yonghong
    Liou, Yeong-Cheng
    Marino, Giuseppe
    BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2012, 85 (02) : 232 - 240
  • [30] SOLUTION-EXISTENCE AND ALGORITHMS WITH THEIR CONVERGENCE RATE FOR STRONGLY PSEUDOMONOTONE EQUILIBRIUM PROBLEMS
    Duc, Phung M.
    Muu, Le D.
    Quy, Nguyen V.
    PACIFIC JOURNAL OF OPTIMIZATION, 2016, 12 (04): : 833 - 845
12345