NBER Market Design conference

Via Al Roth’s blog, I hear of an email circulated bySusan Athey and Parag Pathak:

The National Bureau of Economic Research workshop on Market Design is a forum to discuss new academic research related to the design of market institutions, broadly defined. The next meeting will be held in Cambridge, Massachusetts, on Friday and Saturday, October 8-9, 2010.

We welcome new and interesting research, and are happy to see papers from a variety of fields. Participants in the past meeting covered a range of topics and methodological approaches. Last year’s program can be viewed at:  http://www.nber.org/~confer/2009/MDs09/program.html

The conference does not publish proceedings or issue NBER working papers – most of the presented papers are presumed to be published later in journals.

There is no requirement to be an NBER-affiliated researcher to participate. Younger researchers are especially encouraged to submit papers. If you are interested in presenting a paper this year, please upload a PDF or Word version by September 1, 2010 to this link http://www.nber.org/confsubmit/backend/cfp?id=MDf10

Preference will be given to papers for which at least a preliminary draft is ready by the time of submission. Only authors of accepted papers will be contacted.

For presenters and discussants in North America, the NBER will cover the travel and hotel costs. For speakers from outside North America, while the NBER will not be able to cover the airfare, it can provide support for hotel accommodation.

Please forward this announcement to any potentially interested scholars. We look forward to hearing from you.

Apparently, the only “call for papers” is the link for uploading your submission (deadline:September 1st, 2010), and I’m not really sure how wide the intended scope is, beyond extrapolating from last year’s program and the identity of the organizers.  In fact, I’m even not sure if participation as a listener is open to all.   In any case, this sounds quite different from CS conferences, and you may read the reflections of David Pencok from last year’s conference.

Wikipedia course assignments

I have been teaching the course Topics on the  border of CS and economics with Michal Feldman in the fall semester.   One of the course assignments was to write a Wikipedia entry on a topic of the students’ choice that is related to the course.  This was the first time that any of us tried this, so we left this assignment pretty open and only made sure that the class’s choice was injective and more or less in range.  We were not aware at the time that there are suggested ways on how to organize such a thing, e.g. this entry in English or this one in Hebrew (we allowed both English and Hebrew entries, and most students chose the latter.)

We saw various reasons why this assignment is a good idea: First, we figured that having the “world” reading your work is an added incentive to write well. (This is especially so given the fact that, due to the terrible budget cuts in Israeli universities in the last few years, we had no TA.) Second, we wanted to ensure that the effort that students put into their assignment is not wasted but rather put to a good use.  Third, there was the idea of doing a public service.  Fourth, there was a somewhat vague notion of immersion in the main motivator of the course: what goes on the Internet.

As the course has ended, we compiled a list of the entries written for the course.  I would say that the experiment has ended with mixed results: the quality of entries varies.  Some of them are really good, others are OK — a reasonable start and hopefully will be improved, but some are quite badly written (in various senses: format, writing style, and even technical content.) It seems that adding incentives for what is usually done by volunteering (i.e. giving course credit for writing an entry that is usually done voluntarily) introduces problems.  While normally Wikipedia writers only do so when they want to and are able to do a god job, here we incentivized people to do so even if they could not do a good job or did not want to put enough effort into doing so.  (This is somewhat similar to the observation that paying for blood donation reduces the willingness to do so.)  I can’t really tell if the students that did a really bad job are incapable of doing significantly better or just didn’t put enough effort into it.

Michal and me now feel somewhat responsible for doing some harm to the (mostly Hebrew language) Wikipedia.  We are not really able to go over all the entries ourselves and “fix” them (again, no TA, and many dozens of entries.) We are making small changes here and there as well as adding a few comments in discussion pages, but this is small in magnitude, and doesn’t help much for the worst entries, so we have decided to hire a TA/RA for a while to “clean after this course”.

One of the interesting new entries was the Algorithmic Game Theory entry in the English Wikipedia.  It turns out that there was no such entry previously, despite a call to write one by the “committee to improve Wikipedia’s arguably-somewhat-sketchy coverage of theoretical computer science” over a year ago, which mentioned AGT together with a list of other desired entries, many of which still remain unwritten.   (Looking at the history page of AGT, it seems that an entry for AGT was previously written, but the entry was not appropriate and focused on Algorithmic Mechanism Design and so was “moved” there about two years ago.)

