FE8 FE8 Auction, bid turn-count handicaps experiment

[JudgeWargrave]

[spoiler=Chapter 18: Two Faces of Evil - 5/109 turns, 0/8 RNs]

Everyone busts out their Sacred Twin and starts making omelets. Forde+Ross are warped north, Ephraim and Joshua are warped east, Myrrh is warped northeast, then Warp gets Hammerned. Forde gets the honor of the boss-kill with Vidofnir, his massive movement range preventing the boss from getting to do anything. Pure water keeps Ross alive T1EP, after which no one is near enough to even attack him and he squashes eggs at 5hp until the end of the chapter. Myrrh burns herself to kill a gorgon, but patches herself up with a vulnerary, so she never faces a chance of death. Natasha uses Rescue on Moulder to get him to the north in time to get the last eggs.

Warp 5/5 Hammerne 1/3 Rescue 2/3

[spoiler=Chapter 19: Last Hope - 1/110 turns, 0/8 RNs]

Warp Ross to Boss. Colm's torch came in handy to illuminate a tile to actually put Ross on.

Warp 4/5 Hammerne 1/3 Rescue 2/3

[spoiler=Chapter 20: Darkling Woods - 2/112 turns, 0/8 RNs]

Thank god the mountain range is slightly less wide at the bottom, so Natasha's current 13 mag is able to Warp Moulder across. Moulder Rescues Tethys and she dances him. Eirika takes Warp from Natasha and drinks a Pure Water, then gets Rescued as well. Myrrh flies just to the end of the mountain range, while Joshua takes a ride with Forde and Kyle to actually get in range to do something.

Next turn enemies swarm over. Tethys dodges in a forest while Eirika tanks hits down to 14 hp. Joshua and Forde rush in with their Sacred Twins to kill some blocking enemies, then Moulder+Tethys Warp Eirika and Myrrh. Myrrh re-kills Morva. Ephraim and Kyle manage a round of combat.

Warp 1/5 Hammerne 1/3 Rescue 0/3

[spoiler=Final: Sacred Stone - 2+1/115 turns, 0/8 RNs]

Warp gets Hammerned by Natasha immediately, giving us the last 5.

Lyon exactly kills barriered Ross in one hit, making Ross's chance of success 0.3% if he and Myrrh warp in turn 2. I am not going back multiple chapters to get Ross a better level up. His last level was in Ch18, and it procced res so I would have to change it to HP+Res and redo everything from there. Fortunately there's enough Warp left to send in two more people, we just need to put Ross and Myrrh over there T1 and tank EP. They drink Pure Waters and Ross goes in front to dodge tank the stone spells with his much greater avoid. Then Forde and Ephraim clear the way T2 for Myrrh to chip and Ross to get a much more reliable 18% crit.

Warp 1/5 Hammerne 0/3 Rescue 0/3

Final part 2

Forde gets danced and whiffs his Vidofnir, the Renais twins chip in, sadly not activating any kind of triangle attack, and then Moulder uses the very last Warp to get Ross up, critting with Garm for exactly enough damage! (Ephraim 20, Eirika 16, Ross 28*3=84) I could have 'burned' an RN by trying to Silence the Demon King with Natasha, but that wouldn't actually help Forde hit, so if any unit had less strength I would have needed to burn more RNs. (Forde does 10 dmg) Fortunately that can be avoided, meaning I went without burning RNs since Ch8!

[spoiler=Characters and Turncount Summary]

Stat dev hp str skl spd def res luck %tile

Eirika -1.0 1.0 -2.0 1.0 2.0 1.0 -2.0 67.5
Moulder 2.4 4.8 4.0 3.8 3.5 1.5 -0.6 99.9
Ross -3.7 0.5 2.2 6.7 7.3 1.8 1.6 99.4
Garcia 0.6 3.3 2.8 1.4 2.5 1.3 1.8 99.6
Colm 2.5 4.8 3.8 0.3 1.5 1.4 1.9 99.7
Natasha 2.5 3.4 0.3 1.6 2.3 0.9 0.4 99.9
Joshua 1.8 3.1 0.3 1.3 4.2 2.2 2.8 99.9
Ephraim 1.4 0.4 1.4 1.6 3.8 -2.0 1.0 98.0
Forde -0.6 1.6 7.0 2.8 1.8 -3.0 0.4 99.4
Kyle 1.4 1.0 3.4 1.4 2.5 0.2 1.2 99.3
Tethys -0.4 -0.2 -0.4 -0.8 0.8 0.0 -0.2 61.1
Myrrh 1.0 0.0 -0.5 0.5 -3.0 -2.0 0.0 22.3

Why Ross has a higher Def and Spd deviation than Moulder has Mag deviation, I don't know. He had Garm so it's not like he even needed so much speed. Myrrh actually managed to be below average, somehow?

Eirika's stats were pretty middle of the road. Actually she gained exactly 20 levels, meaning all her deviations were whole numbers.

Moulder handicap: 6.895

Moulder, of course, went nuts on Magic. Pretty sure his Slayer skill was never used, except on an egg I guess. Of course his Warp capability, with an initial 9 range, was crucial to these turn-counts. I mean, the man threw out 4 warps in Final 1, and since there were some people being carried he technically warped 5 people in Chapter 18. Much respect.

Ross handicap: 7.385

Ross was my go-to boss killer in the second half of the game, killing Demon King, Lyon, Riev, Lyon (again), Orson, Valter, and Aias. The crit rate was obviously a big part of that, but the mobility of his classes was also key. Peak-walking helped in Ch12A, and the pirate water-walking was integral in Ch7.

Garcia handicap: 9.415

Garcia was very much a first-half-of-the-game unit. Very helpful in the early combat, but dropped off just as Ross picked up. If I were to do it again, I would try him as a Hero, but I don't think it would save or lose a turn either way. He's mostly on easy mop-up duty from Ch 14 on. I'm not really sure he's worth more than Ross. Of course there's a question of whether redundancy drove his value down. If he had his hands on Garm in a Rossless team, he would be better than he was here.

Colm handicap: 3.04

He did thiefly duties and chipped in during combat here and there. A thief isn't so crucial when there are plentiful door and chest keys though. I guess Moulder owed 1 staff range to him stealing an Energy Ring. Sadly the man didn't even get to A Swords. Starting at E rank really sucks. Oh, his vision in Ch19 was useful I guess. I think Natasha could cast Torch far enough though.

Natasha handicap: 5.05

