The following sections of this web page provide general introductions to research areas, each followed by a very brief overview of a paper I have written that is relevant to that research area (listed at the bottom of this web page).
A game is a situation in which a number of people each have a choice to make. The outcome of all these decisions may be more or less valuable to each individual, depending on who did what. Notice that the best thing for one person to do, may depend on what others decide. A simple example is the (two-person) game of rock-paper-scissors, in which the value of "rock" is good provided that the other person chooses "scissors", but poor if he chooses "paper", and so on.
A Nash equilibrium is a state of affairs where every person has - tentatively - made their choice, and furthermore would be happy to stick with that decision even if they know everyone else's decisions.
At the moment, it seems like rock-paper-scissors has no Nash equilibrium -- if each player knows what the other one plans to choose, then at least one of them will want to change his mind. But now, suppose that we allow more flexibility about what is meant by a "choice" or "decision". Suppose that we let either player choose a "mixture" of the original set of allowed decisions. You can think of this as being a decision to choose one of the three possibilities at random, or alternatively as being allowed to choose, for example, one-thind of a rock, one-third of a sheet of paper and one-third of a pair of scissors. If you're allowed fractions, the value of the outcome can be calculated in a natural way as a weighted average of the possible outcomes that are specified by the non-fractional choices.
John F. Nash proved in 1951, that provided these mixtures of decisions are allowed, then any game has a Nash equilibrium (which is of course why we now call it a Nash equilibrium). In the case of rock-paper-scissors, there is just one Nash equilibrium, which has both players doing the above trick of assigning one-third to each of the options.
My contribution: Every game has a mixed Nash equilibrium, but how do you actually find one for a particular game? The main paper that I have co-authored on this topic, shows that for some rather "fiendish" games, it may be surprisingly hard to find one (even though Nash's result assures us that it must be there).
Suppose you want to sell an object by auction. (Let's say it's something you have no use for, like an air ticket to a destination you don't want to visit.) There is a poor but reliable man who can offer $100, and a rich, unreliable man who is known to be able to offer about $200. You model the latter's unknown best price as coming from a normal distribution with a mean of 200 and a standard deviation of 20 (this means that $200 is your best guess at the price he's good for, but you could easily be off by about $20).
You want to maximize your expected revenue, and most of the time, of course, the rich man should be good for a much higher price than the poor man's. But, if you sell using a standard "English auction", the rich man buys for just over $100. Can you do any better?
Clearly you can. If you offer the item for sale at $150 (fixed price), then about 99% of the time the rich man will buy it for $150 and the other 1% of the time it will go unsold. Furthermore, if the rich man trusts you to stick to that rule, he will not mind revealing what he would really be prepared to pay (his purchase alone merely tells you whether that amount is more than $150). Better still, you could tell him: "First, tell me your true valuation, if it's above $150, I will sell you the item for $150. If it's lower, I will sell it to the poor man for $100". If the rich man trusts you to stick to this, he might as well tell you truthfully his valuation. Then you apply the rule.
One issue that has gone unresolved in the above discussion is the choice of that figure of $150, which is probably too low. We would like a general rule to find the optimal threshold, which should for example be higher if the poor man is less poor (if we can get $140 from him, we don't mind so much about losing the sale to the rich man).
In 1981 a paper by Myerson gave a general rule that applies to any finite number of bidders who might be involved, any of whom may have "random" valuations. There are two general principles to be applied:
The general idea is to take each bid and compute an associated "virtual bid". The winner is the bidder with the highest virtual bid. The higher your bid is to begin with, the higher would be the associated virtual bid. But the amount you pay (if you win) is the bid whose virtual bid would match the second-best virtual bid that was obtained from all participants. These features ensure the two truthfulness properties identified above.
So, how does the auctioneer calculate these virtual bids? Each virtual bid depends only on the true bid, and the probability distribution from whence it came (which is a nice thing). I'll omit the details, but the general idea is to impose a penalty so that the average virtual bid is zero. Essentially, you tend to favour people who exceed expectations.
My contribution so far is a recent paper on combinatorial auctions (where there are particular sets of objects, rather than individual objects, that a buyer is after). We consider the issue of to what extent one can limit the overpayment that sometimes arises.
Suppose we are interested in two types of animal, A and B, and any individual is equally likely to be type A as to be type B. Assume we can measure their height and weight, and we would like to guess an animal's type, based on these measurements. Diagram 1 shows one kind of scatter of observations that could potentially occur, in a situation where for each type, the two measurements are highly correlated, but there is not much overlap between the two classes. A green spot is a type A individual and a red spot is a type B individual. Diagram 2 shows a plausible-looking pair of underlying distributions (the ellipses show the regions where we expect most of the measurements to occur), with their averages indicated by crosses.
Now, consider an animal situated at the point indicated by the blue cross. Clearly, it is more likely to be type B (the red distribution). If we are told that this is an individual's height and weight, and we want to predict its type, we would guess type B. But suppose we were only given one or other of the two measurements. Notice that each of its two measurements is above average for either type A or type B. Since type A's average is larger for both measurements, we would predict it as being type A.
Either measurement on its own would, for an individual located at the blue cross, make us more likely to guess its type incorrectly. Conclude that a little knowledge can be a dangerous thing.
My contribution: In a 2001 paper, I consider the problem of finding the most likely dividing line between two types, if we are given as data, observations of individual measurements of random individuals (which as we saw above, may be misleading). But suppose each observation is labelled correctly with its type. I show that the amount of data you need for this purpose, depends heavily on the nature of the distribution of random individuals.
C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. Procs. of the 38th Symp. on Theory of Computing (STOC) (2006) 71-78.
E. Elkind, L.A. Goldberg and P.W. Goldberg. Frugality Ratios And Improved Truthful Mechanisms for Vertex Cover available on arXiv.
P.W. Goldberg. Learning Fixed-dimension Linear Thresholds from Fragmented Data. Information and Computation 171, 98-122 (2001)
An "English auction" is the most common type of auction that most people are familiar with. There is one seller and multiple buyers, and the seller accepts a sequence of bids in which each bid is slightly higher than the previous one. Notice that