A PATH GUESSING GAME WITH WAGERING
| Autor: | Marcus Pendergrass |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Statistics and Probability
Computer Science::Computer Science and Game Theory Correctness Theoretical computer science 91A43 60J20 Coin flipping Probability (math.PR) Stochastic game ComputingMilieux_PERSONALCOMPUTING TheoryofComputation_GENERAL Directed graph Management Science and Operations Research Outcome (game theory) Industrial and Manufacturing Engineering Oracle Combinatorics Path (graph theory) FOS: Mathematics Statistics Probability and Uncertainty Lying Mathematics - Probability Mathematics |
| Zdroj: | Probability in the Engineering and Informational Sciences. 24:375-396 |
| ISSN: | 1469-8951 0269-9648 |
| DOI: | 10.1017/s0269964810000033 |
| Popis: | We consider a two-player game in which the first player (the Guesser) tries to guess, edge-by-edge, the path that second player (the Chooser) takes through a directed graph. At each step, the Guesser makes a wager as to the correctness of her guess and receives a payoff proportional to her wager if she is correct. We derive optimal strategies for both players for various classes of graphs, and we describe the Markov-chain dynamics of the game under optimal play. These results are applied to the infinite-duration Lying Oracle Game, in which the Guesser must use information provided by an unreliable Oracle to predict the outcome of a coin toss. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|