Overshadowed by a certain 'stache, but actually a second staffer was a complete game changer. Three uses per turn rather than two meant it was never a problem to Hammerne the Warp. She even did some warping herself despite her smaller range, specifically in 16 and 20, and saved a turn by doing so both times. The high movement and canto of the Valkyrie was useful in Ch18, but not really anywhere else.

Joshua handicap: 4.425

A better Colm that can't steal or pick, or move 6 prepromoted. Killed Caellach and what's his face from Ch9, wielded Audhulma to kill a few things Ch18 and Ch20. Just a filler unit beyond that, pretty good at combat early on but contributed very little after Ch15.

Ephraim didn't see much action of course. Did his job 1HKOing monsters and being a horse in endgame. Opened up a path to Lyon and chipped the Demon King.

Forde handicap: 6.7

Kyle handicap: 7.605

The fact that I added a random factor to my bids Somehow or other Kyle's handicap was higher than Forde's while Forde clearly took the lead this playthrough. It just worked out that he got more exp in 5x/8 where there's no choice of deployment, and that advantage snowballed as more resources went into the better of the pair: first a bunch of stat boosters for Ch9, then the Knight's Crest, then the Boots. The final factor was that Forde quickly reached S rank Lances, but Kyle never did. Vidofnir and 10 move made Forde superior to the Lords in endgame utility, while Kyle was their inferior. Still, 8 move, canto, and decent combat with a Silver Lance, Javelin, and Killing Edge meant Kyle was not bad by any means.

Standard game changers. Myrrh got three levels on one enemy phase (Final T1EP) that dragged her percentile down, but its deceptive to view things in that way alone: three bad levels are much better than one good one.

Dat Ch9 tho. Redo

Other than Ch9, where could I have saved? Nothing's jumping out at me. Ch3 maybe. I don't think the four units I had could handle Ch4 in less than 5 turns. Ch5 I had visiting to do. I don't believe Ch7 could be shortened without a really rigged Ross and Halberd on the boss who has somehow equipped the javelin...Ch8, maybe if Eirika goes into the armor room first and crits her way through multiple knights. Yeah, maybe...110 would be possible? I'm pretty happy with 115!

Final score: 115+50=165, behind Horace's 129+13=142 by 23. Egg was 10 behind Horace as of Ch5x, so if she can avoid losing 13 more turns I'll be 3rd, 2nd if not.

This was a lot of fun. This was my first LTC run, ever. It took up a lot of time over 16 days, much of it working on my lua script, which was equally fun/frustrating as actually doing the chapters. Now that the initial work is done though, the dividends next time will already be paid for.

I'll be crunching some numbers to try and create more accurate handicap estimates. What's clear is that I overestimated. Since my handicap of 50 was 23 "too high" a good starting point might simply be dividing them all by 2. Of course Horace's handicap of 13 might have also been "too low".

