[ExI] bar sinister gets more than you, was:... gets more than you do

[Adrian Tymes]

On Sat, Nov 21, 2015 at 10:06 PM, spike <spike66 at att.net> wrote:

>  I will be damned if I can prove this is the optimal bid but the gradient
> seems to zero out at that point.  Anders?  Adrian?
>
>
Easy.  Even if we allow fractions, the problem stated that there's actual
cash in US dollars, and there are no half-cents in physical US currency as
of today, so there's an even probability of anywhere from 0 to 1 billion
pennies.  We want the number that gives the highest total payout for each
value, and that's a trivial matter of evaluating candidate values against
each of 500,000,001 possibilities (we can eliminate bids over $5,000,000
because we know that either we'd guess too high and get nothing, or we
wouldn't but we'd get less than if we bid $5,000,000).  There are of course
several optimizations that can be taken to reduce run time; for instance,
for each bid X (in pennies), you know already that each possible sum Y < X
will get 0.

We can also simply sum up the possible gains to us.  For bid X, the
probability N that we get nothing, i.e. that X >= Y, is (X+1) /
1,000,000,001.  The probability H of a too-high bid, i.e. that X >= Y/2, is
((2*X)+1) / 1,000,000,001.  With probability 1-H we get X, with probability
H-N we get Y-X (and for each X in this case, the possible Ys are evenly
distributed from X to 2*X, so the average Y is X + (X/2), meaning the
average payout in this case is (X + (X/2)) - X = X/2), and with probability
N we get 0.  So we need to select X to maximize ((1-H) * X) + ((H-N) *
(X/2)) + (N * 0).  Reducing this equation in steps:

((1-(((2*X)+1) / 1,000,000,001)) * X) + (((((2*X)+1) /
1,000,000,001)-((X+1) / 1,000,000,001)) * (X/2)) + 0

(((1,000,000,000-(2*X)) / 1,000,000,001) * X) + ((X / 1,000,000,001) *
(X/2))

X * ((1,000,000,000-(2*X)) + (X/2)) / 1,000,000,001

And this is something that can simply be computed.

Now, we can also do heuristic look-aheads so we don't have to evaluate the
whole set.  As you noted, it seems highly unlikely that X < 250,000,000 is
the value, and indeed evaluating it around there shows an increasing
slope.  The function does not seem to allow for discontinuities or anything
other than a simple curve, so a local maximum (so long as it is not at the
edge of a section evaluated) should be the global maximum.

When I run it, I get a maximum of 333333333 pennies ($3,333,333.33) with an
average expected payout of 166666666.5 pennies ($1,666,666.665).  Check
your floating point buffers if you run the calculation, because the
difference between the payouts for 333333333 and 33333334 is quite small,
but 333333333 is higher (likely because it is closer to what would be the
maximum if fractional pennies were allowed: 333333333.333...).

Note that this is evaluating for maximum payout to us, and we don't care
what the other guy gets.  If the other guy getting as much as or more than
us is a significant problem, the answer may be some variant on, "arrange
for the vault to be burned to the ground unopened and make it look like an
accident".

As to the other problem (the "Anders branch"), it is in fact technically
bounded too: http://www.federalreserve.gov/faqs/currency_12773.htm shows
there is less than $1.4 trillion out there, so this serves as an upper
bound of how much currency the vault could contain.  (It was stipulated
that the vault contains dollars - as in, only US cash.)  But that aside,
I'd bid $10 million: if it's less than $20 million, the other side isn't
waving all that much in my face, while if it's more, I suspect I could
bootstrap $10 million much faster than most extant bad guys could usefully
exploit $10 billion or even $10 trillion.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20151122/cbcee831/attachment.html>