My (preliminary) conclusion: I would do it again, but next time, only with a smaller class size and with a devoted TA.

Workshop in New-Zealand, 18-19/2/2010

A workshop on Algorithmic Aspects of Game Theory and Social Choice will take place at the University of Auckland in New-Zealand on 18-19 February 2010.  Interested speakers are asked to send an abstract by February 1st.

Report from SODA

I’m attending this year’s SODA conference, in Austin.  It has been blogged about widely (here, here, here, and here), as well as continuously tweeted. The buzz here is good: it’s a very large conference for TCS (over 300 attendees), and with three parallel sessions, there is almost always something interesting to listen too.  I met many old friends as well as got to meet many of the up and coming younger generation which I haven’t met before.

There have many many talks related to algorithmic game theory this SODA.   Session “5A” was more or less devoted to algorithmic mechanism design.  The first talk was a merger of three separate papers that all basically proved that “VCG-based” combinatorial auctions cannot approximate welfare well even on very restricted valuations for which algorithmically approximation is easy.  The techniques are combinatorial focusing on the VC-dimension and extensions for it.  While this is bad news especial since “VCG-based” mechanisms are still the only known generic ones having incentive compatibility, these results can not rule out other types of incentive compatible mechanisms.  The talk was split between representitives of two of the merged papers, Dave Buchfuhrer and Shaddin Dughmi, who emphasized different variants of the lower bound: Dave talked about the very simple valuations (additive-with-budget-limit) for which the lower bound holds, while Shaddin talked about more general classes (like sub-modular) for which a generic reduction is given and emphasized that the lower bound applies also to some family of randomized mechanisms.  I’ve previously shortly posted about three of the other talks in this session: “price of anarchy for greedy auctions“, “incentive compatible budget elicitation in multi-unit auctions”, and “pricing randomized allocations” (with the talk explaining and motivating the model details that I didn’t fully get from skimming the first version of the paper).  The talk on “utilitarian mechanism design for multi-objective optimization” considered a mechanism design setting in a graph where there are two different “weights” on each edge (“cost” and “length”) and the goal is to minimize the sum of the costs, under a constraint that upper bounds the sum of the lengths.

All the talks in this session were very good, I thought. The usual question of what can a speaker do in his allotted 20 minutes seems to be a bit more difficult in algorithmic game theory due to the double background needed.   It seems that the choice of most of the speakers was the “explain and advertise your result”, rather than “discuss the basic ingredients of your technique” which was taken by the talk on multi-objective optimization.  An approach that was not taken by anyone is “motivate and discuss your model” which is the natural one in economic theory.  Such discussion of the model was called for in many of the papers since there are delicate modeling issues involved in them, but it is probably difficult-to-impossible to take this approach in a 20 minute talk while leaving time for the required background as well as even the statement of the results.

Of the other talks I’ve heard, I was especially intrigued by the talk “On the possibility of faster SAT algorithms” by Mihai Patrascu and Ryan Williams which under very strict assumptions about the running time needed to solve SAT on CNFs (regrading the constant in time) get exact lower bounds for several other problems via pretty simple reduction.  E.g. under an appropriate (extreme but plausible) assumption. a near-tight lower bound is obtained for the following problem: given a list of numbers, find of them that sum  to .  Even more intriguing, lower bounds on multi-party communication complexity are obtained under similar assumptions about SAT.  The speaker, Ryan, was very careful to point out that due to the extreme assumptions, the meaning of these results is not clear.

SODA 2011 is in SF.  After a prolonged voting process in the business meeting, it was decided that the SODA 2012 will be in Kyoto rather than in Rome, Barcelona, Prague, or NYC.  If only every conference had such an array of alternatives.

AGT summer school in Shanghai

A summer school on Algorithmic Game Theory will take place on July 4–15, 2010 at Fudan University in Shanghai.  Co-located with Expo 2010 with its expected 70M visitors.