I also have some thoughts about the auction system itself. It met the goals of starting quickly, removing last/first pick (dis)advantage, and creating novel teams--but failed in creating balanced teams+handicaps. Part of that was the newness of the system, and an initial wacky miscalibration is acceptable in my mind, but it could have been made better to avoid that. Capping maximum and minimum team size would help. I also want to try a different tiebreak system (although we didn't use the existing one, as bids drop, ties would become common) and handicap adjustment system while balancing teams, to prevent very high/very low bids from producing degenerate results.

[JudgeWargrave]

So I reworked the auction system and I think it's much better now. But before I explain the changes, let me show how it would have affected this draft.

[spoiler=Auction process (long)]
-BIDS-
.Wargrave.Egg .Horace .Carmine .
Franz 10.84 |05.00 |10.10 |16.00 |
Gilliam 06.63 |01.00 |04.10 |14.00 |
Moulder 04.79 |01.00 |02.10 |09.00 |
Vanessa 11.11 |05.00 |11.10 |22.00 |
Ross 04.77 |00.50 |02.10 |10.00 |
Garcia 06.83 |01.00 |04.10 |12.00 |
Neimi 02.05 |00.30 |01.10 |03.00 |
Colm 03.04 |02.00 |02.10 |03.00 |
Artur 07.39 |04.00 |08.10 |17.00 |
Lute 05.59 |03.00 |04.10 |12.00 |
Natasha 04.10 |02.00 |00.10 |06.00 |
Joshua 03.85 |02.00 |01.10 |05.00 |
Forde 04.40 |03.00 |02.10 |09.00 |
Kyle 06.21 |03.00 |03.10 |09.00 |
Tana 08.86 |04.00 |05.10 |14.00 |
Amelia 02.02 |00.10 |01.10 |01.00 |
Innes 02.02 |01.00 |01.10 |07.00 |
Gerik 04.03 |02.00 |02.10 |12.00 |
Marisa 00.01 |00.30 |00.10 |00.00 |
L'Arachel 00.99 |01.00 |00.10 |02.00 |
Dozla 02.56 |01.00 |01.10 |03.00 |
Cormag 02.88 |01.00 |03.10 |08.00 |
Saleh 05.81 |04.00 |05.10 |17.00 |
Ewan 00.60 |02.00 |00.10 |00.00 |
Rennac 00.44 |03.00 |00.10 |02.00 |
Duessel 00.97 |02.00 |01.10 |02.00 |
Knoll 01.06 |02.00 |00.10 |02.00 |
Syrene 00.53 |01.00 |00.10 |02.00 |

CAP BIDS
reducing Carmine 's bid on Franz : 16.00->15.56
reducing Carmine 's bid on Gilliam : 14.00->7.04
reducing Wargrave's bid on Moulder : 4.79->4.65
reducing Carmine 's bid on Moulder : 9.00->4.65
reducing Carmine 's bid on Vanessa : 22.00->16.33
reducing Wargrave's bid on Ross : 4.77->3.90
reducing Carmine 's bid on Ross : 10.00->3.90
reducing Carmine 's bid on Garcia : 12.00->7.16
reducing Carmine 's bid on Neimi : 3.00->2.07
reducing Carmine 's bid on Artur : 17.00->11.69
reducing Carmine 's bid on Lute : 12.00->7.61
reducing Wargrave's bid on Natasha : 4.10->3.15
reducing Carmine 's bid on Natasha : 6.00->3.15
reducing Carmine 's bid on Joshua : 5.00->4.17
reducing Carmine 's bid on Forde : 9.00->5.70
reducing Carmine 's bid on Kyle : 9.00->7.39
reducing Carmine 's bid on Tana : 14.00->10.78
reducing Wargrave's bid on Amelia : 2.02->1.32
reducing Carmine 's bid on Innes : 7.00->2.47
reducing Carmine 's bid on Gerik : 12.00->4.88
reducing Egg 's bid on Marisa : 0.30->0.02
reducing Horace 's bid on Marisa : 0.10->0.02
reducing Carmine 's bid on L'Arachel: 2.00->1.25
reducing Carmine 's bid on Dozla : 3.00->2.80
reducing Carmine 's bid on Cormag : 8.00->4.19
reducing Carmine 's bid on Saleh : 17.00->8.95
reducing Wargrave's bid on Ewan : 0.60->0.15
reducing Egg 's bid on Ewan : 2.00->0.15
reducing Egg 's bid on Rennac : 3.00->0.81
reducing Carmine 's bid on Rennac : 2.00->0.81
reducing Egg 's bid on Knoll : 2.00->1.74
reducing Carmine 's bid on Knoll : 2.00->1.74
reducing Egg 's bid on Syrene : 1.00->0.95
reducing Carmine 's bid on Syrene : 2.00->0.95

-BIDS-
.Wargrave.Egg .Horace .Carmine .
Franz 10.84 |05.00 |10.10 |15.56 |
Gilliam 06.63 |01.00 |04.10 |07.04 |
Moulder 04.65 |01.00 |02.10 |04.65 |
Vanessa 11.11 |05.00 |11.10 |16.33 |
Ross 03.90 |00.50 |02.10 |03.90 |
Garcia 06.83 |01.00 |04.10 |07.16 |
Neimi 02.05 |00.30 |01.10 |02.07 |
Colm 03.04 |02.00 |02.10 |03.00 |
Artur 07.39 |04.00 |08.10 |11.69 |
Lute 05.59 |03.00 |04.10 |07.61 |
Natasha 03.15 |02.00 |00.10 |03.15 |
Joshua 03.85 |02.00 |01.10 |04.17 |
Forde 04.40 |03.00 |02.10 |05.70 |
Kyle 06.21 |03.00 |03.10 |07.39 |
Tana 08.86 |04.00 |05.10 |10.78 |
Amelia 01.32 |00.10 |01.10 |01.00 |
Innes 02.02 |01.00 |01.10 |02.47 |
Gerik 04.03 |02.00 |02.10 |04.88 |
Marisa 00.01 |00.02 |00.02 |00.00 |
L'Arachel 00.99 |01.00 |00.10 |01.25 |
Dozla 02.56 |01.00 |01.10 |02.80 |
Cormag 02.88 |01.00 |03.10 |04.19 |
Saleh 05.81 |04.00 |05.10 |08.95 |
Ewan 00.15 |00.15 |00.10 |00.00 |
Rennac 00.44 |00.81 |00.10 |00.81 |
Duessel 00.97 |02.00 |01.10 |02.00 |
Knoll 01.06 |01.74 |00.10 |01.74 |
Syrene 00.53 |00.95 |00.10 |00.95 |

REASSIGNING
Tiebreak: Carmine ->Moulder ->Wargrave
Tiebreak: Carmine ->Ross ->Wargrave
Tiebreak: Carmine ->Natasha ->Wargrave
Tiebreak: Egg ->Marisa ->Horace
Tiebreak: Wargrave->Ewan ->Egg
Tiebreak: Carmine ->Rennac ->Egg
Tiebreak: Carmine ->Duessel ->Egg
Tiebreak: Carmine ->Knoll ->Egg
Tiebreak: Carmine ->Syrene ->Egg
From overfilled: Carmine ->Neimi ->Wargrave, 00.02
From overfilled: Carmine ->Dozla ->Wargrave, 00.24
From overfilled: Carmine ->L'Arachel->Egg , 00.25
From overfilled: Carmine ->Joshua ->Wargrave, 00.32
From overfilled: Wargrave->Natasha ->Carmine , 00.00
From overfilled: Carmine ->Garcia ->Wargrave, 00.33
From overfilled: Wargrave->Ross ->Carmine , 00.00
From overfilled: Carmine ->Gilliam ->Wargrave, 00.41
From overfilled: Wargrave->Moulder ->Carmine , 00.00
From overfilled: Carmine ->Innes ->Wargrave, 00.45
From overfilled: Wargrave->Colm ->Carmine , 00.04
From overfilled: Carmine ->Gerik ->Wargrave, 00.85
From overfilled: Wargrave->Amelia ->Horace , 00.22
From overfilled: Carmine ->Colm ->Horace , 00.90
From overfilled: Carmine ->Cormag ->Horace , 01.09
From overfilled: Carmine ->Natasha ->Egg , 01.15
From overfilled: Carmine ->Kyle ->Wargrave, 01.18
From overfilled: Wargrave->Innes ->Horace , 00.92
From overfilled: Carmine ->Forde ->Wargrave, 01.30
From overfilled: Wargrave->Neimi ->Horace , 00.95
From overfilled: Carmine ->Ross ->Horace , 01.80

[spoiler=Results]

Wargrave 7
Gilliam 06.63 = 06.63
Garcia 06.83 = 06.83
Joshua 03.85 = 03.85
Forde 04.40 = 04.40
Kyle 06.21 = 06.21
Gerik 04.03 = 04.03
Dozla 02.56 = 02.56
34.51, relative hc 25.73

Egg 7
Natasha 02.13 = 02.00 + 00.13
L'Arachel 01.00 = 01.00
Ewan 00.15 = 02.00 - 01.85
Rennac 00.81 = 03.00 - 02.19
Duessel 02.00 = 02.00
Knoll 01.74 = 02.00 - 00.26
Syrene 00.95 = 01.00 - 00.05
08.78, relative hc 00.00

Horace 7
Ross 02.77 = 02.10 + 00.67
Neimi 01.47 = 01.10 + 00.37
Colm 02.68 = 02.10 + 00.58
Amelia 01.10 = 01.10
Innes 01.83 = 01.10 + 00.73
Marisa 00.02 = 00.10 - 00.09
Cormag 03.10 = 03.10
12.97, relative hc 04.19

Carmine 7
Franz 15.56 = 16.00 - 00.44
Moulder 04.65 = 09.00 - 04.35
Vanessa 16.33 = 22.00 - 05.67
Artur 11.69 = 17.00 - 05.31
Lute 07.61 = 12.00 - 04.39
Tana 10.78 = 14.00 - 03.22
Saleh 08.95 = 17.00 - 08.05
75.57, relative hc 66.79

Wargrave: Gilliam, Garcia, Joshua, Forde, Kyle, Gerik, Dozla, 34.51, relative hc 25.73
Egg: Natasha, L'Arachel, Ewan, Rennac, Duessel, Knoll, Syrene, 08.78, relative hc 00.00
Horace: Ross, Neimi, Colm, Amelia, Innes, Marisa, Cormag, 12.97, relative hc 04.19
Carmine: Franz, Moulder, Vanessa, Artur, Lute, Tana, Saleh, 75.57, relative hc 66.79

[spoiler=Explanation and analysis of the new system]The most obvious difference here is that Carmine's handicap has been reduced by about 50, but there are other, more subtle improvements.

The first difference is that bids are capped such that no bid is 50% greater than the average bid. As Carmine's final handicap shows, this is still very large and leaves plenty of room to make bad overbids, but putting some limit on it is much better than no limit. In fact, we all had some of our bids reduced in this way; even Horace had his Marisa bid reduced. Not only does this bail out Carmine, but it mitigates the spillover from his bids to other player's team.

Next, ties are broken in recruitment order, going to the player with the lower handicap at the time.

Then, the overfilled teams are reduced in size. I've changed my perspective on team size: the should all be within at least 1 of each other. Each team member is progressively less important than the next, so larger teams paying a handicap for their 8th unit are worse off than a team of 5 paying that same handicap to make it their sixth unit. Also, larger teams would be disproportionally hurt by the overbids of others. So team size is fixed at 7 here.

Now, how units are pulled from overfilled teams is changed. Rather than least absolute valued, they are pulled by order of least relative valued. This makes more sense, and reduces the amount of "bid preference violation" that the rebalancing does: it's better to move a unit from a person that bid 10 to a person that bid 9.5, than it is to move a unit from a person that bid 5 to a person that bid 2. In the old system, the second case would happen.

One more difference: if you are assigned a unit by the balancing that you didn't win outright via highest bid, the handicap will be set to the average of every player's bid other than yourself. This gives you the unit at the best cost the system can create, while providing no incentive to game the system by bidding all 0s.

Overall this set up did much better. Although Egg is still screwed teamwise and Carmine screwed handicapwise, these are, I think, unavoidable consequences of the bids themselves, and in Carmine's case the issue was greatly reduced. (Arguably Egg is also better off, with Natasha instead of Marisa and 3.52 smaller handicap too.) What is gained, objectively, is that the amount people are paying above what they bid has been reduced a lot. Only Horace is paying more than his bids, and then only by 2.27! In the old system, Horace paid 6.16 more, Egg paid 1 more, and I paid about 12.5 more. So the total "dissatisfaction from paying more than bid" is reduced from 19.76 to 2.27, or only 11.5% as much dissatisfaction!

(Of course, there is also "dissatisfaction from others paying less than they bid", but I don't think this is a valid grievance. By definition, either they still paid more than you, in which case you think they still got a bad deal; they paid the same as your bid, in which case you should be ambivalent; or they paid less than you, in which case they must have paid their full bid anyway, and losing some of your units in that way would be an necessary consequence of any system that balances teams.)

[General Horace]

I think that works a lot better. Along with people likely not bidding as high in a future draft, things would work out a lot nicer.

[ruadath]

Just saw this thread now and this idea looks pretty interesting. As someone who knows things about auction theory, I would note that second-price auctions generally tend to be more fair/successful (in more ways than one) than first-price auctions; the way this works is that the highest bidder wins the unit, but only pays the price (in turns) of the second highest bidder.

This seems to me like it would be a much simpler fix than some complicated bid modification system (with the cap bids or whatever). People are also encouraged to bid their "true valuation" for a unit rather than trying to game the system.

Edited November 24, 2016 by ruadath

[JudgeWargrave]

Just saw this thread now and this idea looks pretty interesting. As someone who knows things about auction theory, I would note that second-price auctions generally tend to be more fair/successful (in more ways than one) than first-price auctions; the way this works is that the highest bidder wins the unit, but only pays the price (in turns) of the second highest bidder.

This seems to me like it would be a much simpler fix than some complicated bid modification system (with the cap bids or whatever). People are also encouraged to bid their "true valuation" for a unit rather than trying to game the system.

Thanks for pointing out 2nd price auctions! I had vague knowledge of the existence of such things, but didn't know that bidding true valuation was optimal. I foolishly assumed that overbidding would be a viable strategy, since you didn't have to pay your own bid, not really realizing that this can't benefit you more than truthful bidding. Either your truthful bid would have won anyway, or the other persons bid would be higher than your truthful bid, meaning you wouldn't want to win at the price they set!

But the team balancing complicates things. Are you still incentivized to bid your true valuation if it is possible to win a unit without the highest bid? I'm not sure. At the very least, it doesn't appear to be strictly dominant.

Consider the case of two players P₁ and P₂, and two units U₁ and U₂ . Now say P₁ values the units at (1, 2), and P₂ values them at (5, 10). If we assume P₂ bids truthfully, P₁ would be better served by bidding (0, 4.9). The result of this is P₁ gets U₁ for 0, and P₂ gets U₂ for 4.9. If P₁ bid truthfully, the result would be P₁ gets U₁ for 1, and P₂ gets U₂ for 2, which is clearly worse from P₁'s perspective. P₁ paid 1 more, and P₂ paid 2.9 less, due to P₁'s honesty. Of course P₁ probably doesn't have the foreknowledge of P₂'s valuations to make this exact scenario happen, but it theoretically could happen. Dishonest bids aren't strategically dominated by honest bids as in a simple 2nd price auction if everyone must win the same number of items.

The 2nd price auction doesn't consider one person trying to inflate the winner's price because generally there's no rational motive for this (other than the seller using a shill to increase profits, but that isn't relevant here because the "seller" isn't even an entity that can profit). If you lose the bid, the only point in increasing the winner's price is spite.

However, in this case, there's an obvious rational incentive: you are about to enter a competition with the unit's winner, a competition whose victory was the sole point of your bids, and by inflating their price you inflate their handicap, and your chances of winning! The payoff of a strategy is not merely (units acquired - handicap assigned): the units and handicaps of other players are just as relevant.

To quote the wikipedia article on the subject: the statement "If max b_j > b_i then the bidder would lose the item either way so the strategies have equal payoffs in this case" is no longer true. You lose the unit either way, but hurt an opponent more by overbidding, which is a better payoff. The other two cases remain true, but not this one.

Similarly, for underbidding: "If max b_j > v_i then the bidder would lose the item with a truthful bid as well as an underbid, so the strategies have equal payoffs for this case" is no longer true for similar reasons, though it just makes the underbidding strategy worse. Underbidding is instead better when you win in last place, i.e. bid 0 and get the unit anyway via team balancing.

So, truthful bidding does not dominate under- or over-bidding if we balance teams and use 2nd price. Of course, I haven't exactly demonstrated any such thing for the system of determining price via average of other bids either, and I assume it also isn't true in that case....

[ruadath]

To quote the wikipedia article on the subject: the statement "If max b_j > b_i then the bidder would lose the item either way so the strategies have equal payoffs in this case" is no longer true. You lose the unit either way, but hurt an opponent more by overbidding, which is a better payoff. The other two cases remain true, but not this one.

Right, it's no longer truthful dominant in this case, but I feel like it is somewhat closer (although maybe that's not something you can easily quantify). I'll try and see if I can think up of a better alternative (though I'm not sure I can).

