Last weekend I attended a conference in Budapest where I saw a nice trick in an unexpected place. (A longer report about the whole trip will appear on the CS Theory Blog.) Wikipedia calls it de Moivre’s martingale and the reason that I liked it is that it somehow gives me some intuition, that I formerly lacked, about virtual valuations in Myerson’s seminal result about obtaining profit-maximizing auctions from welfare-maximizing auctions.
To give some background to de Moivre’s martingale, consider the following problem: take a fair random walk in which you walk left or right by 1 unit in each step with probability 1/2; calculate the expected squared distance from the origin after n steps. One method is to explicitly calculate the value using some binomial coefficients, and do painful simplications, giving the answer n. But there is a simpler method to get this simple answer: notice that, conditioned on your position p(t) at time t, the expected increase in square distance at time t+1 is
So unconditioning and using linearity of expectation, we get
de Moivre’s martingale
Suppose you are participating in a biased random walk where on each step you move left with probability L≠1/2 and right with probability R=1-L. You can think of this as gambling. Say you start at position x, representing that you have $x. Now let’s play until either you run out of money (hit position 0) or you break the bank (hit position y>x). What is the probability of each of these two cases (win/lose), as a function of L, x, y?
Again, a direct calculation seems possible but is nasty. But instead, we can define a virtual position. We will define a function f : N→R and when the real position at time t is p(t), the virtual position at time t is f(p(t)). In fact, we will define the virtual positions so that the martingale formula holds:
This would mean that f(p(t)) is a martingale in t, that is to say, its expected value is the same in each time step. If we can accomplish this, then by comparing the final virtual position to the initial one, we deduce a formula for what we want (end is the stopping time, a random variable):
If you think about the martingale formula for a few minutes, you find that f satisfies a second-order linear recurrence relation, . Standard methods give all the solutions of this recurrence, almost any will do, but the simplest is to take Then the probability of winning is
What Myerson accomplished is to show basically that the celebrated “VCG mechanism” for combinatorial auctions, which is truthful and maximizes social welfare, can be converted into a truthful mechanism to maximize the auctioneer’s income, under mild technical assumptions, in the model that bidder’s distributions on valuations are known in advance. Myerson’s method is to replace each valuation with a “virtual valuation” that looks mysterious at first, but is similar to the above example, in the sense that you define the function based on the properties that you want it to have. My lecture notes from last term explain this in a more precise way. I am glad now to have this valuable intuition!
Filed under: b.k.a.t., computer science, game theory, probability | Leave a Comment