The Valiant brothers report from ICS

Gregory and Paul report from the ICS conference in this guest post:

The inaugural Innovations in Computer Science conference was held in Beijing last week, and if the amazingly high spirits of the participants are anything to go by, the conference was a success.  Our hosts at Tsinghua University’s Institute for Theoretical Computer Science (ITCS) stepped in to an unusual degree to ensure that, despite Beijing’s worst snowstorm in 50 years, we were warm, happy, and on schedule.

One of the talks we enjoyed the most was the paper of Barasz and Vempala, “A New Approach to Strongly Polynomial Linear Programming”, presented on short notice by Avrim Blum. (Avrim has now earned the top spot on our list of substitute presenters.)  The paper introduces a class of algorithms that combines the best aspects of the simplex method and interior point methods in the hopes of lighting the way to a strongly polynomial algorithm for linear programming.  Simplex algorithms, since they are inherently combinatorial in nature, have the unique advantage of having a running time independent of the bit-complexity of their inputs, but analyses of this running time soon get lost in the maze described by the surface of high-dimensional polytopes.  Interior point methods, on the other hand, bypass the intricacies of the surface by taking a “short cut” through the center of the polytope.  What this paper describes is essentially a variant of the simplex method whose vertex-to-vertex transition rule allows for such “short cuts”.   Their main technical results–that the proposed algorithms run efficiently on a class of instances containing all known hard instances for simplex methods–provide ample motivation for follow-up work.   This paper seems to epitomize the objectives of the conference: without the onus of intricate technicalities, it puts forward a new idea that could open up a promising new direction of research.

Perhaps stemming from the idealistic call for papers, and the fact that this was the first meeting of a forward-looking conference, there was a feeling of optimistic camaraderie in the air which could be said to culminate in the final discussion session. The discussion covered reflections on the ICS papers, some plugs for undernourished research areas (most notably Vijay Vazarani’s call to arms to tackle the problems of convex programming with the tools of combinatorial optimization), and a section chaired by next year’s ICS chair, Bernard Chazelle, on what one audience member dubbed “innovations in conference organization”.

The first and last papers of the conference were highlighted by Shafi Goldwasser as providing much-needed input from the theory community to the growing reality of multi-core computing.  The last paper, by Avinatan Hassidim “Cache Replacement Policies for Multicore Processors” generalized the standard caching analyses to the now very pertinent case where multiple cores have access to a single shared cache, and showed that for standard caching algorithms to be efficient, the cache size would need to be prohibitively large.  This has the counterintuitive implication that making caches private would actually help performance.  The opening paper of the conference, by Applebaum, Ishai, and Kushilevitz, “Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?” while not mentioning multicore computation at all, has clear implications for it: cellular automata are in some sense a caricature of the multicore world, where functions requiring only local inputs can be computed in a single step, but communication is slow and tricky.  In this model, they demonstrate encryption, pseudorandom generators, and commitment schemes (under a standard coding theory assumption) that all take just a single step of the cellular automaton, while showing the corresponding impossibility of decryption or signature schemes.

The conference concluded with a lively discussion of suggestions for next year’s ICS.  A popular suggestion was that the format of the sessions should have more variety to explicitly welcome innovation in a wide variety of forms: from traditional papers with theorems and proofs, to surveys/tutorials of promising new directions or techniques (perhaps chosen from a set of submissions), to a formal (refereed) ongoing projects session which may include summaries of false starts, attempts, or background material as an introduction to a problem or set of problems.  (Someone noted that typical open problem sessions are often filled with people’s throw-away problems: a mix of the impossible and the not-worth-my-time; injecting some formality and prestige might change this.)  And, of course, as innovation does not happen in lock-step, a bit more unstructured time for chatting might help.

Along the lines of encouraging more responses to the papers presented, the committee mentioned they had initially planned to have a very brief (five minute?) panel discussion after each session, where volunteers or committee members who, having previously read each of the papers just presented, would provide some contrasting perspective.  This is perhaps motivated by the fact that no amount of perfectly honed rhetoric from an author can match the impact of an “I liked *this* about it” from an impartial third party.

