# Spy Auction

talzamir
Posers and Puzzles 14 Jan '13 11:56
1. talzamir
Art, not a Toil
14 Jan '13 11:56
There are two bidders for three items.

Codebook:
* worth \$40,000 to the White Spy, \$10,000 to the Black Spy

Fake passport:
* worth \$25,000 to each

Sniper rifle:
* worth \$10,000 to the White Spy, \$40,000 to the Black Spy

White Spy has \$100,000 to spend, Black Spy \$50,000.

Both make one closed bid, naming a sum for each item.

White Spy does so by having the auctioneer bid for him, using instructions based on all available information, which does NOT include the bid of the Black Spy. However, the Black Spy is aware of the exact instructions by the White Spy.

What are the optimal instructions for the White Spy?
What should the Black Spy then bid?
2. talzamir
Art, not a Toil
14 Jan '13 16:40
Oh. One thing was missing. Victory conditions.

First: Profit. Both spies seek to maximise their profit from the auction.

or

Second: Prestige. Each spy seeks to gain more profit than the other.

Do the different victory conditions cause the optimal strategy to change?
3. apathist
looking for loot
14 Jan '13 18:16
Originally posted by talzamir...
Both make one closed bid, naming a sum for each item.

White Spy does so by having the auctioneer bid for him, using instructions based on all available information, which does NOT include the bid of the Black Spy. However, the Black Spy is aware of the exact instructions by the White Spy...
It looks like the white spy should make his own closed bid - he benefits nothing from putting the auctioneer in the loop. And since the black spy gets to know the information the white spy would give the auctioneer, it actually seems to hurt the white spy to have the auctioneer determine the white's closed bid via instructions. Or is that the point, to handicap the white spy?

I'm so confused. I guess I wouldn't make a good spy.
4. talzamir
Art, not a Toil
14 Jan '13 20:54
White Spy being in a position where his bid or bidding strategy is known to Black Spy is a terrible handicap for sure; and he may only bid by means of a letter to the auctioneer, contents of which Black Spy will know (being proficient as spy; otoh, White Spy is also proficient, and knows that Black Spy will know the contents). On the other hand, Black Spy is handicapped by having available only half the money that White Spy has.

Obviously exact sums won't do well. as Black Spy can outbid White Spy by \$0.01 if he wants. I wonder if some random arrangement could work better? The auctioneer can certainly roll dice, as long as the instructions are crystal clear and independent of the bid by Black Spy.
5. 15 Jan '13 06:432 edits
Originally posted by talzamir
There are two bidders for three items.

Codebook:
* worth \$40,000 to the White Spy, \$10,000 to the Black Spy

Fake passport:
* worth \$25,000 to each

Sniper rifle:
* worth \$10,000 to the White Spy, \$40,000 to the Black Spy

White Spy has \$100,000 to spend, Black Spy \$50,000.

Both make one closed bid, naming a sum for each item.

White Spy d ...[text shortened]... py.

What are the optimal instructions for the White Spy?
What should the Black Spy then bid?
If trying to maximum absolute profit, white spy can bid:
10,001 for codebook
25,000 for passport
39,999 for sniper rifle

The black spy can make no "profit" on the codebook and passport, but he makes \$1 on the sniper rifle, he bids 40,000 on that but can't outbid the white spy on anything else, so the white spy picks up the codebook and passport for a total 29,999 profit and the black spy only makes \$1.

However, if trying to maximise relative profit, this strategy doesn't work out as well for the white spy because the black spy bids 10,002 for the codebook leaving himeself with a \$2 loss, and the white spy now loses \$29,999 so the black spy wins
6. 15 Jan '13 21:30
Originally posted by iamatiger
If trying to maximum absolute profit, white spy can bid:
10,001 for codebook
25,000 for passport
39,999 for sniper rifle

The black spy can make no "profit" on the codebook and passport, but he makes \$1 on the sniper rifle, he bids 40,000 on that but can't outbid the white spy on anything else, so the white spy picks up the codebook and passport for a ...[text shortened]... k leaving himeself with a \$2 loss, and the white spy now loses \$29,999 so the black spy wins
Slight error, sorry

white spy bids:

10,001 for codebook
25,000 for passport
39,998 for sniper rifle

