pith. sign in

arxiv: 1907.06001 · v1 · pith:F2CG3HJXnew · submitted 2019-07-13 · 💻 cs.DS · cs.GT

The Two-Sided Game of Googol and Sample-Based Prophet Inequalities

Jos\'e Correa , Andr\'es Cristi , Boris Epstein , Jos\'e A. Soto This is my paper

Pith reviewed 2026-05-24 22:07 UTC · model grok-4.3

classification 💻 cs.DS cs.GT
keywords secretary problemprophet inequalityonline selectiontwo-sided cardssample-based prophetgame of Googol
0
0 comments X

The pith

Algorithms for the two-sided Googol game select the maximum hidden value with probability at least 0.45292.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines a two-sided version of the game of Googol where each of n cards has arbitrary numbers on its two sides. Cards are placed in random order with a random side showing, and the player must choose online which hidden value to accept after seeing all visibles and flipping sequentially. The authors prove that simple algorithms based on three stopping rules achieve a selection probability of at least 0.45292 for the overall maximum hidden value. They also establish an expectation guarantee of 0.63518 relative to the expected maximum. These methods further yield improved guarantees for the prophet secretary problem when distributions are unknown but one sample is given per distribution.

Core claim

In the two-sided game of Googol with arbitrary non-negative numbers on both sides of randomly permuted cards with random visible sides, algorithms exist that select the maximum hidden value with probability at least 0.45292 and achieve an expected selected value at least 0.63518 times the expected maximum hidden value by combining three basic strategies: stopping when larger than all initial visible numbers, stopping when the flipped value is the largest among current visibles, and stopping when it is also larger than its card's other side. The same approach improves the guarantee for the sample-based prophet secretary problem beyond the 1-1/e bound that held only for the i.i.d. case.

What carries the argument

Combination of three stopping strategies based on comparisons to visible numbers and the card's other side.

If this is right

  • The probability of selecting the max hidden value is at least 0.45292.
  • The expected selected hidden value is at least 0.63518 of the expected max.
  • These guarantees hold for arbitrary numbers and random model.
  • The prophet secretary problem with one sample per distribution has a guarantee better than 1-1/e.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Extensions to multi-choice or other online problems with two-sided information may be possible.
  • Analyzing the performance for finite n could yield tighter constants.
  • Applying the strategies to real data with two attributes per item could be tested.

Load-bearing premise

The positions of the cards and the visible sides are chosen uniformly at random.

What would settle it

Finding card values where, over many random permutations and visible choices, the algorithm succeeds with probability below 0.45292.

Figures

Figures reproduced from arXiv: 1907.06001 by Andr\'es Cristi, Boris Epstein, Jos\'e A. Soto, Jos\'e Correa.

Figure 1
Figure 1. Figure 1: Auxiliary functions to analyze ALG(t), as k tends to ∞. We will now study the behaviour of ALG(t) when k is large. For that, define Rk(i, t) = P(ALG(t) ≥ Yi) P(max D ≥ Yi) = 1 1 − (1/2)i X i l=1 k X−1 j=l+1 b(k, t) + a(j, t) 2 j . Rk(t) = P(ALG(t) stops) = 1 2 + k X−1 j=2 (1 − t) j 2 j j . Consider also their limits as k → ∞, which since kb(k, t) → 0 can be computed as R∞(i, t) = 1 1 − (1/2)i X i l=1 X∞ j=… view at source ↗
read the original abstract

The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. We consider a variant of the problem and explore its connections to data-driven online selection. Specifically, we are given $n$ cards with arbitrary non-negative numbers written on both sides. The cards are randomly placed on $n$ consecutive positions on a table, and for each card, the visible side is also selected at random. The player sees the visible side of all cards and wants to select the card with the maximum hidden value. To this end, the player flips the first card, sees its hidden value and decides whether to pick it or drop it and continue with the next card. We study algorithms for two natural objectives. In the first one, as in the secretary problem, the player wants to maximize the probability of selecting the maximum hidden value. We show that this can be done with probability at least $0.45292$. In the second one, similar to the prophet inequality, the player maximizes the expectation of the selected hidden value. We show a guarantee of at least $0.63518$ with respect to the expected maximum hidden value. Our algorithms result from combining three basic strategies. One is to stop whenever we see a value larger than the initial $n$ visible numbers. The second one is to stop the first time the last flipped card's value is the largest of the currently $n$ visible numbers in the table. And the third one is similar to the latter but it additionally requires that the last flipped value is larger than the value on the other side of its card. We apply our results to the prophet secretary problem with unknown distributions, but with access to a single sample from each distribution. Our guarantee improves upon $1-1/e$ for this problem, which is the currently best known guarantee and only works for the i.i.d. case.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript studies a two-sided variant of the secretary/game-of-Googol problem: n cards bear arbitrary non-negative values on each side; positions are a random permutation and each visible side is chosen uniformly at random. The algorithm sees all visible values, then flips cards sequentially and must decide online whether to stop on the revealed hidden value. Two objectives are considered: (i) maximize the probability of selecting the card whose hidden side is the global maximum, and (ii) maximize the expected hidden value of the selected card relative to E[max hidden value]. The authors exhibit explicit algorithms, each formed by combining three simple stopping rules, that achieve probability at least 0.45292 for objective (i) and ratio at least 0.63518 for objective (ii). The same techniques yield an improved guarantee for the prophet-secretary problem when only a single sample from each (possibly non-i.i.d.) distribution is available, surpassing the previous 1-1/e bound that held only in the i.i.d. case.