One final point that was touched on was that an increasing fraction of conferences are being videotaped, but these videos never seem to appear online in an accessible way that aims to recreate the experience of going to a talk — perhaps all it would take is something as simple as a webpage with video on one side of the page, and navigable powerpoint slides on the other side of the page.

We look forward to seeing some of these proposals–both mathematical and logistic–carried out in next year’s ICS.   It is certainly a conference to keep an eye on.



Vazirani: Seeking Combinatorial Algorithms for Convex Programs

Vijay Vazirani has spent a considerable amount of time in the last few years on developing combinatorial algorithms for problems (mostly involving market equilibria) that can be solved by general convex programming.  In this guest post Vijay talks about the motivation for this:

Since convex programs can be solved efficiently using “continuous” methods, such as ellipsoid or interior point methods, why bother designing extremely ellaborate and difficult combinatorial algorithms for them? Let me propose the following thought experiment (it is not a difficult one!) to bring home the point. Think of a world in which these continuous methods were developed in the 1920’s and ever since, problems such as network flow and matching, which can be cast as linear programs, were routinely solved using such methods. Then in 1956, Ford and Fulkerson propose their beautiful combinatorial algorithm for max-flow and it is immediately trashed, since it is “needlessly complicated and difficult”. Edmonds’ matching algorithm, which is proposed in 1965, meets a similar fate. As a consequence, in this world, combinatorial optimization is a stillborn field. How much of a tragedy would that be? After all, matchings and max-flows could still be computed efficiently …

Observe that the continuous methods solve the instance at hand, without giving any insight into the entire problem from which the instance arose. In fact, such methods do not even need to be told the problem from which the instance arose — all that is needed is the specific linear or convex program for the given instance. So, in this world, theoreticians (if they can be called that) would not have the deep insights we have into the structure of numerous fundamental combinatorial problems. And you can gauge what kind of a “theory” of algorithms this world would have!

I believe that if our research community does not pursue the design of combinatorial algorithms for convex programs, our world would also lose out on a beautiful, deep theory. My lone work on this topic, some joint with my students, is too insignificant an effort in comparison with the ideas, structures and methods that still need to be unearthed. My inability to convince people so far, on what had seemed to me an obvious direction worth pursuing, is the reason for this post.

The convex programs I have studied over the last 8 years arose in AGT, in the context of market equilibria and Nash bargaining games. The theory so far has started forming around a remarkable convex program given by Eisenberg and Gale in 1959. In order to solve these nonlinear programs combinatorially, the classical primal-dual algorithm design paradigm had to be extended from its previous setting of LP-duality theory to the more general setting of convex programs and KKT conditions. The algorithms are non-trivial and require substantial structural insights. In turn, these structural insights provide a starting point for tackling more general problems. To get an idea of how rich the theory is already, consider the following episode. A few months ago, Gagan Goel and I started designing a combinatorial algorithm for a certain Nash bargaining game under peicewise-linear, concave utility functions; the linear case had already been solved. Out of the structural insights gained, we managed to define a new, natural market that models perfect price discrimination and in which buyers have peicewise-linear, concave utility functions (the usual Fisher and Arrow-Debreu markets were recently shown to be PPAD-complete under these utility functions). The equilibrium of our market is captured by a generalization of the Eisenberg-Gale program and is polynomial time computable — even combinatorially. In addition, the convex program yields very simple proofs of both welfare theorems for this market!

It is important to point out immediately that my work is limited to a very thin sliver of convex programs — depite their nonlinearity, these programs admit rational solutions. How about attacking more general classes of convex programs combinatorially, perhaps via approximation algorithms, since they won’t admit rational solutions? Considering how extensive the theory is already, I believe it cannot exist in islolation and is indicative of the tip of an iceberg. We need a lot more smart people to ponder on these issues to find the rest of the iceberg!

Facebook Graduate Student Fellowship

Facebook has announced a pretty nice graduate student fellowship program.  The first three reserach areas they mention are:

