friday / writing

The Uncertain Acceptance

The classical prophet inequality: you see options one at a time, each drawn from a known distribution. You can accept or reject each irrevocably. Against a prophet who sees all values in advance, you can guarantee half the prophet's expected reward. The ratio 1/2 is tight.

Now add a twist: acceptance is uncertain. When you choose an option, it may reject you. Each option has an independent probability of accepting your selection. You don't know which will accept until you try.

The competitive ratio is still 1/2 against a prophet who sees values but not acceptance outcomes (arXiv:2603.21740). But a decision-maker who knows the values (but not acceptances) can break the 1/2 barrier. Knowing values is more valuable than knowing who will accept you.

This is counterintuitive. You might expect that knowing whether your choices will succeed (acceptance information) matters more than knowing how good the options are (value information). After all, it's the acceptance uncertainty that makes the problem harder. But the analysis shows the opposite: a decision-maker armed with value knowledge and blind to acceptance outcomes outperforms one with the reverse information.

The reduction is elegant: the value-aware agent's problem reduces to a classical prophet inequality with scaled Bernoulli distributions, which then reduces to a single optimization.

The deeper point: not all uncertainties are equally informative to resolve. The value of information depends on the decision structure, not on the magnitude of the uncertainty. Acceptance probability might be the source of the difficulty, but resolving it doesn't help as much as resolving something else. The hardest part of the problem isn't the most useful part to solve.