Dov Monderer

AIJ Journal 2009 Journal Article

Strong mediated equilibrium

• Dov Monderer
• Moshe Tennenholtz

Stability against potential deviations by sets of agents is a most desired property in the design and analysis of multi-agent systems. However, unfortunately, this property is typically not satisfied. In game-theoretic terms, a strong equilibrium, which is a strategy profile immune to deviations by coalition, rarely exists. This paper suggests the use of mediators in order to enrich the set of situations where we can obtain stability against deviations by coalitions. A mediator is defined to be a reliable entity, which can ask the agents for the right to play on their behalf, and is guaranteed to behave in a pre-specified way based on messages received from the agents. However, a mediator cannot enforce behavior; that is, agents can play in the game directly, without the mediator's help. A mediator generates a new game for the players, the mediated game. We prove some general results about mediators, and mainly concentrate on the notion of strong mediated equilibrium, which is just a strong equilibrium at the mediated game. We show that desired behaviors, which are stable against deviations by coalitions, can be obtained using mediators in several classes of settings.

AIJ Journal 2009 Journal Article

Two-terminal routing games with unknown active players

• Itai Ashlagi
• Dov Monderer
• Moshe Tennenholtz

We analyze 2-terminal routing games with linear cost functions and with unknown number of active players. We deal with both splittable and unsplittable models. We prove the existence and uniqueness of a symmetric safety-level equilibrium in such games and show that in many cases every player benefits from the common ignorance about the number of players. Furthermore, we prove new theorems on existence and uniqueness of equilibrium in 2-terminal convex routing games with complete information.

IJCAI Conference 2007 Conference Paper

• Dov Monderer

We introduce and analyze q -potential games and q -congestion games, where q is a positive integer. A 1-potential (congestion) game is a potential (congestion) game. We show that a game is a q -potential game if and only if it is (up to an isomorphism) a q -congestion game. As a corollary, we derive the result that every game in strategic form is a q -congestion game for some q. It is further shown that every q -congestion game is isomorphic to a q -network game, where the network environment is defined by a directed graph with one origin and one destination. Finally we discuss our main agenda: The issue of representing q -congestion games with non-negative cost functions by congestion models with non-negative and monotonic facility cost functions. We provide some initial results in this regard.

AIJ Journal 2007 Journal Article

Learning equilibrium as a generalization of learning to optimize

• Dov Monderer
• Moshe Tennenholtz

We argue that learning equilibrium is an appropriate generalization to multi-agent systems of the concept of learning to optimize in single-agent setting. We further define and discuss the concept of weak learning equilibrium.

AAMAS Conference 2007 Conference Paper

Routing Games with an Unknown Set of Active Players

• Itai Ashlagi
• Dov Monderer
• Moshe Tennenholtz

In many settings there exists a set of potential participants, but the set of participants who are actually active in the system, and in particular their number, is unknown. This topic has been first analyzed by Ashlagi, Monderer, and Tennenholtz [AMT] in the context of simple routing games, where the network consists of a set of parallel links, and the agents can not split their jobs among different paths. AMT used the model of pre-Bayesian games, and the concept of safetylevel equilibrium for the analysis of these games. In this paper we extend the work by AMT. We deal with splitable routing games, where each player can split his job among paths in a given network. In this context we generalize the analysis to all two-node networks, in which paths may intersect in unrestricted manner. We characterize the relationships between the number of potential participants and the number of active participants under which ignorance is beneficial to each of the active participants.

AAMAS Conference 2006 Conference Paper

Resource Selection Games with Unknown Number of Players

• Itai Ashlagi
• Dov Monderer
• Moshe Tennenholtz

UAI Conference 2006 Conference Paper

Robust Learning Equilibrium

• Itai Ashlagi
• Moshe Tennenholtz
• Dov Monderer

