Feeds:
Posts
Comments

Archive for February, 2010

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.

Read Full Post »

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

Read Full Post »

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 »

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 »

Older Posts »