IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v155y2012i2d10.1007_s10957-012-0082-x.html
   My bibliography  Save this article

On the Probability of Correct Selection in Ordinal Comparison over Dynamic Networks

Author

Listed:
  • Hyeong Soo Chang

    (Sogang University)

  • Jiaqiao Hu

    (SUNY)

Abstract

We consider distributed ordinal comparison of selecting the best option which maximizes the average of local reward function values among available options in a dynamic network. Each node in the network knows only his reward function, and edge-connectivity across the nodes changes over time by Calafiore’s model. To estimate each option’s global reward function value, local samples for each option are generated at each node and those are iteratively mixed over the network by a weighted average of local estimates of instantaneous neighbors. Each node selects an option that achieves the maximum of the current global estimates as an estimate of the best option. We establish a lower bound on the probability of correct local-selection at any node, which uniformly converges over the nodes to a lower bound on the probability of correct global-selection by a virtual centralized node with the total available samples.

Suggested Citation

  • Hyeong Soo Chang & Jiaqiao Hu, 2012. "On the Probability of Correct Selection in Ordinal Comparison over Dynamic Networks," Journal of Optimization Theory and Applications, Springer, vol. 155(2), pages 594-604, November.
    • Handle: RePEc:spr:joptap:v:155:y:2012:i:2:d:10.1007_s10957-012-0082-x
    DOI: 10.1007/s10957-012-0082-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-012-0082-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-012-0082-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Pichitlamken, Juta & Nelson, Barry L. & Hong, L. Jeff, 2006. "A sequential procedure for neighborhood selection-of-the-best in optimization via simulation," European Journal of Operational Research, Elsevier, vol. 173(1), pages 283-298, August.
    2. Y-C Ho & C G Cassandras & C-H Chen & L Dai, 2000. "Ordinal optimisation and simulation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 51(4), pages 490-500, April.
    3. Stephen E. Chick & Koichiro Inoue, 2001. "New Two-Stage and Sequential Procedures for Selecting the Best Simulated System," Operations Research, INFORMS, vol. 49(5), pages 732-743, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Batur, D. & Choobineh, F., 2010. "A quantile-based approach to system selection," European Journal of Operational Research, Elsevier, vol. 202(3), pages 764-772, May.
    2. Weiwei Fan & L. Jeff Hong & Barry L. Nelson, 2016. "Indifference-Zone-Free Selection of the Best," Operations Research, INFORMS, vol. 64(6), pages 1499-1514, December.
    3. Shing Chih Tsai & Tse Yang, 2017. "Rapid screening algorithms for stochastically constrained problems," Annals of Operations Research, Springer, vol. 254(1), pages 425-447, July.
    4. Shing Chih Tsai, 2013. "Rapid Screening Procedures for Zero-One Optimization via Simulation," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 317-331, May.
    5. Miguel Lejeune & François Margot, 2011. "Optimization for simulation: LAD accelerator," Annals of Operations Research, Springer, vol. 188(1), pages 285-305, August.
    6. Batur, D. & Choobineh, F., 2012. "Stochastic dominance based comparison for system selection," European Journal of Operational Research, Elsevier, vol. 220(3), pages 661-672.
    7. Lee, Loo Hay & Chew, Ek Peng & Manikam, Puvaneswari, 2006. "A general framework on the simulation-based optimization under fixed computing budget," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1828-1841, November.
    8. H. S. Chang, 2004. "Technical Note: On Ordinal Comparison of Policies in Markov Reward Processes," Journal of Optimization Theory and Applications, Springer, vol. 122(1), pages 207-217, July.
    9. Sigrún Andradóttir & Andrei A. Prudius, 2009. "Balanced Explorative and Exploitative Search with Estimation for Simulation Optimization," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 193-208, May.
    10. L. Jeff Hong & Barry L. Nelson, 2006. "Discrete Optimization via Simulation Using COMPASS," Operations Research, INFORMS, vol. 54(1), pages 115-129, February.
    11. S.Y. Lin & Y.C. Ho, 2002. "Universal Alignment Probability Revisited," Journal of Optimization Theory and Applications, Springer, vol. 113(2), pages 399-407, May.
    12. Tsai, Shing Chih & Chen, Sin Ting, 2017. "A simulation-based multi-objective optimization framework: A case study on inventory management," Omega, Elsevier, vol. 70(C), pages 148-159.
    13. Jie Xu & Barry L. Nelson & L. Jeff Hong, 2013. "An Adaptive Hyperbox Algorithm for High-Dimensional Discrete Optimization via Simulation Problems," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 133-146, February.
    14. H. S. Chang, 2005. "On the Probability of Correct Selection by Distributed Voting in Stochastic Optimization," Journal of Optimization Theory and Applications, Springer, vol. 125(1), pages 231-240, April.
    15. Yijie Peng & Chun-Hung Chen & Michael C. Fu & Jian-Qiang Hu, 2016. "Dynamic Sampling Allocation and Design Selection," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 195-208, May.
    16. David J. Eckman & Shane G. Henderson, 2022. "Posterior-Based Stopping Rules for Bayesian Ranking-and-Selection Procedures," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1711-1728, May.
    17. Zhongshun Shi & Siyang Gao & Hui Xiao & Weiwei Chen, 2019. "A worst‐case formulation for constrained ranking and selection with input uncertainty," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(8), pages 648-662, December.
    18. Healey, Christopher M. & Andradóttir, Sigrún & Kim, Seong-Hee, 2013. "Efficient comparison of constrained systems using dormancy," European Journal of Operational Research, Elsevier, vol. 224(2), pages 340-352.
    19. Demet Batur & Lina Wang & F. Fred Choobineh, 2018. "Methods for System Selection Based on Sequential Mean–Variance Analysis," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 724-738, November.
    20. Daniel Russo, 2020. "Simple Bayesian Algorithms for Best-Arm Identification," Operations Research, INFORMS, vol. 68(6), pages 1625-1647, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:155:y:2012:i:2:d:10.1007_s10957-012-0082-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.