I think what you want might be a VCG mechanism (in particular, look at the following example). This assumes 1 unit for each bidder, though you can probably modify it and get fair results. In fact, now that I think about it, this is probably ideal, since the primary weakness of VCG is that it doesn't maximize profits for the auctioneer (sometimes they lose money!) but we don't care about that in this case.

Yeah, so you can do this just in a pretty straightforward manner with just a simple modification to the standard bipartite maximal matching algorithm. It's polynomial time too, so no worries about tractability. Yay for operations research!

EDIT: Actually this might still be wrong because you can still make other people overpay with high bids across the board (maybe). I think an easy way to fix this should just be to impose a penalty of either the average or max (depending on whether you value 2nd place > 3rd place etc., or just winning vs losing) of a player's bids.

This should work assuming that a player's utility is given by:

utility = sum of unit values - prices paid + average or min of other players' prices paid (corresponding to viewpoint choice from above)

since the penalty cancels out the last term.

Edited November 25, 2016 by ruadath

[JudgeWargrave]

I think what you want might be a VCG mechanism (in particular, look at the following example). This assumes 1 unit for each bidder, though you can probably modify it and get fair results. In fact, now that I think about it, this is probably ideal, since the primary weakness of VCG is that it doesn't maximize profits for the auctioneer (sometimes they lose money!) but we don't care about that in this case.