black spy picks up sniper rifle for 39,999 leaving himself 10,001 and making \$1 profit. He loses if he bids on anything else, so the white spy makes 29,999 profit on the codebook.
7. apathist
looking for loot
18 Jan '13 04:36
Originally posted by iamatiger
Slight error, sorry
Could run with that all day and night. run run run
8. 18 Jan '13 13:191 edit
Originally posted by apathist
Could run with that all day and night. run run run
For this problem, can I assume that the black spy cannot tie the auction on any item? If he can do that (with no loss to himself since the item is then not sold to either) then he has a massive advantage over the white spy as he can cancel any white bid at no cost to himself.
9. talzamir
Art, not a Toil
18 Jan '13 14:03
Yes, let's assume there are no ties. Black Spy has to bid higher than White Spy, or White Spy gets the goods and pays the money.
10. 18 Jan '13 21:104 edits
Hmm, when going for kudos, if white spy bids \$24,999 for all items, and assuming bids have to be integers, then...

If white wins all bids, then white makes:
\$15,001 on the codebook,
\$1 on the passport
-\$14,999 (a loss) on the sniper rifle

for a net gain of \$3

black can outbid white on any of these items by bidding \$25,000

if black outbids white on the codebook, he makes a loss of \$15,000 pounds on it, which is a net_gain of \$1

if black outbids white on the passport he makes a loss of 0, and this is a net_gain of \$1

and if black outbids white on the sniper rifle, he makes a gain of 15,000 pounds of it, and this is again a net_gain of \$1.

However black can only outbid white on two items, so white makes \$1 more than black.

white bidding more on any items reduces his gain (or increases his loss) on that item, reducing his profit, I also think bidding less means black makes more money, so \$24,999 is the sweet spot.

This strategy takes advantage of the fact that bids have to be integers. If bids can be any number (which reduceds blacks penalty for overbidding to zero), then the best white can do is bid \$25,000 for everything, making no profit, but at least black makes no profit either

Is \$24999 the right answer (when both spies are trying to outdo each other and bids are integers)?
11. 19 Jan '13 00:432 edits
For instance, if the white spy bids one less than my answer for everything (i.e. 24998), then he potentially makes:

40000-24998 = 15002
25000 - 24998 = 2
24998-10000 = -14998

for a potential net profit of 6

however the black spy bids 24999 on the last two items, so the white spy makes \$15002

The black spy makes
1 + 40000-24999 = 1 + 15001 = 15002

So if the white spy bids 24998 for everything he only equals rather than making \$1 more profit than the black spy.
12. 19 Jan '13 20:192 edits
Hmm, thinking a bit more

White could have the following instruction in pseudocode:

Auction passport first, I bid \$19,999
.. If black wins passport bid \$19,999 for codebook
.... If black wins codebook (he only has 10k now) bid \$10000 for sniper rifle
...... Now white has a profit of 0 and black has lost \$5000, kudos to white
.....If black no bids on codebook then bid \$24,999 for rifle
...... If black no bids on rifle then black has made \$5000 and white has made \$5002
...... If black wins rifle then black has made \$20000 and white has made \$20,001
.. If black no bids on passport white has locked in a \$5001 profit
...... Bid 24,999 for codebook and rifle, the best black can do is buy them both
...... Now white has a \$5001 profit and black has a profit of 0

So there are other approaches, given complex bidding instructions, but I can't find any that let white make more the \$1 over black given best bidding strategy by black. They do though let white get that \$1 margin and still come out with a positive total profit (\$20,001 in this case)
13. 21 Jan '13 00:432 edits
Originally posted by talzamir
Oh. One thing was missing. Victory conditions.

First: Profit. Both spies seek to maximise their profit from the auction.

or

Second: Prestige. Each spy seeks to gain more profit than the other.

Do the different victory conditions cause the optimal strategy to change?
When Maximising profit the best strategy for the white spy (assuming bids must be integers) is as follows:

Bid 10,000 for codebook, black spy makes no profit overbidding on this so this is safe
Bid 17,500 for the Passport
Bid 32,499 for the sniper rifle

To overbid white on both the passport and the rifle would take 50001, which the black spy doesn't have, so he can only overbid on one of them

