Touch the Truck

There was a British game show in the early 2000s called “Touch the Truck,” where, according to the rules, the truck would go to whomever could keep his hands on it the longest. Similar games have been featured in a number of other shows, including Survivor, where the last person to keep his hand on the totem would win immunity and That 70’s Show, in the following episode (start at 3:37 — you don’t need to watch the whole episode, unless you want to):

The three games that I’ve just mentioned differ in a couple of ways. In the British show, the contestants are able to take breaks, and are disqualified if they fall asleep, so it is primarily a contest of sleep-deprivation. In Survivor and That 70’s Show, bathroom breaks are not allowed, so the contest is much shorter and contestants might gain an advantage by wearing (ew) diapers or catheters. Obviously, pulling a stunt like that incurs costs — does the contestant really want to wear a diaper?

We can also think of Touch the Truck as a war of attrition or all-pay auction — any amount of time that the contestants spend holding their hands to the truck is a sunk cost. They’re not getting that time back. In most all-pay auctions or wars of attrition, the outcome can someone be that the players bid more than the object is worth — suppose you auction off a $20 bill, and everyone pays their bid regardless of whether they win. Then, you can imagine a scenario in which someone has bid up to $20, and another player who already has $18 in the game might bid $21 so as to only lose $1 rather than $18. If he wins by bidding more than the value of the object, we call it a Pyrrhic victory.

However, there is a slight (and largely inconsequential) difference between Touch the Truck and most wars of attrition or all-pay auctions. In all-pay auctions, players can bid as high as they like, whereas in Touch the Truck, the human body can endure only so much. The world record for staying awake is something like 11 days, and in most of the latter 8 days or so the person is basically not really functioning. (The longest I’ve ever continuously stayed up is probably around 50 hours, and by then I pretty much can’t do anything.) The truck, however, we can say is worth at least $15,000 — a conservative estimate. So, even if someone were able to stay up for 11 days, and took another 4 days off to recuperate, he has still earned $15K in 15 days [1]. Not too shabby. And, since none of the contestants can actually stay up long enough for the time lost to be equal to $15K, there will always be additional rent that each contestant can earn (the winner will never have a Pyrrhic victory).

So what’s the equilibrium outcome? Well, the winner’s outcome is similar to the winner’s outcome in second-price auctions or English auctions. Since the contestants have differentiated levels of ability to stay awake, if you’re not the person who can stay awake the longest, then you might as well lose immediately. If you are the contestant who can endure sleep-deprivation the longest, then you should stay up as long (or \epsilon longer) than the second most fortitudinous contestant. You should choose to do it even if no one else is choosing to enter the contest, because if there’s a chance you’ll quit sooner than that, then someone else might be able to win and might want to enter the contest.

Of course, in this example, there is perfect information — everyone knows everyone else’s level of fortitude, etc. The entertainment value comes from everyone’s thinking that they might actually be able to endure longer than anyone else, and of course, this comes at the expense of the contestants. Everyone would be better off if he could reliably and accurately communicate how long he could stay touching the truck, but most efforts at communicating this information are cheap talk (like Daniel does in the show.)

[1] Generally we would have to account for different people’s different valuations of the truck, but, since this is a game show and the organization running the game wants to pick the most enthusiastic bunch of people it can find, we will safely assume that every contestant values the truck at market price.

Advertisements

How to win big in eBay auctions, Part II: Winning stuff for free

So I promised I’d show how there’s a perfect Bayesian equilibrium in the eBay setup where all people pay only the price at which the bidding started, \pi_0. How’s that, you say? Won’t people want to bid up the price, if they’re willing to pay more?

The key to this equilibrium is, obviously, to remove the incentive to bid any higher. Since, in eBay, the highest bid up to any given point is not observed, we can describe perfect Bayesian equilibria based on beliefs for those situations if they were to come up. Thus, if any bidder bids something other than \pi_0 at any time except for the last moment, the other bidders can plausibly believe that this bidder has bid something ridiculously high, and so will respond by bidding up the price of the item, knowing that they have nothing to lose by doing so. This way, they can punish any bidder who deviates by bidding higher than \pi_0, so no one will do so.