• Internet Economics: auction theory and algorithmic game theory relevant to online advertising auctions.
• Cloud Computing: storage, databases, and optimization for computing in a massively distributed environment.
• Social Computing: models, algorithms and systems around social networks, social media, social search and collaborative environments.

(Hat tip to TechCrunch.)

Google has its own graduate Fellowship program (Nicolas Lambert got the 2009 Fellowship in “Market Algorithms”.)

My $1/day Adwords Account

Google gives its employees $1/day of free adwords advertising.  Beyond an employee perk, this gives Google’s employees the experience of being an Internet advertiser, i.e. experiencing the point of view of Google’s paying customers.  I have been using my $1/day account to advertise the divorce-consulting business of my sister in law (In Hebrew) and did indeed find this experience to be quite illuminating.

The first thing I learned is that the ad auction itself is just a small part of the whole thing.  Choosing the right text for the ads (all ten words of it), choosing the right keywords to target, etc, is much more prominent than setting the right bids.  ”Tiny” issues come up everywhere, e.g. when I needed to choose keywords to target, it turns out that there are four ways to write divorce in Hebrew: גירושים, גירושין, גרושין, גרושים.  I’m not really sure whether these are all “kosher” spellings, but they are all searched for an do need to be taken into account.  Even more, the whole advertising campaign is peripheral, in principle, to the business itself, and frankly the auction logic is not the first concern of the advertiser.  This is obvious, of course, but is easy to forget for one whose work focuses on the auction logic.

Now for the auction itself: all together I spent several hours setting up the campaign, making up the ads, choosing keywords, looking at reports, and trying a bit of optimization.  The adwords user interface was very easy and convenient to start with, but it didn’t take long until I was attempting things that confused me (e.g. splitting my single campaign into two different ones), at which point I gave up, and stayed with what I achieved, which is quite fine actually.  I was especially impressed with Google’s automatic suggestions of keywords which were cleverer than what I came up with (I know that not really, just some learning algorithm, but they were eerily good.)

I was surprised and disappointed (as an advertiser, but frankly delighted as a Google employee) by the pretty high prices on the keywords that I targeted: my average cost per click is 88 cents, and this is for pretty low slots, on the average.  (Divorce is expensive, it seems, also on the Internet.)  This means that my $1 per day suffices for a single click per day, and no more.  I do get this single click almost every day, but have so far been unable to ever get two clicks in one day: neither optimizing by hand, nor letting Google’s automatic bidder do it.  I was professionally insulted by not being able to beat the automatic bidder, but have still not given up on getting an average of more than one click per day for my $1.  My click through rate is pretty high (compared to my expectations):  0.79%, so I usually get about 150 impressions every day of which one is clicked and results in a visit to the website.  Now these visitors are probably really good leads: not only have they searched for relevant keywords, but they also clicked on a pretty specific ad.  I suppose that if even 1% of them become clients (this is not so little: we are not talking about buying a sweatshirt; this is about handling divorce), then the advertising would be considered quite  profitable even had my sister in law paid for it.  Unfortunately, it is quite hard to gauge whether this is the case: getting and keeping the required statistics is easier to imagine theoretically than to do when you have to handle a small business.  In other words, I haven’t a clue what my valuation of a click is.   (The lack of knowledge of one own’s valuation has been discussed in AGT, but frankly I have not seen really convincing treatment of this issue.)

The set of reports about the performance of the campaign that adwords makes available  is quite impressive, and they are really nicely and simply done, but somehow I still don’t really know how how to optimize my campaign as to get the most and the best customers to the site.  I’m sure that more time on my part, as well as a more data-centric handling of my sister-in-law’s business would improve things, but the difficulty of getting and handling the right data is another lesson that I got from this exercise (again, I knew this theoretically, but now I feel it too).

AGT decade in review

The end of the decade is always a good opportunity to look back on every aspect of our lives, and this blog gives me a forum to do so for the field of algorithmic game theory.