EDIT: Yeah, so you can do this just in a pretty straightforward manner with just a simple modification to the standard bipartite maximal matching algorithm. It's polynomial time too, so no worries about tractability. Yay for operations research!

I haven't fully grasped all the details here yet, but I have a question about one thing. If I understand correctly, VCG maximizes "social welfare," but is that a meaningful goal in a zero-sum situation? Put another way, can it account for the intrinsically adversarial nature of the players?

*Seems like I got ninja'd and you're already thinking along these lines, but I'll leave this here just to show my own thoughts*

If VCG assigns the units such that each of our estimates of (my team's turncount+handicap) is minimized, that isn't actually what we want. We are willing to accept longer turncounts, so long as other turncounts are larger than ours, and therefore longer in general. Each player would rather have a high turncount, and everyone else a worse turncount, than a low turncount, and everyone else a better one. If not, the players could just collude themselves to create an optimum partition of units into teams to minimize net turncount. (Actually, that would be a very interesting (and long) project in it's own right...but not what we're working on right now. Note to self, keep it in mind.)

And so the idea of maximizing "social welfare", where each individuals welfare is "having a good team" is, at best, at right angles to our goal. Now if the "social welfare" is each player's estimate of their victory chances, or estimate of each placing weighted in some manner, that perhaps can be maximized because although the game is zero-sum, player estimate of victory does not necessarily sum to a constant (100%) since estimates can be wrong and so could be maximized. An assignment could give each of 4 players a personal estimate of 30% chance of victory, for instance. However, quantifying that from the bids seems non-trivial.

Of course it may be that I have completely failed to understand VCG in the past hour or so of trying, it seems like pretty advanced stuff to me!

On another note, I think I found a pretty short proof that the goal of under-bidding and over-bidding being dominated by true-bidding is unattainable, even if we don't balance teams at all.

If under-bidding is never better than true-bidding, that must mean the price of a unit does not depend on it's winner's bid at all. If it did, we can easily construct a situation where under-bidding reduces the price and is therefore better (unless price depended inversely on the winner's bid, but that's just nonsense). Of course, 2nd price auctioning solves that very issue in perhaps the best way possible, but it can't fix the opposite issue:

If over-bidding is never better than true-bidding, then the price of a unit does not depend on the losers' bids at all. If it did, then overbidding could increase the price an adversary pays, which would be better than true-bidding in such circumstances.

So the only way to completely rule out under- and over-bids simultaneously is to have price be totally independent of bids, which is clearly not an OK solution! Now, personally I'm OK with under- and over- bids being unviable with imperfect information, which I think is very much attainable, probably in a variety of ways, but that appealing mathematical perfection isn't.

[ruadath]

This is a fun discussion! I'm looking forward to seeing what comes out of it!

At this point though, I'm reasonably confident (although for the moment too lazy to prove) that the "correct" idea is one of the following:

1) Apply VCG mechanism, but charge an additional fee of average bid amount to each player

2) Constrain players to have a certain "pool" of values to play with; i.e. every player has 100 points to play with and must distribute across bids. Then apply VCG on that bidding set

I think your proofs don't apply to situation one because they don't account for the fact that there can be a penalty in addition the prices. Thoughts?

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The first step in determining a correct auction though is to determine each player's utility function. Let us suppose a player intrinsically values units at a value v_unit. Then given a set of units S along with prices p_unit, we have

utility(S) = sum_{unit in S} v_unit - sum_{unit in S} p_unit + {some factor that depends on the other players payments and units}

What is this factor? It depends on the player's outlook. If I take the average over all the other player's payments that seems OK, but its not clear to me that it makes sense.

What about units that other players received? That actually doesn't matter, because we can redefine our valuation of a unit to be "the value I get from having this unit and the other players not having said unit"

One major assumption with this auction that is flawed is that we are assuming unit valuations are uncorrelated when this is not true. Certain units may perform better in pairs (or groups), and this would affect make their value a function of the other units you have, but this situation is too complex to consider for now.

Edited November 25, 2016 by ruadath

[JudgeWargrave]

I think your proofs don't apply to situation one because they don't account for the fact that there can be a penalty in addition the prices. Thoughts?

Maybe you could explain the penalty a bit more? If it just adds on to the price and is some function of the bids, I don't understand how it affects the fact that both:

a winner's underbids must not benefit them, so must not lower the price (+penalty) they pay, so their bid can't affect the price

a loser's overbids must not benefit them, so must not raise the price the winner pays, so their bids can't affect the price

And then we are left with the problem of: if not the bids, what does determine price or penalty?