For this equilibrium to work, we must also consider the timing and tie-breakers. eBay has structured its auction mechanism so that, once there is at least one bid on an item, all bids must be greater than the current price. This means that at most one person can bid \pi_0; the rest, if they will bid, must bid more. We can resolve this issue by stipulating that all bidders try to bid \pi_0 at some time \tau, and one of these, chosen randomly, does so successfully. Meanwhile, anyone who bids at some other time (rather than the last minute) is believed to have again bid something ridiculously high, and punished in the same way as the one who bids something different from \pi_0. Again, this will ensure that everyone bids only at \tau, except for maybe at the last moment when no one has time to respond to their bid.

We have to (finally) deal with what happens at the last moment. Suppose bidder i is the lucky guy who successfully submitted his bid earlier at time \tau. At the last moment, to discourage others from trying to outbid him, now he is the one who bids ridiculously high. Knowing that they cannot win the item, no one else tries to submit a bid at the last moment.

One can formally check that this is indeed a perfect Bayesian equilibrium. Though this is unlikely to ever happen in reality, this shows the lack of uniqueness of symmetric equilibria (in the sense that all people’s strategies are ex ante the same) in eBay’s setup, and that we can get a pretty sweet outcome given the right beliefs. Pretty cool, huh?


How to win big in eBay auctions: Part I

OK, I lied a little bit: I can’t guarantee that you will win lots of really awesome things for dirt cheap. But I did stay at a Holiday Inn Express last night. What I can provide, though, is a perfect Bayesian equilibrium strategy that will mean you are bidding optimally (assuming others are also bidding in a similarly defined manner). Basically, I wrote my senior thesis at Princeton on eBay, so I know how it works pretty well.

I’m not going to go through the exact details of how eBay works, since I assume if you care, you already know more or less about that (you can look here for more information). I’ll also omit most of the gory details of how exactly to rigorously demonstrate that these strategies mathematically form an equilibrium, since I assume most readers will care mostly about the practical implications. I hope to upload a link to my thesis, so if you want, you can take a look at that yourselves.

At first glance, eBay seems to work exactly like a sealed-bid second-price auction. Indeed, eBay itself suggests that one should always bid exactly how much one values the item up for sale. But there are two potential issues. First, there are likely to be multiple items of the same type. For example, suppose I collect stamps: there are likely to be multiple copies of the same stamp (unless it is extremely rare). Thus, I might want to avoid bidding on an earlier auction of a stamp, if I could get the same one a little later for a better price (we’ll assume no discounting, since it doesn’t much change the reasoning). Second, eBay complicates the general second-price auction setup by showing the price history; that way, it might be possible to infer how badly others want, say, the stamp, and use that information to one’s advantage.[1]

Fortunately, in the single-item case, the reasoning for second-price auctions works for eBay auctions as well: one should always bid exactly the value of the stamp (though it’s no longer a dominant strategy). There is also a well-established result for multiple items, first shown by Robert Weber, which is that if there are N items, and M bidders (where M>N, and each person wants exactly one item), then we can rank the bidders’ valuations from high to low as (V_{1},V_{2},...V_{M}); it is then a subgame-perfect equilibrium for a person with valuation V to bid
b_{l}(V)=E[V_{N+1} |V_{l+1}=V] (a)
in the lth round of bidding; that is, one bids what one expects the (N+1)^{th} highest valuation to be, if one were to have the (l+1)^{th} highest valuation. For period N, this works out to bidding one’s valuation, so it fits nicely with the single-item case.

Can we generalize this to the eBay model? Fortunately, as I showed in my thesis, we can: all it takes is to construct a set of beliefs where the bidders will ignore the previous bids of others, and bid as they would in the sealed-bid case. The best way to break down the cases is to those of two items, and those of three or more.

