I spent most of last week in the Bertinoro workshop on Frontiers in Mechanism Design organized by Jason Hartline and Tim Roughgarden. Such a small focused event is really a winning format (when done right — of course): almost every talk was very close to my interests and was really good (since the speakers presented their preferred recent work which usually was also accepted to some other top conference).
One of my take-homes from this event was the strengthening of the realization that computer scientists are doing more and more Bayesian analysis in Algorithmic Mechanism Design, in this respect getting closer to the economists’ way of thinking. It is not that computer scientists have lost their basic dislike of “average case analysis”, distributional priors, or especially, common priors, it is just that we have started reaching in more and more places the limits of “worst case” analysis. It seems that computer scientists are being very careful with “how much” they rely on Bayesian analysis, obtaining various “hybrid” results that are more robust, in various senses, than straight Bayesian ones.
An extreme good example is the classic result of economists Jeremy Bulow and Paul Klemperer who show that revenue of the straight 2nd price auction (for a single item) with 
A weaker type of result, but still better than full-blown Bayesian, is the 2nd price version of Myerson’s auction. In this version, the auctioneer must “know” the underlying distribution in order to set the optimal reserve price, but once that is done, the bidders see a “worst-case” situation in front of them(2nd price with reserve) and should bid truthfully in the dominant strategy sense without needing to know or agree about the underlying prior distribution. (This is opposed to the revenue-equivalent-in-principle 1st price version in which bidders must know and agree on a common prior for them to have any chance of reaching he desired equilibrium.) A recent paper Multi-parameter mechanism design and sequential posted pricing by Chawla, Hartline, Malec, and Sivan (to appear in STOC 2010) gets similar types of results in a unit-demand heterogeneous auction setting where the auctioneer needs to know the distribution in order to set prices (in this case, posted prices) but the resulting mechanism is very simple and truthful in the dominant-strategy sense (again the approximation guarantee is in an approximation sense).
A yet weaker version of a similar type of result appears in the paper Bayesian Algorithmic Mechanism Design by Jason D. Hartline and Brendan Lucier (to appear in STOC 2010). In this paper again the auctioneer does need to know the underlying distribution, and then he creates a mechanism that is incentive compatible, but here only in the Bayesian sense. I.e. the the bidders need not know the underlying distribution (as they should just act truthfully) but they should still agree that the auctioneer knows the prior distribution. This type of result is more fragile than the previously mentioned ones since the truthfulness of the auction depends on the auctioneer correctly knowing the underlying distribution, rather than just the optimality of it. On the plus side, the paper shows that the auctioneer’s derivation of the auction can be done effectively just by using a “black box” for sampling the underlying distribution (as is the case for he derivation of Myerson’s optimal reserve price).
A someone dual situation is presented in the paper Price of Anarchy for Greedy Auctions by Brendan Lucier and Allan Borodin (SODA 2010). In that paper, auctions are presented in which the auctioneer need not know the underlying auction and acts in “detail-free” way, i.e. the auction is independent of the underlying distribution. However, the approximate-optimality holds when the bidders are in a Bayesian equilibrium, i.e the bidders must know and agree on a common prior for the analysis to hold.
The last example of “somewhat-Bayesian” results that comes to mind has nothing to do with incentives but is just algorithmic. The paper The Adwords Problem: Online Keyword Matching with Budgeted Bidders under Random Permutations by Nikhil Devanur and Thomas Hayes (in EC 2009) considers an online model of repeated auctions, where no distributional assumptions are made on the bidder values that are assumed to be “worst case”, but a distributional assumption is made on the order or arrival which is assumed to be uniform. This allows them to get arbitrarily good approximations, circumventing the known lower bounds for the completely worst case.
While economists too have looked at weakening of the fully Bayesian assumptions, as computer scientists are doing now, I see a difference in the two approaches. Harsanyi‘s influence on economic thinking seems to be so great that the Bayesian point of view seems to be taken as the correct model by economists, and even its criticisms (cf. the Wilson critique) and results that weaken the assumptions are simply taken as “2nd order” improvements. Computer Scientists, on the other hand, seem to have their basic intellectual foundation in a non-Bayesian setting, and as they move toward Bayesian models they do not seem to have a single model in mind but are rather quite happy to explore the “Pareto frontier ” between the strength of the model and the strength of the results obtained.
Finally, as a side note, let me observe that while the gap between computer scientists and economists is narrowing on the Bayesian question, the other great gap — the issue of approximation — seems to be as great as ever. E.g., all the results by computer scientists mentioned in this posts only provide approximate results, while all those by economists provide exact ones.
. We interpret 
. A matching is a subset of 
such that no bidder and no good appear more than once in it.
is the usual maximum matching problem.
and 
.
, where 
is the number of goods.
.
.
then
into Q.
.
.
for all j.
-happy if one of the following is true:
and for all goods j’ we have that 
.
.
. The main point is that this iteration cannot hurt the invariant for any other i’: any increase in 
.
, and as all weights are integers, this implies that our matching does in fact have maximum weight.
and 
, which takes care also of case 2 in the definition of happy) Summing up over all i we get 
. Now notice that since both the algorithm and M’ give matchings, each j appears at most once on the left hand side and at most once on the right hand side. More over if some j does not appear on the left hand side then it was never picked by the algorithm and thus 
. Thus when we subtract 
from both sides of the inequality, the LHS becomes the LHS of the inequality in the lemma and the RHS becomes at most the RHS of the inequality in the lemma. QED.
. It follows that the total number of iterations of the main loop is at most 
where n is the total number of vertices (goods+bidders). Each loop can be trivially implemented in O(n) time, giving total running time of 
, which for the unweighted case, C=1, matches the running time of the basic alternating paths algorithm on dense graphs.
edges (where an edge is a non-zero 
priority queue operations, where 
times, and since 
we get a total of O(Cmn) priority queue operations. Using a heap to implement the priority queue takes 
per operation. However, for our usage, an implementation using an array of linked lists gives O(1) amortized time per operation: entry t of the array contains all j such that 
, updating the value of j requires moving it down one place in the array, and finding the maximum 
gives a linear time 1.01-approximation for the maximum matching.
gives a matching that misses at most 
edges, that can then be added using 
.
Turing's Invisible Hand 