One major assumption with this auction that is flawed is that we are assuming unit valuations are uncorrelated when this is not true. Certain units may perform better in pairs (or groups), and this would affect make their value a function of the other units you have, but this situation is too complex to consider for now.

Yep, I had that in mind even before starting this thread. One advantage drafts have is that, assuming N players and N units with a certain characteristic (flying, warping, etc) every player can get at least one, (though not always one from all categories with the standard 12344321 style of order). Having bids on units contingent on the results of other unit assignments is more complexity than I want to lay on the players, so I set the issue aside as well.

Edited November 25, 2016 by JudgeWargrave

[ruadath]

a winner's underbids must not benefit them, so must not lower the price (+penalty) they pay, so their bid can't affect the price

VCG covers this case because the price you pay is independent of your (i.e. the winner's) bid

If over-bidding is never better than true-bidding, then the price of a unit does not depend on the losers' bids at all. If it did, then overbidding could increase the price an adversary pays, which would be better than true-bidding in such circumstances.

In my modified VCG mechanism, the price of our unit does depend on the loser's bids, but your payment is also based on your own bid values. By overbidding, even if you don't pay any extra for units individually, you incur a penalty for the size of your bid and therefore lose utility.

The penalty should be something like average of all the bids you make, or max (I'm not sure which is better yet). Actually, upon further reflection, perhaps it should just be sum of all your bids.

Edited November 25, 2016 by ruadath

[JudgeWargrave]

In my modified VCG mechanism, the price of our unit does depend on the loser's bids, but your payment is also based on your own bid values. By overbidding, even if you don't pay any extra for units individually, you incur a penalty for the size of your bid and therefore lose utility.

The penalty should be something like average of all the bids you make, or max (I'm not sure which is better yet)

OK, so the overbidding losers still hurt the winner, but their bid factors into the penalty which hurts themselves as much or more? But how can injuring oneself based on bids for units you don't even win work out? You would get hurt by your bid whether its an overbid or not, since the system doesn't actually know your true valuation, right?

Edited November 25, 2016 by JudgeWargrave

[ruadath]

But how can injuring oneself based on bids for units you don't even win work out? You would get hurt by your bid whether its an overbid or not, since the system doesn't actually know your true valuation, right?

Since everyone gets "hurt" this way, it shouldn't actually matter.

OK, so the overbidding losers still hurt the winner, but their bid factors into the penalty which hurts themselves as much or more?

Whether it's as much or more depends on what we define to be a player's utility, so I guess we should figure that out first. Do you agree with my proposed notion of utility in the earlier post?

[JudgeWargrave]

Since everyone gets "hurt" this way, it shouldn't actually matter.

But if we're just giving everyone -your total bids or -your average bid, this hurts them unequally right? For instance, Carmine would just get completely wrecked. It seems to incentivize underbids. How would the mechanism handle someone that bid 0 on everything? Would they profit by bidding more, and if so, wouldn't someone who truly valued everyone at 0 profit by overbidding?

Never mind that, I was conflating their personal view of profit with whether they would actually profit in a practical sense.

Edit: I guess I need a practical example to understand all this. So if we use the scenario I made up before: "the case of two players P₁ and P₂, and two units U₁ and U₂ . Now say P₁ values the units at (1, 2), and P₂ values them at (5, 10)"

How does the mechanism allocate things if they bid truthfully, and why can't they profit by over or under bidding their values?

Whether it's as much or more depends on what we define to be a player's utility, so I guess we should figure that out first. Do you agree with my proposed notion of utility in the earlier post?

My starting point for estimating each player's utility would be (their own team value - handicap - (another player's team value - the other's handicap)) summed over all other players. Basically, treating team value as a proxy for estimated turncount, maximize net turncount lead on each other player.

Edited November 25, 2016 by JudgeWargrave

[ruadath]

My starting point for estimating each player's utility would be (their own team value - handicap - (another player's team value - the other's handicap)) summed over all other players. Basically, treating team value as a proxy for estimated turncount, maximize net turncount lead on each other player.

OK, so assuming each player bids truthfully, their own team value is just the sum of the bids that they won. Handicaps are just fixed payments, so those are easy as well. The tricky thing is another player's team value... it's tempting just to take the sum of the winning bids for the other player, but it probably makes more sense to take the sum of your losing bids on those units; after all if someone paid a ton of money for some set of units and they see the value in it but you don't, you probably don't care.

So then taking that into account, if N is the number of players, your expression for utility from above simplifies to

(N-1)*(sum of own winning bids - handicap) - sum of losing bids + sum of other players handicaps

Let's see what we can work with from there. This utility seems good up to the fact that I'm not sure the weighting is correct. I think that the utility should be of the form

f[sum of own winning bids - handicap]-g[sum of losing bids + sum of other players handicaps]

But it's not clear to me what f and g should be.

Edit: I guess I need a practical example to understand all this. So if we use the scenario I made up before: "the case of two players P₁ and P₂, and two units U₁ and U₂ . Now say P₁ values the units at (1, 2), and P₂ values them at (5, 10)"

How does the mechanism allocate things if they bid truthfully, and why can't they profit by over or under bidding their values?

OK, so suppose they bid their true values. A maximal weight matching is P_2(U_2)+P_1(U_1)=11. So what is the price of each unit? P_1 causes no harm to P_2 by getting U_1 so he pays 0 for U_1. P_2 causes a harm of 1 to P_1 by getting U_2, so P_2 pays 1 for U_2. Then we impose the penalties to each player, which would be a total of 3 for P_1 and 15 for P_2. I guess this does seem excessively harsh on P_2... what if we changed the penalty to not account for the winning bid (since that is "locally second price" or something like that)? Then the penalty for P_1 is 2 and the penalty for P_2 is 5 which seems better... but not perfect (in particular, both P_1 and P_2 benefit from bidding less for U_1)

{thinking about under/overbidding right now}

Edited November 25, 2016 by ruadath

[ruadath]

Actually, I think the correlation of units is a bigger problem than we're considering due to negative correlations (having one warp/flyer might be extremely important, but picking up a second is not nearly as important). So I propose the following alternative mechanism, an auction draft, which seems pretty fair to me:

At each round of the auction, players make bids to see who gets to make a pick. Whoever bids the highest for that round pays their bid and gets to make a pick, and then we move on to the next round. Once a person fills out their team, they drop out of the auction (or not?).

This seems pretty simple and straightforward. What do you think?

Edited November 25, 2016 by ruadath

[JudgeWargrave]

I've been watching a few videos and I think I get VCG a bit better now. I think I was on the wrong track when including the handicap/price as part of the utility function, because the price is what they're paying to get the utility, that is, the units. But anyway, if I consider the case of the four players here (W E H and C) bidding on Vanessa (V) I think this is how it works out, assuming utility = value of units I got - (value of units I didn't get/3). For now I'll just make my bid 11 and Horace's 10.

bid| V |utility|

W 11 | | -11/3 |

E 5 | | -5/3 |

H 10 | | -10/3 |

C 22 | x | 22 |

Net utility to others: (-11-5-10)/3 = -26/3

Now if C didn't exist:

bid| V |utility|

W 11 | X | 11 |

E 5 | | -5/3 |

H 10 | | -10/3 |

Net utility to others: (33-5-10)/3 = 18/3

Social cost of C: (18 - -26)/3 = 44/3 = 14.67

So Carmine gets Vanessa and pays 14.67, is that right? So that, after considering the handicap, the utilities are ((44/3-11)/3, (44/3-5)/3, (44/3-10)/3, 22-44/3) = (1.22, 3.22, 1.55, 7.33). W E and H consider C to have gotten a bad deal in proportion to the price - their value of V, /3 since C is one of their three opponents. Then C considers himself to have a good deal in proportion to his value for V - the price.

Now for under/over bidding. C could have bid lower, but that wouldn't help C, because it wouldn't change his social cost = price. E could have bid higher, but that would not change the social cost of C because it wouldn't change the difference in net utility.

But what about 2nd place, W, bidding more? This would change the difference in net utility since W wins in one world and loses in the other. By W bidding 1 more, the social cost of C, and price on V, rises by 4/3. It seems that the fact that W is incentivized to increase V's price is still throwing a wrench in....

Bidding on the right to draft another unit, now that's interesting. The immediate problem that jumps out at me is that it would take longer, up to 4*28 PMs would be needed. Well, less than that because of the people dropping out, at most 4*25+3+2 really, but way more than 4 in any case. Including the auctioneer posting their hashed bid each round as basically equivalent to a PM if they were participating. So ultimately it would be 4 times longer than a normal draft (even longer really due to the sequences where the last and first person draft twice in one action), rather than 7 times shorter.

We could have people submit 7 bids in decreasing order, using their highest remaining to bid on each round. That gets us back to 4 PMs, though it loses the adaptability...plus people would still have to post their pick after winning, so still 27 more!

Edited November 25, 2016 by JudgeWargrave

[ruadath]

I've been watching a few videos and I think I get VCG a bit better now. I think I was on the wrong track when including the handicap/price as part of the utility function, because the price is what they're paying to get the utility, that is, the units. But anyway, if I consider the case of the four players here (W E H and C) bidding on Vanessa (V) I think this is how it works out, assuming utility = value of units I got - (value of units I didn't get/3). For now I'll just make my bid 11 and Horace's 10.

Price should definitely be part of the utility function because you're better off getting Vanessa for free than getting Vanessa for 10 turns (for example).

bid| V |utility|

W 11 | | -11/3 |

E 5 | | -5/3 |

H 10 | | -10/3 |

C 22 | x | 22 |

Net utility to others: (-11-5-10)/3 = -26/3

Now if C didn't exist:

bid| V |utility|

W 11 | X | 11 |

E 5 | | -5/3 |

H 10 | | -10/3 |

Net utility to others: (33-5-10)/3 = 18/3

Social cost of C: (18 - -26)/3 = 44/3 = 14.67

You're a little off here. The social cost is not the difference in net utility, but rather the difference in net values of items received. VCG for auction a single item (unit) just reduces to a second-price auction. So if Vanessa was the only unit being auctioned, then Carmine would win and pay 11. And yes, VCG has problems with overbidding losers in this scenario because our utility function depends on other player's winnings which is why this system needs to be modified with a penalty of some sort.

Edited November 25, 2016 by ruadath

[JudgeWargrave]

Price should definitely be part of the utility function because you're better off getting Vanessa for free than getting Vanessa for 10 turns (for example).

Right, I should have said price isn't part of the utility when calculating the social cost, as the price is the social cost.

The social cost is not the difference in net utility, but rather the difference in net values of items received.

I see. In the case where utility of the losers are not negative but 0 (as is the case when they aren't "spiteful" towards the winner) these are identical, so I didn't pick up on the difference there because none of the examples I looked at involved spiteful agents.

[JudgeWargrave]

So I still think that dominant truthful bidding in an auction with rational spite is impossible. No system of prices or penalties can avoid this. To formalize what I mean:

Consider two players in an auction on a single item. Without loss of generality, let the winning player be P_W and the losing player be P_L. Let their private values for the item be {V_W, V_L}, their sealed bids be {B_W, B_L}, B_W>= B_L, and the price of the item be F(B_W, B_L). Now we call the players "spiteful" if the final utilities are given by {V_W - F, F - V_L}. The sum of utilities is exactly V_W - V_L, which is expected: in a zero-sum game the utility should be constant.

We can include other prices and penalties, but if they are functions of the bids, they can just be absorbed by F, as it is a zero sum game. The sum of utilities must be V_W - V_L. The individual utilities must be {V_W - X, X - V_L}. So unless X depends on something other than the bids, we can continue with X = F = the price of the item.

Now consider the price F(B_W, B_L). In order for under-bidding to be dominated by truthful bidding, F cannot have positive correlation with B_W, else the winner could increase their utility by under-bidding. In order for over-bidding to be dominated by truthful bidding, F cannot have positive correlation with B_L, else the loser could increase they utility by over-bidding.

So F, price, cannot have positive correlation with either bid under the condition that truth is dominant. Such an F is useless as a mechanism for an auction.

I did think of yet another method of fair team allocation: adapting the pie rule.

1. Assign the players numbers 1 to N in arbitrary order.

2. The player with no team with the lowest number (initially 1, generally A) constructs a team of 7 from the available pool of units.

3. The player with no team with the next lowest number (initially 2, generally B) either accepts the team, or gives it to player A. If they give it to A, they perform step 2 next, otherwise A will do it again.

Repeat 2 & 3 until the last units are given to the last person. The effect of the pie rule is to incentivize the construction of average teams: if you make an above average team, you are punished by an opponent getting it. If you make a below average team, you are punished by receiving it yourself.

Pros:

Faster than a normal draft.

Players don't all need to join before the process can begin. They can join by either accepting the proposed team, or giving it to its creator and constructing the next one.

Cons:

Still slower than a sealed bid auction.

Its still possible to be harmed by placement order, even if your decisions are optimal, because there are more than two players; for instance, if you are last, you only get one choice. If the 1st person made two really good teams, taken by 2nd and 3rd, there's nothing you can do about the fact that your team will at best be 3rd best.

Doesn't advance the aim of assigning numerical values to the units.

Teams might just end up being similar to the stale draft teams.

Like bidding, fair team construction requires novel evaluation skills, so the initial runs would probably have unbalanced results just like the auction system used here.

[ruadath]

OK, I agree with your proof. Here is a different idea (a refinement of my approach #2):

Suppose that we give each player some fixed amount of turns to bid (let's call it 100 for now, we can figure that out later). Then each player makes bids on all the units that sums to 100, and then we apply VCG to allocate, and then impose the VCG prices as handicaps to each player. Would that end up working?

Coming up with an appropriate number for the pool of turns to bid would be an interesting challenge though, since it does end up having an effect on the auction...

Edited November 26, 2016 by ruadath

[JudgeWargrave]

OK, I agree with your proof. Here is a different idea (a refinement of my approach #2):

Suppose that we give each player some fixed amount of turns to bid (let's call it 100 for now, we can figure that out later). Then each player makes bids on all the units that sums to 100, and then we apply VCG to allocate, and then impose the VCG prices as handicaps to each player. Would that end up working?

Coming up with an appropriate number for the pool of turns to bid would be an interesting challenge though, since it does end up having an effect on the auction...

Very likely that would work, considering even the naive, ad hoc system I suggested with the bid caps and price = max(winner's bid, average of losers' bids) seemed to be "working" for practical purposes. Would the VCG way provide an advantage significant enough to implement it? I've already got the other way coded, but if a new way is a significant improvement then of course I want to use it.

Edited November 26, 2016 by JudgeWargrave

[ruadath]

VCG should allow you to fairly easily implement any team balancing you want (i.e. set max size of a team as X). If you don't care about that, you should probably just second-price auction each unit. I'll try and do some analysis on the situation and see what happens (if anything).

Edited November 26, 2016 by ruadath

[JudgeWargrave]

VCG should allow you to fairly easily implement any team balancing you want (i.e. set max size of a team as X). If you don't care about that, you should probably just second-price auction each unit.

Well, I don't feel I really have the mathematical grounding to "fairly easily" implement VCG on 28 items even with no team size limit in place....I suppose I would generate one assignment with all players, then generate an assignment for each player being excluding in turn to calculate social cost...how should the teams be generated with an excluded player? Everyone still gets 7 units, with 7 unassigned?

But anyway, my question isn't only ease of implementation, but benefit gained. What's the advantage of the VCG method? The property of truth-dominance didn't hold up in this problem domain. Does it have other unique properties that are maintained in this context?

[JudgeWargrave]

It's a nice feature of 2nd price is that no one pays more than their own bid. I wanted a price function f that still had this property, but depended on the winner's bid, so that incentives to under or over bid could be made to cancel out. It took a few pages of high school level math that required a sad amount of error checking, but I succeeded in proving that if the price f(x,y) = Ax + By, where x is the winner's bid, y is the next highest bid, and A+B = 1, then setting A = (1/number of players) produced exact equalization of incentives. An intuitive result, but demonstrating it was a pain.

By the way, while doing so, I found that in a single item, 2 player, 2nd price spiteful auction, if you believe the other player will bid in the interval [v-m, v+m] around your valuation v with uniform distribution, your optimal expected outcome would be bidding v+m/3. 1/2 times you have unchanged utility, 1/6 times you have utility (-m/3)/2 [value increases from 0 to m/3 over the range (v, v+1/6)], and 1/3 times you have utility +m/3, for an average increase in utility of m/12.

Anyway, in the case of this auction, if the price is 25% of the winning bid + 75% of the next, here's the results that gives, with no bid capping:

[spoiler=weighted average price]

Wargrave 7
Moulder 02.77 : 04.79
Garcia 04.78 : 06.83
Natasha 02.52 : 04.10
Joshua 02.46 : 03.85
Kyle 03.88 : 06.21
Tana 06.04 : 08.86
Dozla 01.47 : 02.56
23.93, relative hc 15.29

Egg 7
Forde 02.33 : 03.00
Marisa 00.15 : 00.30
L'Arachel 00.99 : 01.00
Ewan 00.95 : 02.00
Rennac 02.25 : 03.00
Duessel 01.33 : 02.00
Syrene 00.65 : 01.00
08.64, relative hc 00.00

Horace 7
Franz 06.28 : 10.10
Neimi 00.50 : 01.10
Colm 02.02 : 02.10
Amelia 01.02 : 01.10
Innes 01.02 : 01.10
Cormag 02.94 : 03.10
Knoll 00.03 : 00.10
13.81, relative hc 05.17

Carmine 7
Gilliam 08.47 : 14.00
Vanessa 13.83 : 22.00
Ross 06.08 : 10.00
Artur 10.32 : 17.00
Lute 07.19 : 12.00
Gerik 06.02 : 12.00
Saleh 08.61 : 17.00
60.53, relative hc 51.89

Comparing these to the 2nd system I ran (the first one after I finished my playthrough), I think it's gotten even better! Now no one is paying more than their bid, Carmine is even closer to the edge of competitive, we simplified things by ditching the bid caps, and our teams even look a bit more fun (Egg and Horace get a mounted unit early on, and I get a flyer), though that part could be a coincidence. And of course there's no rational incentive to give dishonest bids unless you have a read on the opposition, and even then the potential gain is marginal, so I think players will give their honest valuations and we can accurately quantify unit values over time.

[ruadath]

By the way, while doing so, I found that in a single item, 2 player, 2nd price spiteful auction, if you believe the other player will bid in the interval [v-m, v+m] around your valuation v with uniform distribution, your optimal expected outcome would be bidding v+m/3. 1/2 times you have unchanged utility, 1/6 times you have utility (-m/3)/2 [value increases from 0 to m/3 over the range (v, v+1/6)], and 1/3 times you have utility +m/3, for an average increase in utility of m/12.

More generally, in a n player, 2nd price spiteful auction with spite coefficient alpha (meaning that your utility = (1-alpha)*your profit-alpha*(sum of other player's profit)), where each player's valuation is drawn from a distribution F (where this is the cdf), you can prove that an optimal strategy for a player with valuation v is given by bidding E[X|X>v], with X=1-(1-F)^(1/alpha).

So it probably makes sense (in this scenario) to take F a normal distribution around your own bid, with some standard deviation that's up to the player to determine...

In the extreme case of a uniform distribution, this simplifies to (v+alpha)/(1+alpha)

Edited November 26, 2016 by ruadath