In the former, given that, in the second period, everyone is just going to bid as in the single-item case anyway, they will bid as in the sealed-bid, two item case no matter what at the last moment. We just need to make sure that no one will screw things up by bidding earlier. We can ensure that this happens by, say, constructing an equilibrium in which bidders believe that only people who value the stamp very highly would bid earlier than the last moment; so, if someone else has bid earlier, the rest of the bidders would assume they had lost anyway. Since one can’t see the top bid (only the current stamp price, based on the second-highest bid up to then), this belief is plausible. And if they’ve lost, they might as well just bid what they would otherwise, as given by equation (a), since bids are costless. This solves the two-item case.

In the three-plus item case, we have to be a little more careful, since if everyone just blindly bid as in equation (a), you might learn other’s valuations in earlier rounds, realize that you weren’t going to win at all if you continued bidding as in (a), and outbid others who valued the stamp more highly to “steal” the stamp. To get around this, one could construct an equilibrium where the bids are staggered – those who want the stamp more bid earlier. Since equation (a) is monotonic in V, this means that no more than two bids can occur in any given period; those who are supposed to bid earlier cannot, since the item price is already greater than what they are willing to bid (eBay requires that all bids must be greater than the current item price, since otherwise they are not relevant for determining the price of the given item, given the mechanism eBay uses). By assuming some plausible beliefs so that bidders would ignore anyone who deviated from this strategy profile, we can ensure that all bidders will adhere to the strategy profile – they’ll have no incentive to deviate.

Do people actually bid like I described in the multiple-item cases? Obviously not – most people don’t even bid their valuations, let alone think things through as much as here. Nor does it seem that people time their bids as in the equilibria described here. Yet the basic idea, that if one can ignore the bids of other people in determining how much they want the item, and only focus on bidding up to the value suggested in equation [1], that continues to make sense. After all, really, does anyone actually try to memorize how much someone was willing to bid last time a stamp came up for auction? Come on. Since no one tracks bids like this, it’s safe to bid as described here in general.

Note that, unlike the sealed-bid case, the equilibrium described here is not the unique symmetric one. In fact, there is an equilibrium in which all items are sold for the start price, if sold at all. But we’ll get to that in part II.

[1]Indeed, this issue causes there to not be any pure-strategy, increasing bidding function for multiple-item auctions with bid revelations. See Cai, Wurman and Chao (2007).


Bidding up blood

Mexican drug cartels, which control the tremendously lucrative flow of drugs into the US, have over the past several years begun to kill civilians with impunity. Bodies are displayed in public, severed limbs have been tossed onto dance floors, and the total body count continues to rise.

Until recently, civilians and children were off limits in the cartels’ informal codes of honor. The willingness to kill civilians was a signal of ruthlessness, to inform citizens and each other who is winning the war[1].

As of 2010, the Mexican drug cartels have formed two tenuous alliances against each other, one composed of the Juárez Cartel, Tijuana Cartel, Los Zetas Cartel and the Beltrán-Leyva Cartel, and the other, the Gulf Cartel, Sinaloa Cartel and La Familia Cartel [2].

To see how the two alliances might be bidding up the violence, we can first model the civilian killings as an all-pay auction. After all, the cartel incurs some cost for each civilian it kills regardless of whether it wins, and the alliance that has the most kills at the end of each period becomes the more feared of the two among civilians.

In the classic War of Attrition game, the only Nash equilibrium outcomes are that one player bids 0 and the other bids V, the value of the territory under dispute for the period. This implies that we should see in any given time period a large number of killings by one alliance and none by the other, and perhaps the territory would switch hands from period to period (as is one solution for repeated Battle of the Sexes). The expected utility for each alliance should be 0. Alternatively, each cartel has a probability distribution over [0,N] for when it will stop killing civilians. If this is a good model, then the increase in killings might be explained by the decrease in cost of killing civilians (law enforcement is getting less effective).