Significance. If the stated ratios are correct, the work supplies the first non-trivial guarantees for this natural two-sided online-selection model and demonstrates that a simple combination of threshold, record, and two-sided-record rules suffices to beat the classic 1-1/e benchmark even when distributions are unknown and only one sample per distribution is given. The results sit at the intersection of secretary problems, prophet inequalities, and data-driven online algorithms; the explicit, non-asymptotic constants and the reduction to the sample-based prophet-secretary setting are the primary contributions.

minor comments (3)
  1. [Abstract] Abstract, first paragraph after the model description: the numerical constants 0.45292 and 0.63518 are stated without any forward reference to the theorem, section, or lemma that derives them. Adding such pointers would allow a reader to locate the supporting analysis immediately.
  2. [§3] The description of the three stopping rules (stop on value larger than the initial n visibles; stop on current record among visibles; stop on current record that also exceeds the opposite side of its own card) is given only at a high level. A short pseudocode block or numbered list in §3 or §4 would make the combination rule precise.
  3. No table or figure summarizes the three component strategies and the final combined ratios; adding one would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition of its contributions at the intersection of secretary problems and sample-based prophet inequalities, and the recommendation for minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives explicit algorithmic guarantees (0.45292 probability of selecting the max hidden value and 0.63518 ratio to E[max]) by combining three concrete stopping rules under the stated random-permutation + random-side model. No equations reduce a claimed result to a fitted parameter or prior self-citation by construction; the numerical bounds arise from direct analysis of the strategies rather than renaming or re-deriving inputs. The model is standard and externally falsifiable, with no load-bearing self-citation chains or ansatz smuggling visible in the derivation structure.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard assumption that positions and visible sides are chosen uniformly at random; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (1)
  • standard math Cards are placed in random order and each visible side is chosen uniformly at random.
    This is the generative model stated in the first paragraph of the abstract.

