{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T04:27:59Z","timestamp":1751430479741,"version":"3.40.5"},"reference-count":19,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,5,23]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Making a rapid unpredictable decision from <jats:inline-formula>\n                     <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_comp-2022-0243_eq_001.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:mi>N<\/m:mi>\n                        <\/m:math>\n                        <jats:tex-math>N<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula> choices of unequal value is a common control task. When the cost of predictability can be modelled as a penalty hidden under a single option by an intelligent adversary, then an optimal strategy can be found efficiently in <jats:inline-formula>\n                     <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_comp-2022-0243_eq_002.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:mi>O<\/m:mi>\n                           <m:mrow>\n                              <m:mo>(<\/m:mo>\n                              <m:mrow>\n                                 <m:mi>N<\/m:mi>\n                                 <m:mi>log<\/m:mi>\n                                 <m:mi>N<\/m:mi>\n                              <\/m:mrow>\n                              <m:mo>)<\/m:mo>\n                           <\/m:mrow>\n                        <\/m:math>\n                        <jats:tex-math>O\\left(N\\log N)<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula> steps using an approach described by Sakaguchi for a zero-sum hide-search game. In this work, we extend this to two games with multiple parallel predictions, either coordinated or drawn independently from the optimal distribution, both of which can be solved with the same scaling. An open-source code is provided online at https:\/\/github.com\/pec27\/rams.<\/jats:p>","DOI":"10.1515\/comp-2022-0243","type":"journal-article","created":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T19:41:53Z","timestamp":1653334913000},"page":"171-180","source":"Crossref","is-referenced-by-count":2,"title":["Two hide-search games with rapid strategies for multiple parallel searches"],"prefix":"10.1515","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4049-4928","authenticated-orcid":false,"given":"Peter E.","family":"Creasey","sequence":"first","affiliation":[{"name":"AI Navigation, Mercuna Developments , Edinburgh , Scotland"}]}],"member":"374","published-online":{"date-parts":[[2022,5,23]]},"reference":[{"key":"2022081707553239039_j_comp-2022-0243_ref_001","unstructured":"J. von Neumann, O. Morgenstern, and A. Rubinstein, Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition), Princeton, NJ, Princeton University Press, 1944. ISBN 9780691130613."},{"key":"2022081707553239039_j_comp-2022-0243_ref_002","doi-asserted-by":"crossref","unstructured":"P. M. Vaidya, \u201cSpeeding-up linear programming using fast matrix multiplication,\u201d in: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, SFCS \u201989, IEEE Computer Society, USA, 1989, pp. 332\u2013337. ISBN 0818619821, 10.1109\/SFCS.1989.63499.","DOI":"10.1109\/SFCS.1989.63499"},{"key":"2022081707553239039_j_comp-2022-0243_ref_003","unstructured":"S. Jiang, Z. Song, O. Weinstein, and H. Zhang, Faster Dynamic Matrix Inverse for Faster LPs. arXiv e-prints, art. arXiv:2004.07470, April 2020."},{"key":"2022081707553239039_j_comp-2022-0243_ref_004","unstructured":"M. Jack, \u201cTactical position selection,\u201d In: Game AI Pro., S. Game, Ed., Chapter 26. Boca Raton, CRC Press, 2013, pp. 337\u2013359."},{"key":"2022081707553239039_j_comp-2022-0243_ref_005","doi-asserted-by":"crossref","unstructured":"E. Johnson, \u201cGuide to effective auto-generated spatial queries,\u201d in: Game AI Pro 3, chapter 26, S. Rabin, Ed., Boca Raton, CRC Press, 2017, pp. 309\u2013325.","DOI":"10.4324\/9781315151700-26"},{"key":"2022081707553239039_j_comp-2022-0243_ref_006","unstructured":"M. Sakaguchi, \u201cTwo-sided search games,\u201d J. Operat. Res. Soc. Japan, vol. 16, no. 4, pp. 207\u2013225, Dec 1973."},{"key":"2022081707553239039_j_comp-2022-0243_ref_007","unstructured":"M. Dresher, Games of Strategy: Theory and Applications. Englewood Cliffs, NJ, Prentice-Hall, 1961."},{"key":"2022081707553239039_j_comp-2022-0243_ref_008","doi-asserted-by":"crossref","unstructured":"A. Washburn, Two-Person Zero-Sum Games. 4th edition, New York, Springer, 2014.","DOI":"10.1007\/978-1-4614-9050-0"},{"key":"2022081707553239039_j_comp-2022-0243_ref_009","doi-asserted-by":"crossref","unstructured":"L. A. Petrosyan and N. A. Zenkevich, Game Theory. Hackensack, NJ, World Scientific, 2016, ISBN 9789814725385, 10.1142\/9824.","DOI":"10.1142\/9824"},{"key":"2022081707553239039_j_comp-2022-0243_ref_010","unstructured":"T. S. Ferguson, Game Theory, Second edition. Hackensack, NJ, World Scientific, 2014."},{"key":"2022081707553239039_j_comp-2022-0243_ref_011","unstructured":"C. Kiekintveld, M. Jain, J. Tsai, J. Pita, F. Ord\u00f3\u00f1ez, and M. Tambe, \u201cComputing optimal randomized resource allocations for massive security games,\u201d in: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), vol. 1, pp. 689\u2013696, 2009, ISBN 9780981738161, 10.5555\/1558013.1558108."},{"key":"2022081707553239039_j_comp-2022-0243_ref_012","doi-asserted-by":"crossref","unstructured":"J. Letchford and V. Conitzer, \u201cSolving security games on graphs via marginal probabilities,\u201d Proc. AAAI Conference Artif. Intell., vol 27, no. 1, pp. 591\u2013597, June 2013.","DOI":"10.1609\/aaai.v27i1.8688"},{"key":"2022081707553239039_j_comp-2022-0243_ref_013","doi-asserted-by":"crossref","unstructured":"K. T. Lee, \u201cA firing game with time lag,\u201d J. Optim. Theory Appl., vol. 41, no. 4, pp. 547\u2013558, December 1983. ISSN 0022-3239, 10.1007\/BF00934642.","DOI":"10.1007\/BF00934642"},{"key":"2022081707553239039_j_comp-2022-0243_ref_014","doi-asserted-by":"crossref","unstructured":"T. Nakai, \u201cA sequential evasion-search game with a goal,\u201d J. Operat. Res. Soc. Japan, vol. 29, no. 2, pp. 113\u2013122, 1986, 10.15807\/jorsj.29.113.","DOI":"10.15807\/jorsj.29.113"},{"key":"2022081707553239039_j_comp-2022-0243_ref_015","doi-asserted-by":"crossref","unstructured":"S. Alpern, R. Fokkink, R. Lindelauf, and G.-J. Olsder, \u201cThe \u2018Princess and Monster\u2019 game on an interval,\u201d SIAM J. Control Optimization, vol. 47, no. 3, pp. 1178\u20131190, 2008.","DOI":"10.1137\/060672054"},{"key":"2022081707553239039_j_comp-2022-0243_ref_016","doi-asserted-by":"crossref","unstructured":"J. C. Deville and Y. Till\u00e9, \u201cUnequal probability sampling without replacement through a splitting method,\u201d Biometrika, vol. 85, pp. 89\u2013101, March 1998, 10.1093\/biomet\/85.1.89.","DOI":"10.1093\/biomet\/85.1.89"},{"key":"2022081707553239039_j_comp-2022-0243_ref_017","doi-asserted-by":"crossref","unstructured":"J. Croucher, \u201cApplication of the fundamental theorem of games to an example concerning antiballistic missile defense,\u201d Naval Res. Logistics Quarter., vol. 22, pp. 197\u2013203, March 1975, 10.1002\/NAV.3800220117.","DOI":"10.1002\/nav.3800220117"},{"key":"2022081707553239039_j_comp-2022-0243_ref_018","doi-asserted-by":"crossref","unstructured":"V. J. Baston and A. Y. Garnaev, \u201cA search game with a protector,\u201d Naval Res. Logistics, vol. 47, no. 2, pp. 85\u201396, 2000. https:\/\/eprints.soton.ac.uk\/29734\/.","DOI":"10.1002\/(SICI)1520-6750(200003)47:2<85::AID-NAV1>3.0.CO;2-C"},{"key":"2022081707553239039_j_comp-2022-0243_ref_019","unstructured":"W. H. Ruckle, Geometric Games and their Applications, Pitman, 1983."}],"container-title":["Open Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2022-0243\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2022-0243\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,17]],"date-time":"2022-08-17T08:00:39Z","timestamp":1660723239000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2022-0243\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,1]]},"references-count":19,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,3,16]]},"published-print":{"date-parts":[[2022,3,16]]}},"alternative-id":["10.1515\/comp-2022-0243"],"URL":"https:\/\/doi.org\/10.1515\/comp-2022-0243","relation":{},"ISSN":["2299-1093"],"issn-type":[{"type":"electronic","value":"2299-1093"}],"subject":[],"published":{"date-parts":[[2022,1,1]]}}}