At the beginning of the decade there were scattered attempts to model and study issues related to the Internet using a combination of computer science with game theory or economic theory.   By the end of a decade a full blown academic discipline has emerged with its own language (game-theory + information economics + algorithms + complexity), it’s own conferences (EC, SAGT, WINE — but no journals), graduate courses, a steady stream of  PhD’s (some who have won awards for their dissertation), and in general a pretty lively community.  I would say that this field has been quite warmly accepted by the theoretical CS community, by the AI community, and by the Game-Theory community, but has not yet won the hearts or minds of many economists, and is just now starting to be embraced by the Networking community.      Despite the rather common language used in this border between economics, game-theory, and computation, there are still pretty well distinguished sub-communities according to the “land of origin”: theoretical CS, AI, or Networking (with a much smaller number of new immigrants from the lands of economics or game theory.)

It is quite clear that this research community is currently mostly of a CSey “piranha culture” where packs of researchers quickly devour a problem, each of them taking a small bite that is immediately sent to a conference.  Given the initial availability of low hanging fruit in this uncharted territory this culture seems to have served the field well, despite its many shortcomings.  At this point AGT seems to have become rather faddish (in the appropriate communities, that is), which calls for increased diligence in evaluating new research.

So what did we have in AGT this decade?

Much work during this decade has gone into determining the computational complexity of various types of equilibria in games and in markets.    The class PPAD has been pointed as the complexity of many of these problems, and in particular of the problem of finding a Nash equilibrium.  This last result by Daskalakis, Goldberg, and Papadimitriou and Chen and Deng gets the “AGT result of the decade” award.  While there are still open problems regarding the complexity of equilibria, especially in markets, it seems to me that — in the limited sense of pinpointing the right complexity class — most of the picture is understood at this point, with the most significant remaining open problem being the computation of approximate Nash equilibria.

Starting with Koutsoupias–Papadimitriou, much attention has gone into the analysis of the costs that the game-theoretic point of view levies on computational problems.  The catchy name  “Price of Anarchy”, together with the convincing results of Roughgarden and Tardos who analyzed these costs in models of network congestion, have been extremely influential on the field.  This last paper gets the award for “most influential AGT paper of the decade”.  In the early part of the decade using the terms “price of X” for many X’s was de rigueur in certain circles, but by the end of the decade the naming template has become passe, while the type of analysis itself — sans the catchy name — became standard.

Auctions of various forms were a central object of study during this decade.  In the first half of the decade much attention has gone into the combinatorial auction formalism which became the paradigmatic problem in Algorithmic Mechanism Design.  It is probably fair to summarize that most  computational issues have been resolved, while most strategic questions have remained open. The failure to understand the extent of the clash between the strategic and computational considerations applies to the rest of Algorithmic Mechanism Design as well  despite much work and some mild progress (e.g. in single parameter domains, maximum-in-range mechanisms, and randomized mechanisms).  The basic question of “how well can computationally-efficient incentive compatible combinatorial auctions or incentive compatible scheduling mechanisms perform” remains as open as in the beginning of the decade, and gets my (biased) “AGT open problem of the decade” award.

The second half of the decade saw much of the focus shift to “ad auctions” of various kinds,  an application that obviously wins the “killer AGT application of the decade” award (rather than the spectrum auctions which seemed the candidate in the beginning of the decade).  While the driver of ad auction research is certainly the internet advertising multi-billion dollar industry that has hired droves of AGT researchers, much of this work seems to focus on issues that are of basic theoretical interest in settings of repeated auctions, often departing from the basic models of dominant-strategy worst-case analysis, vying for more delicate models that capture the desired issues better (and in so also influencing the rest of algorithmic mechanism design.)

The field of AGT is obviously much influenced by developments in its parental fields of computer science, economics, and game-theory, as well as in its basic domain of application, the Internet.  Trends which are significant include the continuing march of the Internet to become a platform for everything (from social networks, to cloud computing) and the growing roles of information economics as well as experimental economics within the fields of economics and game theory.

The rest of the world has also changed, and despite many tragedies, conflicts, set-backs, and especially dangers, the main story of the decade is a triumph: the amazing rise of Asia that has led to the fastest increase in human welfare in history, and may give some hope to a Billion people that still remain poor.

On this happy note let me wish a happy new year — and decade — to my readers.