Amir Ronen

TCS Journal 2011 Journal Article

Local and global price of anarchy of graphical games

• Oren Ben-Zwi
• Amir Ronen

This paper initiates a study of connections between local and global properties of graphical games. Specifically, we introduce a concept of local price of anarchy that quantifies how well subsets of agents respond to their environments. We then show several methods of bounding the global price of anarchy of a game in terms of the local price of anarchy. All our bounds are essentially tight.

AIJ Journal 2008 Journal Article

Fault tolerant mechanism design

• Ryan Porter
• Amir Ronen
• Yoav Shoham
• Moshe Tennenholtz

We introduce the notion of fault tolerant mechanism design, which extends the standard game theoretic framework of mechanism design to allow for uncertainty about execution. Specifically, we define the problem of task allocation in which the private information of the agents is not only their costs of attempting the tasks but also their probabilities of failure. For several different instances of this setting we present both, positive results in the form of mechanisms that are incentive compatible, individually rational, and efficient, and negative results in the form of impossibility theorems.

UAI Conference 2002 Conference Paper

Mechanism Design with Execution Uncertainty

• Ryan Porter
• Amir Ronen
• Yoav Shoham
• Moshe Tennenholtz

We introduce the notion of fault tolerant mechanism design, which extends the standard game theoretic framework of mechanism design to allow for uncertainty about execution. Specifically, we define the problem of task allocation in which the private information of the agents is not only their costs to attempt the tasks, but also their probabilities of failure. For several different instances of this setting we present technical results, including positive ones in the form of mechanisms that are incentive compatible, individually rational and efficient, and negative ones in the form of impossibility theorems.

FOCS Conference 2002 Conference Paper

On the Hardness of Optimal Auctions

• Amir Ronen
• Amin Saberi

We study a fundamental problem in microeconomics called optimal auction design: a seller wishes to sell an item to a group of self-interested agents. Each agent i has a privately known valuation v/sub i/ for the object. Given a distribution on these valuations, the goal is to construct an optimal auction, i. e. a truth revealing protocol that maximizes the seller's expected revenue. We study this problem from a computational perspective and show several lower bounds. In particular we prove that no deterministic polynomial time ascending auction can achieve an approximation ratio better than 3/4. The probability distribution constructed in our example has sensitive dependencies among the agents. In contrast, we show that if the dependency between the agents' valuations is bounded, the problem can be approximated with a factor close to 1.

STOC Conference 1999 Conference Paper

Algorithmic Mechanism Design (Extended Abstract)

• Noam Nisan
• Amir Ronen