Behavioral and Quantitative GT workshop

A workshop on Behavioral and Quantitative Game Theory will be held in Newport Beach on May 14-16, 2010.  Topics and speakers are related to AGT.

Read Full Post »

Trillion $ problems

Muthu sarcastically posted:

I was thinking about research hyperboles. We have already worked on problems that impact “billions” of dollars. Next, papers will claim to solve problems that impact “trillions” of dollars (applications to US govt)?

My own reaction was: well, of course I’m working on trillion dollar problems, and so is Muthu and so are most researchers.  Almost all theoretical work in most branches of science is doing so too. If you take a fundamental problem and try to estimate its worth in dollars, any reasonable measure will give you trillions of $’s.  (One may certainly doubt that such a monetary quantification exercise is useful or tasteful, but that’s another question.)  Now of course, I’m not “solving” any trillion dollar problems, only making small steps, but if even a single paper out of the 100 that I write during my whole career makes even a 0.01% step towards the “solution”, then that will give an average value of a million dollars per paper — certainly much more than society is paying for it.

For the skeptics who worry about the numbers rather than laugh at the whole notion of quantification in $’s, let me justify the trillion dollars, at least for “algorithmic game theory” at large.  (It is probably not hard to undergo a similar exercise for many other branches and sub-branches of science , although likely but not all of them.)

World GDP is over 60 Trillion dollars per year and rising fast.  Computing the present value of all of future humanity’s GDP requires an assumption on future growth as well as a heroic choice of an an interest rate, but the answer will certainly be in the quadrillions (quadrillion = 1000 trillion).  Is it hard to imagine the Internet affecting 10% of that GDP, and algorithmic game theory deserving 1% of the credit for this future Internet?  Is it hard to imagine better theoretical understanding of economics making a 10% change in that GDP, and algorithmic game theory contributing 1% of that understanding?  I would say that each of these four numbers is actually an under-estimate.

Advertisement

Read Full Post »

Algorithmic Game Theory in 1957

Eran Shmaya posts about a beautiful demonstration from 1957 by Micahel Rabin of the twists that computation puts on  game theory.

Read Full Post »

New paper: Budget Feasible Mechanisms

A new paper Budget Feasible Mechanisms by Christos Papadimitriou and Yaron Singer was recently uploaded to the arXiv:

We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, and yet it has not been studied, to our knowledge, in the past. We focus on the case of procurement auctions in which sellers have private costs, and the auctioneer aims to maximize a utility function on subsets of items, under the constraint that the sum of the payments provided by the mechanism does not exceed a given budget. Standard mechanism design ideas such as the VCG mechanism and its variants are not applicable here. We show that, for general functions, the budget constraint can render mechanisms arbitrarily bad in terms of the utility of the buyer. However, our main result shows that for the important class of submodular functions, a bounded approximation ratio is achievable. Better approximation results are obtained for subclasses of the submodular functions. We explore the space of budget feasible mechanisms in other domains and give a characterization under more restricted conditions.

Read Full Post »

Buzzing

My gmail account got “buzzed” yesterday, and I checked it out.  (While I do work for Google part-time, I knew very little about this product previously.) My initial impression is that this is indeed the “social app” for my generation: the email generation.  I have to admit that I never caught up with the younger generation who feels at home at Facebook or Twitter (or, frankly,  even SMSing).  I know that for the young of today email is something that “your teacher uses to talk to your parents”, but, hey, I am these teacher and parents.  So while I wonder with everyone how the Google Buzz vs. Twitter/Facebook thing will go in general, Buzz seems to fit my demographic quite well.

To start with, it lives where I live — in the email.  Just this tiny fact may make a huge difference for me, since I rarely bother entering Twitter or Facebook neither to check things out, nor to write a trivial message.  Now, for example, I can follow Lance’s Twitter on Buzz.  The zero-effort of buzzing means that I can even see myself Buzzing (is this the term that’s go’na catch instead of tweeting?).  Second, as buzz was automatically populated with many of my email contacts, I almost immediately have stuff to look at.  So far certainly almost all buzz that I’ve seen is from the nerdier side of my contacts, but that can change very quickly, if I extrapolate from what I see so far.  Furthermore, as the default of the “profile” page is to show the list of those that you follow or that follow you, it’s easy to “browse the followship graph” and find even more interesting people t0 follow. (Tao is buzzing too, and once you follow him you also get the items he shares from the blogs he reads.)

A bunch of other design choices also seem appropriate for me: from the simplicity of it all, to the directed followship graph (a la twitter) which is easier to swallow for me than the undirected friendship graph of Facebook.  I haven’t tried yet the geo/mobile features (I’m still 2G), or the targeted buzzing to specific subgroups, but at least their description seems simple enough.

To conclude: so far I’m a fan, with two main worries: (1) the overload of information with its time-sink effect will certainly get worse, and (2) while I rarely felt the need to be careful about my privacy online previously, I do feel the need for care in handling my privacy with Buzz.

Read Full Post »

STOC accepted papers

The list of papers accepted to STOC 2010 is now online, with many links to online papers added here.  The following are related to AGT:

• Budget Constrained Auctions with Heterogeneous Items by Sayan Bhattacharya (Duke), Gagan Goel (Georgia Tech), Sreenivas Gollapudi (Microsoft Research) and Kamesh Munagala (Duke).
• Improved Algorithms for Computing Fisher’s Market Clearing Prices by James B. Orlin (MIT)
• On the searchability of small-world networks with arbitrary underlying structure by Pierre Fraigniaud (CNRS and Univ. Paris Diderot) and George Giakkoupis (Univ. Paris Diderot)
• Bayesian Algorithmic Mechanism Design by Jason D. Hartline (Northwestern University) and Brendan Lucier (University of Toronto)
• Multi-parameter mechanism design and sequential posted pricing by Shuchi Chawla (University of Wisconsin-Madison), Jason Hartline (Northwestern University), David Malec (University of Wisconsin-Madison) and Balasubramanian Sivan (University of Wisconsin-Madison)

Read Full Post »

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.

Read Full Post »

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.

Read Full Post »