This issue contains revised and expanded, journal versions of selected papers that were presented at the 4th Symposium on Algorithmic Game Theory that took place in Amalfi, Italy, October 17–19, 2011.

The papers cover current topics in the field of Algorithmic Game Theory: mechanisms, games related to routing, auctions, and the study of the equilibria of general games.

Two of the papers of the special issue study mechanisms. The paper Scheduling without payments considers the classical problem of designing mechanisms for scheduling jobs on unrelated machines but in a setting where payments are not allowed. Quite surprisingly, the paper shows that it is possible to obtain a non-trivial approximation. The paper A Truthful Mechanism for Value-Based Scheduling in Cloud Computing considers the scheduling of batch jobs on a cloud. Here, the owners of the jobs can specify their willingness to pay as a function of job due dates.

Two papers study the structure of equilibria of games that model scenarii in communication networks. The paper Strategic Pricing in Next-hop Routing with Elastic Demands considers next-hop routing by self-interested agents. This model differs from the models in which the source of traffic determines the entire route from source to destination, as agents can only decide about the next hop destination. The paper Weakly-Acyclic (Internet) Routing Games shows that a class of routing games modeling important aspects of Internet routing are weakly-acyclic and thus they admit a pure Nash equilibria that can be found efficiently.

The paper Repeated Budgeted Second Price Ad Auction abstracts existing mechanisms for repeated auctions of ads in sponsored search for agents with a fixed budget and studies their equilibria and dynamics. The main result is a proof of existence of equilibrium for agents that do not overbid.

Two papers deal directly with the notion of a Nash equilibrium for general games: one paper has a positive result and the other gives negative results. The paper Random Bimatrix Games are Asymptotically Easy to Solve (A Simple Proof) gives a simple proof of the fact that for random bimatrix games the uniform distribution is an approximate equilibrium with high probability. It is well known that 3-player games can have irrational equilibria. The paper Complexity of Ration and Irrational Nash Equilibria shows that is hard to decide whether a game has a rational equilibrium.

I would like to thank the authors that contributed to this issue. I also owe my gratitude to all the reviewers, who carefully worked on the papers and often provided insightful comments and remarks.