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.
Archive for February, 2010
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.
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.
- 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)
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.