In the war of attrition game, once both players have made a positive bid, any victory will be a Pyrrhic victory — the expected payoff will be negative. Consider the classic example of the all-pay auction for a $20 bill — if one player bids $20 and the other, $0, they both get a payoff of 0. If one bids $20 and the other, $2, then the player who bids $2 will be forfeiting $2 anyway and might as well bid $22 and win the money. But, now the first player is out $20 — he would lose less if he could get by with winning with a bid less than $40. At some point one player should just take the hit and exit with a negative payoff.

So, the body count continues being bid up as long as both alliances continue to kill civilians on every turn — and this is in fact the case. One explanation might be that the killings are not simply a signal to the civilian population, but also a signal to the other alliance.

We can consider a three-period game:

  1. Each alliance finds out whether it is strong or weak
  2. Given the first, each sends a signal (kill many or kill few)
  3. Each decides whether to attack the other, or to defend. Nonaggression only occurs when both defend.

Each alliance must assert that it is “Strong” type rather than “Weak” type in order to maintain a foothold on the piece of territory. If a strong alliance believes the other alliance is weak on a period, it should attack and take over, since the weaker alliance cannot afford to retaliate.

Alliance j is strong
Attack Defend
Attack -2,V -2,V
Defend -2,V 0,0
Fig. 1: If Alliance i is weak, j is strong
Alliance j is weak
Attack Defend
Attack -1,-1 -1,-1
Defend -1,-1 0,0
Fig. 2: If both are weak
Attack Defend
Attack -2,-2 -2,-2
Defend -2,-2 0,0
Fig. 3: If both are strong

We see that if you are weak, your subgame perfect equilibrium strategy in the last stage is to defend regardless of your opponent’s strength. What signal should you send? Since killing might be costly for a weak alliance, a strong alliance will never send a signal that it is weak (killing few people). Therefore, if the opponent receives the signal that few civilians were killed, he knows that this is a credible signal of weakness.

A weak alliance might signal from the set {many kills, few kills}. Since the players are in identical situations at t=0, their probability p that each will be strong or weak, the probability q that they will give a false signal if weak, and the additional cost c to a weak player giving a high kill signal will be the same. Expected payoff for the weak alliance if it sees a high kill signal is

(q)[mi(strong|many)U(strong, many, defend)+mi(weak|many)U(weak, many, defend)-c]+(1-q)(-2)

= (q)mi(strong|many)[mj(strong|many)(0)+mj(weak|many)(-2)-c]+mi(weak|many)(0)+(1-q)(-2)

= (q)mi(strong|many)[mj(weak|many)(-2)-c]+(1-q)(-2)

It turns out that if sending a false signal is costless, then q is maximized at 1 and we have a pooling equilibrium. If it is costly enough, then there is a separating equilibrium (weak alliance sends low signal, strong sends high signal). What it means for our cartels is that as long as there is a pooling equilibrium, both sides will definitely enter a war of attrition and bid up the body count even beyond their valuations for the territory. It is when the cost of killing just one civilian becomes high enough that it creates a separating equilibrium that the weak alliance doesn’t kill anyone, and the strong alliance kills one[3]. Needless to say, without an honor code to raise this cost, and given the state of Mexican law enforcement, this is quite unlikely.

Thanks to Jeffrey Kang for bouncing ideas around with me.
————————-
[1] http://www.washingtonpost.com/world/mexican-drug-cartels-targeting-and-killing-children/2011/04/07/AFwkFb9C_story.html
[2]”Violence the result of fractured arrangement between Zetas and Gulf Cartel, authorities say”. The Brownsville Herald. March 9, 2010. Retrieved 2010-03-12.
[3] Why one? Because people are discrete. If the separating equilibrium were at 2 kills, then 1 kill might be a possible low signal, in which case the players may enter a war of attrition anyway.


How to win big at Chinese Auctions

(Disclaimer: I wrote my Senior Thesis at Princeton about eBay’s auction mechanism, so I’m kinda obsessed with auctions)