We introduce robust learning equilibrium. The idea of learning equilibrium is that learning algorithms in multi-agent systems should themselves be in equilibrium rather than only lead to equilibrium. That is, learning equilibrium is immune to strategic deviations: Every agent is better off using its prescribed learning algorithm, if all other agents follow their algorithms, regardless of the unknown state of the environment. However, a learning equilibrium may not be immune to non strategic mistakes. For example, if for a certain period of time there is a failure in the monitoring devices (e.g., the correct input does not reach the agents), then it may not be in equilibrium to follow the algorithm after the devices are corrected. A robust learning equilibrium is immune also to such non-strategic mistakes. The existence of (robust) learning equilibrium is especially challenging when the monitoring devices are 'weak'. That is, the information available to each agent at each stage is limited. We initiate a study of robust learning equilibrium with general monitoring structure and apply it to the context of auctions. We prove the existence of robust learning equilibrium in repeated first-price auctions, and discuss its properties.

UAI Conference 2005 Conference Paper

On the Value of Correlation

• Itai Ashlagi
• Dov Monderer
• Moshe Tennenholtz

Correlated equilibrium (Aumann, 1974) generalizes Nash equilibrium to allow correlation devices. Aumann showed an example of a game, and of a correlated equilibrium in this game, in which the agents' surplus (expected sum of payo s) is greater than their surplus in all mixed-strategy equilibria. Following the idea initiated by the price of anarchy literature (Koutsoupias & Papadimitriou, 1999;Papadimitriou, 2001) this suggests the study of two major measures for the value of correlation in a game with non-negative payoffs: 1. The ratio between the maximal surplus obtained in a correlated equilibrium to the maximal surplus obtained in a mixed-strategy equilibrium. We refer to this ratio as the mediation value. 2. The ratio between the maximal surplus to the maximal surplus obtained in a correlated equilibrium. We refer to this ratio as the enforcement value. In this work we initiate the study of the mediation and enforcement values, providing several general results on the value of correlation as captured by these concepts. We also present a set of results for the more specialized case of congestion games (Rosenthal,1973), a class of games that received a lot of attention in the recent literature.

TARK Conference 2003 Conference Paper

Economic efficiency versus complexity communication

• Dov Monderer

AIJ Journal 2000 Journal Article

Optimal auctions revisited

• Dov Monderer
• Moshe Tennenholtz

This paper addresses several basic problems inspired by the adaptation of economic mechanisms, and auctions in particular, to the Internet. Computational environments such as the Internet offer a high degree of flexibility in auctions' rules. This makes the study of optimal auctions especially interesting in such environments. We present an upper bound on the revenue obtained by a seller in any auction with a fixed number of participants, and we show that this bound may be a least upper bound in some setups. We further show that the revenue obtained by standard auctions (e. g. , English auctions) approaches the theoretical bound, when the number of participants is large. Our results heavily rely on the risk-aversion assumption made in the economics literature. We further show that without this assumption, the seller's revenue (for a fixed number of participants) may significantly exceed the upper bound if the participants are sufficiently risk-seeking.

AAAI Conference 1999 Conference Paper

Distributed Games: From Mechanisms to Protocols

• Dov Monderer
• Moshe Tennenholtz
• Technion - Israel Institute of Technology

The theory of mechanism design in economics/game theory deals with a center who wishes to maximize an objective function which depends on a vector of information variables. The value of each variable is known only to a selfish agent, which is not controlled by the center. In order to obtain its objective the center constructs a game, in which every agent participates and reveals its information, becausethese actions maximize its utility. However, several crucial new issues arise when one tries to transform existing economic mechanisms into protocols to be used in computational environments. In this paper we deal with two such issues: 1. The communication structure, and 2. the representation (syntax) of the agents’ information. The existing literature on mechanism design implicitly assumes that these two features are not relevant. In particular, it assumes a communication structure in which every agent is directly connected to the center. We present new protocols that can be implemented in a large variety of communication structures, and discuss the sensitivity of these protocols to the way in which information is presented.

TARK Conference 1998 Conference Paper

Distributed Games

• Dov Monderer
• Moshe Tennenholtz

The Internet exhibits forms of interactions which are not captured by existing models in economics, artificial intelligence and gz. me theory. New models are needed to deal with these multi-agent interactions. In this paper we present a new model - distributed ga. mes. In such a model each player controls a number of agents which participate in asynchronous parallel multi-agent interactions (games). The agents jointly and strategically (partially) control the level of information monitoring and the level of recall by broadcasting messages. As an application, we show that the cooperative outcome of the Prisoner's Dilemma game can be obtained in equilibri, !m in such a setting.

AAAI Conference 1998 Conference Paper

Optimal Auctions Revisited

• Dov Monderer