pith-pipeline@v0.9.0 · 5901 in / 1303 out tokens · 31465 ms · 2026-05-24T22:07:21.126992+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Beating 1-1/e for ordered prophets

    Abolhassani, M., Ehsani, S., Esfandiari, H., Hajiaghayi, M., Kleinberg, R., Lucier, B. Beating 1-1/e for ordered prophets. STOC 2017

    work page 2017

  2. [2]

    Azar, P., Kleinberg, R., Weinberg., S.M.ProphetInequalitiesWithLimitedInformation.SODA 2014

    work page 2014

  3. [3]

    Prophet secretary: Surpassing the 1-1/e barrier

    Azar, Y., Chiplunkar, A., Kaplan, H. Prophet secretary: Surpassing the 1-1/e barrier. EC 2018

    work page 2018

  4. [4]

    STOC 2010

    Chawla, S., Hartline, J., Malec, D., Sivan, B.Multi-parameter mechanism design andsequential posted pricing. STOC 2010

    work page 2010

  5. [5]

    random vari- ables from an unknown distribution

    Correa, J., Duetting, P., Fischer, F., Schewior, K., Prophet inequalities for i.i.d. random vari- ables from an unknown distribution. EC 2019

    work page 2019

  6. [6]

    Posted price mechanisms for a random stream of customers

    Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T. Posted price mechanisms for a random stream of customers. EC 2017

    work page 2017

  7. [7]

    Recent Developments in Prophet Inequalities.ACM SIGecom Exchanges17(1), 61–70, 2018

    Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T. Recent Developments in Prophet Inequalities.ACM SIGecom Exchanges17(1), 61–70, 2018. 22

    work page 2018

  8. [8]

    From pricing to prophets, and back!.Operations Research Letters, 47(1), 25–29, 2019

    Correa, J., Foncea, P., Pizarro, D., Verdugo, V. From pricing to prophets, and back!.Operations Research Letters, 47(1), 25–29, 2019

    work page 2019

  9. [9]

    Prophet secretary through blind strategies

    Correa, J., Saona, R., Ziliotto, B. Prophet secretary through blind strategies. SODA 2019

    work page 2019

  10. [10]

    The optimum choice of the instant for stopping a Markov process.Soviet Math

    Dynkin, E.B. The optimum choice of the instant for stopping a Markov process.Soviet Math. Dokl. 4, 627–629, 1963

    work page 1963

  11. [11]

    Prophet inequalities made easy: Stochas- tic optimization by pricing non-stochastic inputs

    Düetting, P., Feldman, M., Kesselheim, T., Lucier, B. Prophet inequalities made easy: Stochas- tic optimization by pricing non-stochastic inputs. FOCS 2017

    work page 2017

  12. [12]

    Posted Pricing and Prophet Inequalities with Inaccurate Priors

    Düetting, P., Kesselheim, T. Posted Pricing and Prophet Inequalities with Inaccurate Priors. EC 2019

    work page 2019

  13. [13]

    Prophet secretary for combinatorial auctions and matroids

    Ehsani, S., Hajiaghayi, M., Kesselheim, T., Singla, S. Prophet secretary for combinatorial auctions and matroids. SODA 2018

    work page 2018

  14. [14]

    Prophet secretary

    Esfandiari, H., Hajiaghayi, M., Liaghat, V., Monemizadeh, M. Prophet secretary. ESA 2015

    work page 2015

  15. [15]

    Who solved the secretary problem?Statistical Science4(3), 282–296, 1989

    Ferguson, T.S. Who solved the secretary problem?Statistical Science4(3), 282–296, 1989

    work page 1989

  16. [16]

    Recognizing the maximum of a sequence.J

    Gilbert, J., Mosteller, F. Recognizing the maximum of a sequence.J. Am. Statist. Assoc.61, 35–73, 1966

    work page 1966

  17. [17]

    Automated online mechanism design and prophet inequalities

    Hajiaghayi, M., Kleinberg, R., Sandholm, T. Automated online mechanism design and prophet inequalities. AAAI 2007

    work page 2007

  18. [18]

    Comparisons of stop rule and supremum expectations of i.i.d

    Hill, T., Kertz, R. Comparisons of stop rule and supremum expectations of i.i.d. random variables. The Annals of Probability10(2), 336–345, 1982

    work page 1982

  19. [19]

    A survey of prophet inequalities in optimal stopping theory.Contemporary Mathematics 125, 191–207, 1992

    Hill, T., Kertz, R. A survey of prophet inequalities in optimal stopping theory.Contemporary Mathematics 125, 191–207, 1992

    work page 1992

  20. [20]

    Stop rule and supremum expectations of i.i.d

    Kertz, R. Stop rule and supremum expectations of i.i.d. random variables: A complete com- parison by conjugate duality.Journal of Multivariate Analysis19, 88–112, 1986

    work page 1986

  21. [21]

    Kleinberg, R., Weinberg, S. M. Matroid prophet inequalities. STOC 2012

    work page 2012

  22. [22]

    Semiamarts and finite values.Bull

    Krengel, U., Sucheston, L. Semiamarts and finite values.Bull. Amer. Math. Soc.83, 745–747, 1977

    work page 1977

  23. [23]

    On semiamarts, amarts, and processes with finite value.Adv

    Krengel, U., Sucheston, L. On semiamarts, amarts, and processes with finite value.Adv. in Probability4, 197–266, 1978

    work page 1978

  24. [24]

    Dynamic programming and decision theory.Appl

    Lindley D.V. Dynamic programming and decision theory.Appl. Statist.10, 39–51, 1961. The optimum choice of the instant for stopping a Markov process. Soviet Math. Dokl. 4 627-629

    work page 1961

  25. [25]

    An economic view of prophet inequalities.ACM SIGecom Exchanges16(1), 24–47, 2017

    Lucier, B. An economic view of prophet inequalities.ACM SIGecom Exchanges16(1), 24–47, 2017

    work page 2017

  26. [26]

    Comparisons of threshold stop rule and maximum for independent nonnega- tive random variables.The Annals of Probability12(4), 1213–1216, 1984

    Samuel-Cahn, E. Comparisons of threshold stop rule and maximum for independent nonnega- tive random variables.The Annals of Probability12(4), 1213–1216, 1984. 23

    work page 1984

  27. [27]

    The prophet inequality can be solved optimally with a single set of samples

    Wang, J. The prophet inequality can be solved optimally with a single set of samples. ArXiv preprint, 2018. 24

    work page 2018