So, there are lots of different types of auctions out there, and lots of different auction houses. There’s Christie’s, a major art auctioneer; eBay, the #1 online auction site; English auctions, Dutch auctions – the list goes on and on. As one would then expect, the academic literature on auctions is huge. To attempt to summarize it here would be impossible. For the barest of an overview, check out Wikipedia’s page. I guess I can provide a couple of brief sentences: in the first-price auction (where you pay what you bid if you win), the Nash equilibrium symmetric strategy is to bid what you expect the guy with the next-highest bid values the object. In the second-price auction (where you pay what the next highest bid), you should always bid how you value the object, no matter what anybody else does.

Surprisingly, there is virtually no literature on “Chinese auctions,” which is very surprising since this type of mechanism is not at all uncommon. The Wikipedia page says that Chinese auctions are “typically featured at charity, church festival and numerous other events.” I know that every year the local Mikvah (Jewish ritual bathhouse) holds a Chinese auction to raise money (my family has actually done quite well with winning stuff, so I don’t know how they would make money if not that the items for auction are donated, but that’s another story). Yet when doing a Google Scholar search, only one relevant article (which you can’t even access, and has only been cited twice) is listed. Compare that to, say, second-price auctions, which generates hundreds, if not thousands, of relevant hits. Not 100% sure why that is.

Anyway, I guess I should describe just how a Chinese auction works. Basically, an item/good is up for sale (say, two tickets to that thing you love), which different people can value differently. I suppose we can make things simple here by having each person value the object independently (not depending on how others do), with a uniform distribution over [0,M]. Each person (i) of the total of N people buys a certain number of tickets (), and a ticket is chosen at random from those bought, selecting the winner. Thus the probability that person i wins the item is , i.e. the number of tickets they bought out of the total number of tickets sold. Again for simplicity, we assume that , and the cost is $1/ticket.

Let’s assume for now that if you like the item, you’re going to buy more tickets. Makes sense – you’re willing to invest more to ensure that you win. Let’s just check to see that we can find a Nash equilibrium with people following a strategy like this one.

At equilibrium, no person wants to buy any more or any less tickets – they are best off by buying exactly based on how much they like the good (). So, they cannot improve their expected payoffs by buying a different number of tickets. That is, for all i,

This is way too complicated to try to analyze directly. So let’s make things simpler. Say there are K other tickets in the pot. Then one will want to buy tickets so that

Thus, when the number of other tickets in the pot is known to be K, it is best to put in exactly tickets. Of course, this value could be negative – in which case, it would be best to buy no tickets at all! This is because the cost of any ticket is greater than the return one can expect from getting it, and one might as well sit out the auction. Notice that this gives us the characteristic we wanted – people who want the good more will buy more tickets.

Now, let’s try the case where each person knows exactly how much everyone else likes the good. If there are T total tickets, where , then we can rewrite the optimal number of tickets that person i purchases as

Thus we immediately see that only those people who value the object more than the total value of tickets in the pot will actually submit any tickets at all. We’ll assume that’s the case for simplicity’s sake; otherwise, we can just ignore those people who don’t want to get anything.

Summing the i equations of the above form, we get

From there, it is easy to plug in to the equations for to solve for .

Example: Suppose there are two people going for an iPad (I’m still a PC person, but whatever). The first values it at $1000, while the second at $500. By the arguments above, we plug in , , and , and get

One more note: when everyone’s valuations are known, it is still a dominant strategy to submit your valuation as your bid in the second-price auction. This yields a revenue (on average) of , where is the highest appraisal of the item. Yet here, the ticket sales are (at most) just (N-1)/N times the harmonic mean of how much everyone values the item. Indeed, when we take a second look at how many tickets each person is willing to buy, we see that the total number of tickets must be less than how much at least two people value the item, which is less than the amount paid by the winner in the second price auction. Thus it appears that Chinese auctions yield lower revenues to the auctioneer than second-price auctions. Perhaps this is not the best way to run a charity auction. Something to keep in mind; maybe I’ll look more into it at a later point.

Marli will write another post later this week.

(Final disclaimer: the arguments in this post constitute a sketch of an argument, not a rigorous proof. As such, the results here should be considered tentative, and this post should not be construed to be the final word on the subject.)