New CS/Econ blog: Constructive Economics

Constructive Economics is a rather new blog on the border of Economics and CS written by Abe Othman.  The blog seems to also be interested in AI at large as well as real-world finance.

Read Full Post »

Paper Recommendation Experiment

There are two main reasons why researchers publish papers in conferences and journals.  A “real” reason and a “strategic” reason.  The strategic reason is an artifact of the current academic situation where researchers are judged according to their publication list, when considered for positions, promotions, grants, etc.  Given this state of affairs, we have a strong personal incentive to “publish” whether or not our research is worthwhile and whether or not anyone will ever read it.   The “real” reason for publication is dissemination: let other researchers learn about our work, so they can use it, continue it, be influenced by it, etc.  This is what  the whole “scientific/academic establishment” should aim to promote.  Inherent here is the competition for the attention of other researchers who have to decide to spend time and effort reading your paper rather than the countless others vying for their attention.

In my view the main real service that journals and conferences provide in this day and age is exactly the arbitration of this competition for attention: the editors and reviewers of journals and the program committee of conferences  look at lots of papers and suggest a few of them for me to look at.  When chosen right, this is indispensable: there is no way that I could spot by myself  the new important paper of a young graduate student among the hundreds of non-important ones out there.  The main reason why I prefer conferences to journals in CS is that the former seem to be doing a much better job (although still far from perfect) of this identification of new important stuff.

The Internet has revolutionized the mechanics of dissemination of scientific work.   I can still remember when scientific dissemination worked by putting reprints of our papers in envelopes and sending them in (real) mail.  This was replaced by photocopying from conference proceedings, then by sending email attachments, and today we just “put it on the web”.  The standard that seems to be emerging now is to put it on the arXiv.  In comparison, the “social-scientific” structure surrounding “publication” has hardly changed at all, and putting your paper on the arXiv is not “counted as a publication” , provides no signal of your paper’s quality or correctness, and usually does not suffice for getting much attention for your work.    I think that the main ingredient missing from having “putting your paper on the web” be the main form of publication is a surrounding mechanism that can provide a signal of quality and that will help readers focus their attention on the more important work.  How exactly this can work still remains to be seen, but I would like to run an experiment in this direction on this blog.

Experiment: Recommend interesting AGT/E papers on the Web

I am asking readers of this blog to put forward — as a comment to this blog post — recommendations for interesting papers in the field of Algorithmic Game Theory/Economics.  Here are the rules of this experiment:

• Eligible recommenders: Anyone from the “AGT/E research community”.  I will take this in a wide sense: anyone who has published a paper related to AGT in a recognized scientific forum (conference or journal in CS, AI, GT, economics, …)

• Eligible papers: Papers must be (1) Available openly on the web. (2) Not already have been published in a journal or conference with proceedings.  It is OK if they were submitted to or accepted  by a conference or journal as long as they have not yet appeared yet.  (3) Related to Algorithmic Game Theory/Economics, taken in a wide sense.

• What to include: (1) Name of the recommender and a link to their academic home-page — no anonymous recommendations (2) A link to the paper (3) A short explanation of what the paper is about and why you think it is interesting.   There is no implicit assumption of having refereed the paper in any sense.

• Conflicts: The recommender should follow the usual rules of avoiding conflict of interest followed in program committees: do not recommend (1) your own papers, (2) papers of someone in own department, (3) papers of a frequent collaborator (4) papers of a family member/lover, etc.

[Update: following a suggestion, to start things off, I entered my own recommendation in the format that I was thinking of — as a comment.]

Advertisement

Read Full Post »

Facebook PhD Fellowships Announced

Facebook announced five Inaugural Facebook Fellows who receive “paid tuition and fees, a $30,000 stipend, conference travel and other benefits”. Among them is Algorithmic Game Theorist Yaron Singer.  Congratulations.

Read Full Post »

New paper on “Multi-Unit Auctions: Beyond Roberts”

My paper with Shahar Dobzinski titled Multi-Unit Auctions: Beyond Roberts, was just uploaded to the arXiv.

Abstract

We exhibit incentive compatible multi-unit auctions that are not affine maximizers (i.e. are not of the VCG family) and yet approximate the social welfare to within a factor of . For the case of two-item two-bidder auctions we show that this family of auctions, termed Triage mechanisms, are the only scalable ones that give an approximation factor better than 2. “Scalable” means that the allocation does not depend on the units in which the valuations are measured. We deduce from this that any scalable computationally-efficient incentive-compatible auction for items and bidders cannot approximate the social welfare to within a factor better than 2. This is in contrast to arbitrarily good approximations that can be reached under computational constraints alone, and in contrast the optimal social welfare that can be obtained under incentive constraints alone.

Read Full Post »

ICALP 2010 Accepted Papers

The ICALP 2010 accepted papers have been posted.  AGT/E related ones:

• MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Nicole Immorlica and Hamid Mahini. The cooperative game theory foundations of network bargaining games
• Danny Segev and Iftah Gamzu. A Sublogarithmic Approximation for Highway and Tollbooth Pricing
• Tobias Harks and Max Klimm. On the Existence of Pure Nash Equilibria in Weighted Congestion Games
• Allan Borodin and Brendan Lucier. On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions
• Albert Atserias and Elitza Maneva. Mean-payoff games and propositional proofs
• Giorgos Christodoulou, Katrina Ligett and Evangelia Pyrga. Contention Resolution under Selfishness
• Ning Chen and Xiaotie Deng. Envy-Free Pricing in Multi-Item Markets
• Krishnendu Chatterjee and Laurent Doyen. Energy Parity Games

Read Full Post »

Google research awards

Google awards research grants, including in “economics and market algorithms”, with the next deadline coming soon on April 15th.

Proposals are very short, and there are no strings attached, but it is rather competitive and you do need a Google contact.

Read Full Post »

In Quest of Truth and Justice

Guest post by Ariel Procaccia

Three of the papers uploaded to the archives on March 30 have a common theme: they deal with truth and justice (a.k.a. fairness). In the scientific jargon “paper after paper” means “two papers” and “a series of papers” means “three papers”; since there is also a bonus fourth paper, I can therefore declare a new “trend”.

Two of the arXiv papers are by Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, and Svetlana Olonetsky. Both papers study mechanisms with payments for the allocation of goods. The first paper asks (and answers) the following question: for which allocation rules are there payments such that the resulting mechanism is, at the same time, truthful and envy free? The latter property means that each player weakly prefers his own outcome (bundle+payments) to the outcome of any other player. Interestingly, the fact that an allocation has payments leading to truthfulness, and different payments leading to envy freeness, does not imply that there is a single payment scheme that leads to both. The second paper focuses on a setting where players have a limit on the number of goods they may receive; the main result is that (under additive valuations) the VCG Mechanism with Clark Pivot payments, which is of course truthful, also has the property that a higher capacity agent never envies a lower capacity agent. This implies envy freeness in the natural special case where all agents have the same capacity.

The third paper is by Elchanan Mossel and Omer Tamuz. The first part of the paper deals with cake cutting, informally known as “allocation of divisible goods”. Curiously, most of the literature on cake cutting is concerned with fairness, while truthfulness has so far been largely overlooked. Mossel and Tamuz are interested in mechanisms (without payments this time) that are, again, truthful and fair, but this time the notion of fairness is proportionality: each of the n players is allocated a piece of cake worth at least 1/n according to his valuation. They present a simple randomized mechanism that is truthful (in expectation) and proportional. To be precise, they show that there exists such a mechanism, since the construction relies on a well known nonconstructive existence result. The mechanism is then extended to yield (the existence of) a randomized mechanism that is truthful and guarantees each player a piece worth more than 1/n of the entire cake in expectation (assuming some of the players have different valuation functions). The second part of the papers applies these insights to the allocation of indivisible goods.

Incidentally, I recently wrote a paper with Yiling Chen, John Lai, and David Parkes where we independently asked questions that are very similar to the ones raised by Mossel and Tamuz, but our answers are very different (modulo a small overlap). In our paper we want it all: truthfulness, envy freeness, and proportionality (which in our setting is not implied by envy freeness). Envy free cake cutting is notoriously difficult, and in fact there is no known protocol that achieves an envy-free division with a bounded number of steps. In order to get constructive results we therefore focus on restricted valuation functions where achieving fairness is trivial and the richness of the problem comes from the additional truthfulness requirement. Our main result is a deterministic mechanism that is truthful, envy free, proportional, and polynomial-time, assuming the valuations are what we call piecewise constant. The paper will appear in AAAI’10; in observance of the time honored AAAI tradition the current version is super dense and most proofs are omitted. This is another similarity to the Mossel-Tamuz paper: they have proofs of existence and we have nonexistent proofs! (In fact the proofs do exist, and the full version is coming soon.)

I’ll finish with a word of caution from my AI conscience. The problems that we study in AGT are often justified by assuming that our players are computational agents (e.g., in the scheduling domain). It is clear why lack of truthfulness may lead to socially undesirable outcomes in a multiagent system. In contrast, envy freeness seems to be desirable for philosophical or psychological reasons; it is a priori unclear why we would look for envy freeness in a multiagent system. A nice challenge is to come up with a model that relates envy freeness to the stability of the system, for example in terms of the robustness to random failures.

Read Full Post »

Lecturships in Liverpool

The university of Liverpool is offering two lecturship positions in Economics and Computation.   Deadline for applications: April 30, 2010.

Read Full Post »

Postdoc positions at Jerusalem

Sergiou Hart has postdoc positions for research in game dynamics at the Rationality Center of the Hebrew University in Jerusalem.  Excellent “AGT-types” are also encouraged to apply.  Let me add my recommendation: the rationality center at the Hebrew University is a great place for AGT/E.  The official deadline is over now, but excellent candidates can still apply.

Read Full Post »

Advanced Max Planck Course on AGT

The 11th Max Planck Institute’s Advanced Course on Foundations of CS will be held on August 2–6 in Saarbrücken, Germany, and will be devoted to Approximation Algorithms and Algorithmic Game Theory.  The speakers are Christos Papadimitriou, Vijay Vazirani, and  Guido Schäfer.  Student Grants are available.

h/t Haris Haziz

Read Full Post »