We consider a resource allocation game in polyhedral environments.

Polyhedral environments model a wide range of problems, including bandwidth sharing, some models of Adwords auctions and general resource allocation. We extend the fair sharing mechanism for such resource allocation games. We show that our mechanism simultaneously creates approximately efficient allocations and approximately maximizes revenue.

We also develop a new approach for analyzing games of these types. At the core of this approach is the relation between the condition for Nash equilibriums of the game and the dual of a certain linear program.

Joint work with Eva Tardos.