The black spy makes 7499 by overbidding for the passport
The black spy makes 7500 by overbidding for the sniper rifle

So the black spy bids for the sniper rifle only.

The white spy gets the codebook and the passport for \$27,500 altogether and therefore makes a profit of \$37,5000

The black spy gets the sniper rifle for 32500 and therefore makes a profit of \$7,500

This "optimum" bidding strategy would completely fail if bidding for kudos, black would bid 10,001 for the codebook, let white win the sniper rifle and would win the passport for 17,501. Then black comes out with a \$7,498 profit and white makes a -\$22,499 loss, a relative difference of \$29,997 in black's favour. As I have already shown that white can make a relative profit of at least \$1 when bidding for kudos this proves that the optimum strategies for profit and kudos are completely different.
14. 21 Jan '13 02:401 edit
Considering the bidding for kudos question, and keeping to "simple" bidding strategies (i.e. set a single price for each item) we can derive the following:

Assuming the white spy bids C for the codebook, P for the passport, and R for the rifle

Then white stands to make a potential profit of (40000 - C) + (25000 - P) + (10,000 - R)

We can define the black spies "relative profit" of overbid bidding on any item as
White_spies_potential_profit + black_spies_profit_given_overbid

Since the black spy has to bid \$1 more than the white spy, his profit after overbid on each item is

10000 - C - 1
25000 - P - 1
40000 - R - 1

and his relative change in profit after overbidding is:

Codebook: 40000 - C + 10000 - C - 1 = 50000 - 2C - 1
Passport: 25000 - P + 25000 - P - 1 = 50000 - 2P - 1
Rifle: 10000 - R + 40000 - R - 1 = 50000 - 2P - 1

since the right hand of each equation is the same we can state the whatever the item the white spy has bid on, if the white spies bid is X then the black spies relative profit of overbidding is 50000 -2X - 1 {equation 1}

The above does not take into account that the black spy has only \$50000, to cater for this fact let us consider 4 scenarios:

A) The white spy can makes it unprofitable for the black spy to bid on anything: Given equation 1 this means that the white spy would have to bid 25000 on every item. The black spy would make zero profit and the white spy would also make zero profit (15K on the Codebook, 0 on the Passport and -15K on the rifle)

B) The white spy might try to make it only possible for the black spy to overbid on 1 item:
Clearly this would mean that any one item would have to cost more than half of the black spy's money, i.e. at least \$25001, however then the black spy would bid on nothing, so this is impossible.

C) The white spy can make it possible for the black spy to bid on two items, but not on 3.
In this case each item should cost at least 50001/3 = \$16667; if the white spy bids 16667 for each item and the black spy lets him have (e.g.) the codebook then:
The white spy makes 40000 - 16667 = 23333
The black spy makes 25000 + 40000 - 16668*2 = 31664
However from equation 1 the relative profit of a black overbid reduces the higher white bids as a rate of 2 x Increase, whereas the profit white gets on his one remaining item also reduces, but at a rate of 1 x Increase
This implies that white's bid in this case should be as high as possible while still allowing black to profitably overbid on two items, which means it is optimum for white to bid 24999 if he wants black to overbid on two items.
In this case, white makes (e.g) 40000 - 24999 = \$15001,
and black makes (e,g) 25000 - 24999 - 1 + 40000 - 24999 - 1 = \$15000

D) The white spy can allow the black spy to overbid on everything. This is clearly a non starter as white will make less relative profit than he did when bidding 16667 for each item above.

So the best approach, with simple bidding, and when both spies are going for kudos, is proven to be white bidding \$24999 for every item when he stands to make \$1 more profit than black.
15. 21 Jan '13 20:17
Ahaaa, on the way home from work I think I worked out the optimum answer to the kudos question when complicated bidding instructions are allowed:

The white spy bids 20,000 for the first item auctioned

If he wins that, he bids 25000 for the next item auctioned, otherwise he bids 15000.

If he won either of the two preceding bids, he bids 25000 for the last item auctioned, otherwise he bids 5000 (the black spy only has \$5000 left, so cannot overbid him).

I think this bidding method will let him make \$5000 more profit than the black spy, regardless of the order this items are auctioned in, and regardless of the items the black spy chooses to overbid him on. It also does not need the bids to be integers.