Yoav Shoham

ICLR Conference 2021 Conference Paper

PMI-Masking: Principled masking of correlated spans

• Yoav Levine
• Barak Lenz
• Opher Lieber
• Omri Abend
• Kevin Leyton-Brown
• Moshe Tennenholtz
• Yoav Shoham

Masking tokens uniformly at random constitutes a common flaw in the pretraining of Masked Language Models (MLMs) such as BERT. We show that such uniform masking allows an MLM to minimize its training objective by latching onto shallow local signals, leading to pretraining inefficiency and suboptimal downstream performance. To address this flaw, we propose PMI-Masking, a principled masking strategy based on the concept of Pointwise Mutual Information (PMI), which jointly masks a token n-gram if it exhibits high collocation over the corpus. PMI-Masking motivates, unifies, and improves upon prior more heuristic approaches that attempt to address the drawback of random uniform token masking, such as whole-word masking, entity/phrase masking, and random-span masking. Specifically, we show experimentally that PMI-Masking reaches the performance of prior masking approaches in half the training time, and consistently improves performance at the end of pretraining.

AAAI Conference 2015 Conference Paper

Stable Invitations

• Hooyeon Lee
• Yoav Shoham

We consider the situation in which an organizer is trying to convene an event, and needs to choose whom out of a given set of agents to invite. Agents have preferences over how many attendees should be at the event and possibly also who the attendees should be. This induces a stability requirement: All invited agents should prefer attending to not attending, and all the other agents should not regret being not invited. The organizer’s objective is to find an invitation of maximum size, subject to the stability requirement. We investigate the computational complexity of finding such an invitation when agents are truthful, as well as the mechanism design problem when agents act strategically.

IJCAI Conference 2015 Conference Paper

The Right to Obscure: A Mechanism and Initial Evaluation

• Eric Hsin-Chun Huang
• Jaron Lanier
• Yoav Shoham

The recent landmark “right to be forgotten” ruling by the EU Court gives EU citizens the right to remove certain links that are “inaccurate, inadequate, irrelevant or excessive” from search results under their names. While we agree with the spirit of the ruling—to empower individuals to manage their personal data while keeping a balance between such right and the freedom of expression, we believe that the ruling is impractical as it provides neither precise criteria for evaluating removal requests nor concrete guidelines for implementation. Consequently, Google’s current implementation has several problems concerning scalability, objectivity, and responsiveness. Instead of the right to be forgotten, we propose the right to obscure certain facts about oneself on search engines, and a simple mechanism which respects the spirit of the ruling by giving people more power to influence search results for queries on their names. Specifically, under our proposed mechanism, data subjects will be able to register minus terms, and search results for their name queries that contain such terms would be filtered out. We implement a proof-of-concept search engine following the proposed mechanism, and conduct experiments to explore the influences it might have on users’ impressions on different data subjects.

TIST Journal 2011 Journal Article

Fair Seeding in Knockout Tournaments

• Thuc Vu
• Yoav Shoham

We investigated the existence of fair seeding in knockout tournaments. We define two fairness criteria, both adapted from the literature: envy-freeness and order preservation. We show how to achieve the first criterion in tournaments whose structure is unconstrained, and prove an impossibility result for balanced tournaments. For the second criterion we have a similar result for unconstrained tournaments, but not for the balanced case. We provide instead a heuristic algorithm which we show through experiments to be efficient and effective. This suggests that the criterion is achievable also in balanced tournaments. However, we prove that it again becomes impossible to achieve when we add a weak condition guarding against the phenomenon of tournament dropout.

IJCAI Conference 2011 Conference Paper

Hustling in Repeated Zero-Sum Games with Imperfect Execution

• Christopher Archibald
• Yoav Shoham

We study repeated games in which players have imperfect execution skill and one player's true skill is not common knowledge. In these settings the possibility arises of a player "hustling, " or pretending to have lower execution skill than they actually have. Focusing on repeated zero-sum games, we provide a hustle-proof strategy; this strategy maximizes a player's payoff, regardless of the true skill level of the other player.

AIJ Journal 2010 Journal Article

Designing competitions between teams of individuals

• Pingzhong Tang
• Yoav Shoham
• Fangzhen Lin

We consider a setting with two teams, each with a number of players. There is an ordering of all players that determines outcome of matches between any two players from the opposing teams. Neither the teams nor the competition designer know this ordering, but each team knows the derived ordering of strengths among its own players. Each team announces an ordering of its players, and the competition designer schedules matches according to the announced orderings. This setting in general allows for two types of manipulations by a team: Misreporting the strength ordering (lack of truthfulness), and deliberately losing a match (moral hazard). We prove necessary and sufficient conditions for a set of competition rules to have the properties that truthful reporting are dominant strategies and maximum effort in matches are Nash equilibrium strategies, and certain fairness conditions are met. Extensions of the original setting are discussed.

AAMAS Conference 2010 Conference Paper

Internal Implementation

• Ashton Anderson
• Yoav Shoham
• Alon Altman

We introduce a constrained mechanism design setting calledinternal implementation, in which the mechanism designeris explicitly modeled as a player in the game of interest. This distinguished player has the opportunity to modify thegame before play. Specifically, the player is able to makereliable binding commitments of outcome-specific monetarytransfers to the other players in the game. We characterizethe power of internal implementation for certain interestingclasses of games, and show that the impact of internal implementation on the utility of the players' and the social welfareis often counterintuitive; for example, the social welfare canbe arbitrarily worse after an internal implementation.

AAMAS Conference 2010 Conference Paper

Joint Process Games: From Ratings to Wikis

• Michael Munie
• Yoav Shoham

We introduce a game setting called a joint process, where the history of actions determine the state, and the state and agent properties determine the payoff. This setting is a special case of stochastic games and is a natural model for situations with alternating control. Joint process games have applications as diverse as aggregate rating sites and wiki page updates. These games are related to Black's median voter theorem and also strongly connected to Moulin's strategy-proof voting schemes. When each agent has a personal goal, we look at how the play converges under a simple myopic action rule, and prove that not only do these simple dynamics converge, but the actions selected also form a Nash equilibrium. The convergence point is not the mean or the median of the set of agent goals; instead we prove the convergence point is the median of the set of agent goals and a set of focal points. This work provides the first theoretical model of wiki-type behavior and opens the door to more questions about the properties of these games.

KR Conference 2010 Conference Paper

Joint revision of belief and intention

• Thomas Icard
• Eric Pacuit
• Yoav Shoham

1. The agent makes some observation, e. g. from sensory inWe present a formal semantical model to capture action, belief and intention, based on the “database perspective” (Shoham 2009). We then provide postulates for belief and intention revision, and state a representation theorem relating our postulates to the formal model. Our belief postulates are in the spirit of the AGM theory; the intention postulates stand in rough correspondence with the belief postulates. Motivation

AAMAS Conference 2010 Conference Paper

Optimal Seeding in Knockout Tournaments

• Thuc Vu
• Yoav Shoham

Optimal seeding in balanced knockout tournaments has only been studied in very limited settings, for example, maximizing predictive power for up to 8 players using only the relative ranking of the players (ordinal information). We broaden the scope of the analysis along several dimensions: tournaments of size up to 128, different player models, ordinal as well as cardinal solutions, and two additional objective functions.

AAMAS Conference 2010 Conference Paper

Success, strategy and skill: an experimental study

• Christopher Archibald
• Alon Altman
• Yoav Shoham

In many AI settings an agent is comprised of both action-planning and action-execution components. We examine the relationship between the precision of the execution component, the intelligence of the planning component, and the overall success of the agent. Our motivation lies in determining whether higher execution skill rewards more strategic playing. We present a computational billiards framework in which the interaction between skill and strategy can be experimentally investigated. By comparing the performance of different agents with varying levels of skill and strategic intelligence we show that intelligent planning can contribute most to an agent's success when that agent has imperfect skill.

IJCAI Conference 2009 Conference Paper

• Christopher Archibald
• Alon Altman
• Yoav Shoham

We discuss CUECARD, the program that won the 2008 Computer Olympiad computational pool tournament. Beside addressing intrinsic interest in a complex competitive environment with unique features, our goal is to isolate the factors that contributed to the performance so that the lessons can be transferred to other, similar domains. Specifically, we distinguish among pure engineering factors (such as using a computer cluster), domainspecific factors (such as optimized break shots), and domain-independentfactors (such as state clustering). Our conclusion is that each type of factor contributed to the performance of the program.

TARK Conference 2009 Invited Paper

Considerations on the logic of intention

• Yoav Shoham

AAMAS Conference 2009 Conference Paper

Modeling Billiards Games

• Christopher Archibald
• Yoav Shoham

Two-player games of billiards, of the sort seen in recent Computer Olympiads held by the International Computer Games Association, are an emerging area with unique challenges for A. I. research. Complementing the heuristic/algorithmic aspect of billiards, of the sort brought to the fore in the ICGA billiards tournaments, we investigate formal models of such games. The modeling is surprisingly subtle. While sharing features with existing models (including stochastic games, games on a square, recursive games, and extensive form games), our model is distinct, and consequently requires novel analysis. We focus on the basic question of whether the game has an equilibrium. For finite versions of the game it is not hard to show the existence of a pure strategy Markov perfect Nash equilibrium. In the infinite case, it can be shown that under certain conditions a stationary pure strategy Markov perfect Nash equilibrium is guaranteed to exist.

AAMAS Conference 2009 Conference Paper

On the Complexity of Schedule Control Problems for Knockout Tournaments

• Thuc Vu
• Alon Altman
• Yoav Shoham

Knockout tournaments constitute a common format of sporting events, and also model a specific type of election scheme (namely, sequential pairwise elimination election). In such tournaments the designer controls the shape of the tournament (a binary tree) and the seeding of the players (their assignment to the tree leaves). In this paper we investigate the computational complexity of tournament schedule control, i. e. , designing a tournament that maximizes the winning probability a target player. We start with a generic probabilistic model consisting of a matrix of pairwise winning probabilities, and then investigate the problem under two types of constraint: constraints on the probability matrix, and constraints on the allowable tournament structure. While the complexity of the general problem is as yet unknown, these various constraints – all naturally occurring in practice – serve to push to the problem to one side or the other: easy (polynomial) or hard (NP-complete).

AIJ Journal 2009 Journal Article

Ranking games

• Felix Brandt
• Felix Fischer
• Paul Harrenstein
• Yoav Shoham

The outcomes of many strategic situations such as parlor games or competitive economic scenarios are rankings of the participants, with higher ranks generally at least as desirable as lower ranks. Here we define ranking games as a class of n-player normal-form games with a payoff structure reflecting the players' von Neumann–Morgenstern preferences over their individual ranks. We investigate the computational complexity of a variety of common game-theoretic solution concepts in ranking games and deliver hardness results for iterated weak dominance and mixed Nash equilibrium when there are more than two players, and for pure Nash equilibrium when the number of players is unbounded but the game is described succinctly. This dashes hope that multi-player ranking games can be solved efficiently, despite their profound structural restrictions. Based on these findings, we provide matching upper and lower bounds for three comparative ratios, each of which relates two different solution concepts: the price of cautiousness, the mediation value, and the enforcement value.

AAMAS Conference 2009 Conference Paper

Team Competition

• Pingzhong Tang
• Yoav Shoham
• Fangzhen Lin

In a team competition, two participating teams have an equal number of players, and each team orders its players linearly based on their strengths. A mechanism then specifies how the players from the two teams are matched up and how to score them. There are two types of manipulations by a team: Misreporting the strength ordering and deliberately losing a match. To identify these strategically behaviors, we model the team competition problem in a game-theoretical framework, under which we prove necessary and sufficient conditions which ensure that truthful reporting and maximal effort in matches are equilibrium strategies, and which further ensure certain fairness conditions described by choice functions.

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.

AAAI Conference 2008 Conference Paper

Game Theory Pragmatics: A Challenge for AI

• Yoav Shoham

Game theory has been playing an increasingly visible role in computer science in general and AI in particular, most notably in the area of multiagent systems. I briefly list the areas where most of the action has been in the past decade or so. I then suggest that going forward, the most dramatic interaction between computer science and game theory – with a special role for AI – could be around what might be called game theory pragmatics. 1

IJCAI Conference 2007 Conference Paper

• Felix Brandt
• Felix Fischer
• Paul Harrenstein
• Yoav Shoham

This paper is a comparative study of game-theoretic solution concepts in strictly competitive multiagent scenarios, as commonly encountered in the context of parlor games, competitive economic situations, and some social choice settings. We model these scenarios as ranking games in which every outcome is a ranking of the players, with higher ranks being preferred over lower ones. Rather than confining our attention to one particular solution concept, we give matching upper and lower bounds for various comparative ratios of solution concepts within ranking games. The solution concepts we consider in this context are security level strategies (maximin), Nash equilibrium, and correlated equilibrium. Additionally, we also examine quasi-strict equilibrium, an equilibrium refinement proposed by Harsanyi, which remedies some apparent shortcomings of Nash equilibrium when applied to ranking games. In particular, we compute the price of cautiousness, i. e. , the worst-possible loss an agent may incur by playing maximin instead of the worst (quasi-strict) Nash equilibrium, the mediation value, i. e. , the ratio between the social welfare obtained in the best correlated equilibrium and the best Nash equilibrium, and the enforcement value, i. e. , the ratio between the highest obtainable social welfare and that of the best correlated equilibrium.

IJCAI Conference 2007 Conference Paper

• Felix Brandt
• Tuomas Sandholm
• Yoav Shoham

We study the bidding behavior of spiteful agents who, contrary to the common assumption of self-interest, maximize a convex combination of their own profit and their competitors' losses. The motivation for this assumption stems from inherent spitefulness or, for example, from competitive scenarios such as in closed markets where the loss of a competitor will likely result in future gains for oneself. We derive symmetric Bayes Nash equilibria for spiteful agents in first-price and second-price sealed-bid auctions. In first-price auctions, bidders become "more truthful" the more spiteful they are. Surprisingly, the equilibrium strategy in second-price auctions does not depend on the number of bidders. Based on these equilibria, we compare the revenue in both auction types. It turns out that expected revenue in second-price auctions is higher than expected revenue in first-price auctions in the case of even the most modestly spiteful agents, provided they still care at least at little for their own profit. In other words, revenue equivalence only holds for auctions in which all agents are either self-interested or completely malicious. We furthermore investigate the impact of common knowledge on spiteful bidding. Divulging the bidders' valuations reduces revenue in second-price auctions, whereas it has the opposite effect in first-price auctions.

AIJ Journal 2007 Journal Article

If multi-agent learning is the answer, what is the question?

• Yoav Shoham
• Rob Powers
• Trond Grenager

The area of learning in multi-agent systems is today one of the most fertile grounds for interaction between game theory and artificial intelligence. We focus on the foundational questions in this interdisciplinary area, and identify several distinct agendas that ought to, we argue, be separated. The goal of this article is to start a discussion in the research community that will result in firmer foundations for the area. 1 1 This article has a long history and owes many debts. A first version was presented at the NIPS workshop, Multi-Agent Learning: Theory and Practice, in 2002. A later version was presented at the AAAI Fall Symposium in 2004 [Y. Shoham, R. Powers, T. Grenager, On the agenda(s) of research on multi-agent learning, in: AAAI 2004 Symposium on Artificial Multi-Agent Learning (FS-04-02), AAAI Press, 2004]. Over time it has gradually evolved into the current form, as a result of our own work in the area as well as the feedback of many colleagues. We thank them all collectively, with special thanks to members of the multi-agent group at Stanford in the past three years. Rakesh Vohra and Michael Wellman provided detailed comments on the latest draft which resulted in substantive improvements, although we alone are responsible for the views put forward. This work was supported by NSF ITR grant IIS-0205633 and DARPA grant HR0011-05-1.

AAAI Conference 2007 Conference Paper

Near-Optimal Search in Continuous Domains

• Samuel Ieong
• Yoav Shoham

We investigate search problems in continuous state and action spaces with no uncertainty. Actions have costs and can only be taken at discrete time steps (unlike the case with continuous control). Given an admissible heuristic function and a starting state, the objective is to find a minimum-cost plan that reaches a goal state. As the continuous domain does not allow the tight optimality results that are possible in the discrete case (for example by A*), we instead propose and analyze an approximate forward-search algorithm that has the following provable properties. Given a desired accuracy, and a bound d on the length of the plan, the algorithm computes a lower bound L on the cost of any plan. It either (a) returns a plan of cost L that is at most more than the optimal plan, or (b) if, according to the heuristic estimate, there may exist a plan of cost L of length > d, returns a partial plan that traces the first d steps of such plan. To our knowledge, this is the first algorithm that provides optimality guarantees in continuous domains with discrete control and without uncertainty.

AAMAS Conference 2006 Conference Paper

Learning against multiple opponents

• Thuc Vu
• Rob Powers
• Yoav Shoham

TCS Journal 2005 Journal Article

Non-cooperative computation: Boolean functions with correctness and exclusivity

• Yoav Shoham
• Moshe Tennenholtz

We introduce the concept of non-cooperative computation (NCC), which is the joint computation of a function by self-motivated agents, where each of the agents possesses one of the inputs to the function. In NCC the agents communicate their input (truthfully or not) to a trusted center, which performs a commonly-known computation and distributes the results to the agents. The question is whether the agents can be incented to communicate their true input to the center, allowing all agents to compute the function correctly. NCC is a game theoretic concept and specifically is couched in terms of mechanism design. NCC is a very broad framework and is specialized by imposing specific structure on the agents’ utility functions. The technical results we present are specific to the setting in which each agent has a primary interest in computing the function and a secondary interest in preventing the others from computing it (properties called correctness and exclusivity). For this setting we provide a complete characterization of the Boolean functions that are non-cooperatively computable. We do this for three versions of NCC: a basic deterministic version, a probabilistic version and a version in which the computation can be subsidized by the center. The analysis turns out to depend on whether the inputs of the agents are probabilistically correlated or not and we analyze both cases. 1 1 This work was supported by NSF Grant IIS-0205633.

NeurIPS Conference 2004 Conference Paper

New Criteria and a New Algorithm for Learning in Multi-Agent Systems

• Rob Powers
• Yoav Shoham

We propose a new set of criteria for learning algorithms in multi-agent systems, one that is more stringent and (we argue) better justified than previous proposed criteria. Our criteria, which apply most straightfor- wardly in repeated games with average rewards, consist of three require- ments: (a) against a specified class of opponents (this class is a parameter of the criterion) the algorithm yield a payoff that approaches the payoff of the best response, (b) against other opponents the algorithm's payoff at least approach (and possibly exceed) the security level payoff (or max- imin value), and (c) subject to these requirements, the algorithm achieve a close to optimal payoff in self-play. We furthermore require that these average payoffs be achieved quickly. We then present a novel algorithm, and show that it meets these new criteria for a particular parameter class, the class of stationary opponents. Finally, we show that the algorithm is effective not only in theory, but also empirically. Using a recently introduced comprehensive game theoretic test suite, we show that the algorithm almost universally outperforms previous learning algorithms.

AAMAS Conference 2004 Conference Paper

Run the GAMUT: A Comprehensive Approach to Evaluating Game-Theoretic Algorithms

• Eugene Nudelman
• Jennifer Wortman
• Kevin Leyton-Brown
• Yoav Shoham

AAAI Conference 2004 Conference Paper

Using Contracts to Influence the Outcome of a Game

• Robert McGrew
• Yoav Shoham

We consider how much influence a center can exert on a game if its only power is to propose contracts to the agents before the original game, and enforce the contracts after the game if all agents sign it. Modelling the situation as an extensiveform game, we note that the outcomes that are enforceable are precisely those in which the payoff to each agent is higher than its payoff in at least one of the Nash equilibria of the original game. We then show that these outcomes can still be achieved without any effort actually expended by the center: We propose a mechanism in which the center does not monitor the game, and the contracts are written so that in equilibrium all agents sign and obey the contract, with no need for center intervention.

IJCAI Conference 2003 Conference Paper

A Portfolio Approach to Algorithm Selection

• Kevin Leyton-Brown
• Eugene Nudelman
• Galen Andrew
• Jim McFadden
• Yoav Shoham

TARK Conference 2003 Conference Paper

Towards a general theory of non-cooperative computation

• Robert McGrew 0001
• Ryan Porter
• Yoav Shoham

We generalize the framework of non-cooperative computation (NCC), recently introduced by Shoham and Tennenholtz, to apply to cryptographic situations. We consider functions whose inputs are held by separate, self-interested agents. We consider four components of each agent's utility function: (a) the wish to know the correct value of the function, (b) the wish to prevent others from knowing it, (c) the wish to prevent others from knowing one's own private input, and (d) the wish to know other agents' private inputs. We provide an exhaustive game theoretic analysis of all 2, 1 possible lexicographic orderings among these four considerations, for the case of Boolean functions (mercifully, these 24 cases collapse to four). In each case we identify the class of functions for which there exists an incentive-compatible mechanism for computing the function. In this article we only consider the situation in which the inputs of different agents are probabilistically independent.

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.

UAI Conference 1999 Conference Paper

Expected Utility Networks

• Pierfrancesco La Mura
• Yoav Shoham

We introduce a new class of graphical representations, expected utility networks (EUNs), and discuss some of its properties and potential applications to artificial intelligence and economic theory. In EUNs not only probabilities, but also utilities enjoy a modular representation. EUNs are undirected graphs with two types of arc, representing probability and utility dependencies respectively. The representation of utilities is based on a novel notion of conditional utility independence, which we introduce and discuss in the context of other existing proposals. Just as probabilistic inference involves the computation of conditional probabilities, strategic inference involves the computation of conditional expected utilities for alternative plans of action. We define a new notion of conditional expected utility (EU) independence, and show that in EUNs node separation with respect to the probability and utility subgraphs implies conditional EU independence.

IJCAI Conference 1999 Conference Paper

Speeding Up Ascending-Bid Auctions

• Yuzo Fujishima
• David McAdams
• Yoav Shoham

IJCAI Conference 1999 Conference Paper

Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches

• Yuzo Fujishima
• Kevin Leyton-Brown
• Yoav Shoham

TARK Conference 1998 Conference Paper

Conditional, Hierarchical, Multi-Agent Preferences

• Pierfrancesco La Mura
• Yoav Shoham

We develop a revealed-preferencetheory for multiple agents. Some features of our construction, which draws heavily on Jeffrey's utility theory and on formal constructions by Domotor and Fishburn, are as follows. First, our system enjoys the "small-worlds" property. Second, it represents hierarchical preferences. As a result our expected utility representation is reminscent of type constructions in game theory, except that our construction features higher order utilities as well as higher order probabilities. Finally, our construction includes the representation of conditional preferences, including counterfactual preferences.

AIJ Journal 1998 Journal Article

On the knowledge requirements of tasks

• Ronen I. Brafman
• Joseph Y. Halpern
• Yoav Shoham

In order to successfully perform a task, a situated system requires some information about its domain. If we can understand what information the system requires, we may be able to equip it with more suitable sensors or make better use of the information available to it. These considerations have motivated roboticists to examine the issue of sensor design, and in particular, the minimal information required to perform a task. We show here that reasoning in terms of what the robot knows and needs to know to perform a task is a useful approach for analyzing these issues. We extend the formal framework for reasoning about knowledge, already used in AI and distributed computing, by developing a set of basic concepts and tools for modeling and analyzing the knowledge requirements of tasks. We investigate properties of the resulting framework, and show how it can be applied to robotics tasks.

IJCAI Conference 1997 Conference Paper

A Symmetric View of Utilities and Probabilities

• Yoav Shoham

UAI Conference 1997 Conference Paper

Conditional Utility, Utility Independence, and Utility Networks

• Yoav Shoham

We introduce a new interpretation of two related notions - conditional utility and utility independence. Unlike the traditional interpretation, the new interpretation renders the notions the direct analogues of their probabilistic counterparts. To capture these notions formally, we appeal to the notion of utility distribution, introduced in previous paper. We show that utility distributions, which have a structure that is identical to that of probability distributions, can be viewed as a special case of an additive multiattribute utility functions, and show how this special case permits us to capture the novel senses of conditional utility and utility independence. Finally, we present the notion of utility networks, which do for utilities what Bayesian networks do for probabilities. Specifically, utility networks exploit the new interpretation of conditional utility and utility independence to compactly represent a utility distribution.

AIJ Journal 1997 Journal Article

Economic principles of multi-agent systems

• Craig Boutilier
• Yoav Shoham
• Michael P. Wellman

AIJ Journal 1997 Journal Article

On the emergence of social conventions: modeling, analysis, and simulations

• Yoav Shoham
• Moshe Tennenholtz

We define the notion of social conventions in a standard game-theoretic framework, and identify various criteria of consistency of such conventions with the principle of individual rationality. We then investigate the emergence of such conventions in a stochastic setting; we do so within a stylized framework currently popular in economic circles, namely that of stochastic games. This framework comes in several forms; in our setting agents interact with each other through a random process, and accumulate information about the system. As they do so, they continually reevaluate their current choice of strategy in light of the accumulated information. We introduce a simple and natural strategy-selection rule, called highest cumulative reward (HCR). We show a class of games in which HCR guarantees eventual convergence to a rationally acceptable social convention. Most importantly, we investigate the efficiency with which such social conventions are achieved. We give an analytic lower bound on this rate, and then present results about how HCR works out in practice. Specifically, we pick one of the most basic games, namely a basic coordination game (as defined by Lewis), and through extensive computer simulations determine not only the effect of applying HCR, but also the subtle effects of various system parameters, such as the amount of memory and the frequency of update performed by all agents.

IJCAI Conference 1995 Conference Paper

Knowledge Considerations in Robotics and Distribution of Robotic Tasks

• Ronen I. Brafinan
• Yoav Shoham

We develop a formal tool for representing and analyzing informational aspects of robotic tasks, based on the formal concept of 'knowl­ edge. ' Specifically, we adopt the notion of knowledge-based protocols from distributed systems, and define the notions of knowledge complexity of a robotic task and knowledge ca­ pability of a robot. The resulting formalism naturally captures previous work in the areas of robot information management, but is suffi­ ciently rigorous and natural to allow many ex­ tensions. In this paper we show one novel appli­ cation - the automated distribution of robotic tasks.

AIJ Journal 1995 Journal Article

On social laws for artificial agent societies: off-line design

• Yoav Shoham
• Moshe Tennenholtz

We are concerned with the utility of social laws in a computational environment, laws which guarantee the successful coexistence of multiple programs and programmers. In this paper we are interested in the off-line design of social laws, where we as designers must decide ahead of time on useful social laws. In the first part of this paper we suggest the use of social laws in the domain of mobile robots, and prove analytic results about the usefulness of this approach in that setting. In the second part of this paper we present a general model of social law in a computational system, and investigate some of its properties. This includes a definition of the basic computational problem involved with the design of multi-agent systems, and an investigation of the automatic synthesis of useful social laws in the framework of a model which refers explicitly to social laws.

TARK Conference 1994 Conference Paper

Knowledge as a Tool in Motion Planning and Uncertainty

• Ronen I. Brafman
• Jean-Claude Latombe
• Yoram Moses
• Yoav Shoham

Inspired by the success of the distributed computing community in applying logics of knowledge and time to reasoning ahout distributed protocols, we aim for a similarly powerful and high-level abstraction when reasoning about control problems involving uncertainty. Here we concentrate on robot motion planning, with uncertainty in both control and sensing. This problem has already been well studied within the robotics community. Our contributions include the following: • We define, a new, naturM problem in this domain: obtaining a sound and complete termination condition, given initial and goal locations. • We define a high-level language, a logic of time and knowledge, to reason about motion plans in the presence of uncertainty, and use it to provide general conditions for the existence of sound and complete termination conditions for a broad class of motion plans. ®We characterize the optimal sound termination conditions for the general problem, relate them to a class of fundamental knowledge based protocols and provide a natural example of knowledge based protocols lacking a canonical implementation. 1 *Currently on sabbatical at the Oxford University Computing Laboratory, Oxford OX1 3QD England: The first part of this paper generalizes results of a previous paper by Brafman, I, atombe and Shoham ([BLS93]). Sections 4. 3 and 5 contain ne'w ~aterial.

AIJ Journal 1993 Journal Article

Agent-oriented programming

• Yoav Shoham

A new computational framework is presented, called agent-oriented programming (AOP), which can be viewed as a specialization of object-oriented programming. The state of an agent consists of components such as beliefs, decisions, capabilities, and obligations; for this reason the state of an agent is called its mental state. The mental state of agents is described formally in an extension of standard epistemic logics: beside temporalizing the knowledge and belief operators, AOP introduces operators for obligation, decision, and capability. Agents are controlled by agent programs, which include primitives for communicating with other agents. In the spirit of speech act theory, each communication primitive is of a certain type: informing, requesting, offering, and so on. This article presents the concept of AOP, discusses the concept of mental state and its formal underpinning, defines a class of agent interpreters, and then describes in detail a specific interpreter that has been implemented.

AIJ Journal 1993 Journal Article

Belief as defeasible knowledge

• Yoram Moses
• Yoav Shoham

We investigate the relation between the notions of knowledge and belief. Contrary to the well-known slogan about knowledge being “justified, true belief”, we propose that belief be viewed as defeasible knowledge. We offer several related definitions of belief as knowledge-relative-to-assumptions, and provide complete axiomatic systems for the resulting notions of belief. We also show a close tie between our definitions and the literature on nonmonotonic reasoning. Our definitions of belief have several advantages. First, they are short. Second, we do not need to add anything to the logic of knowledge: the “right” properties of belief fall out of our definitions and the properties of knowledge. Third, the connection between knowledge and belief is derived from one fundamental principle. Finally, a major attraction of logics of knowledge in computer science has been the concrete grounding of the mental notion in objective phenomena; by reducing belief to knowledge we obtain this grounding for a notion of belief.

IJCAI Conference 1993 Conference Paper

Deriving Properties of Belief Update from Theories of Action (II)

• Alvaro del Val
• Yoav Shoham

AIJ Journal 1992 Journal Article

A logic of knowledge and justified assumptions

• Fangzhen Lin
• Yoav Shoham

In this paper we define the logic GK of knowledge and justified assumptions. GK is best understood as a formalization of autoepistemic reasoning processes that are more general than those in Moore's autoepistemic logic, and is formally defined via a modification of Shoham's preference semantics. We show that GK includes not only Moore's autoepistemic logic, but also Reiter's default logic. To our knowledge GK is the first complete semantic unification of the two logics. Similarly to circumscription, GK is based on the notion of logical minimization, and thus provides a bridge between circumscription and fixed-point nonmonotonic logics, an outstanding problem in nonmonotonic logics. As an application of this bridge, we propose a formalization of logic programs with negation-as-failure in circumscription.

TARK Conference 1992 Conference Paper

Multiple Mental Attitudes in Agents

• Yoav Shoham

AAAI Conference 1992 Conference Paper

On the Synthesis of Useful Social Laws for Artificial Agent Societies (Preliminary Report)

• Yoav Shoham

We present a general model of social law in a computational system, and investigate some of its properties. The contribution of this paper is twofold. First, we argue that the notion of social law is not epiphenomenal, but rather should be built into the action representation; we then offer such a representation. Second, we investigate the complexity of automatically deriving useful social laws in this model, given descriptions of the agents’ capabilities, and the goals they might encounter. We show that in general the problem is NP-complete, and identify precise conditions under which it becomes polynomial.

AAAI Conference 1991 Conference Paper

AGENT0: A Simple Agent Language and Its Interpreter

• Yoav Shoham

In [9] we defined the concept of agent oriented programming (AOP), which can be viewed as a specialization of object oriented programming (OOP). AOP views objects as agents with mental state, and, in the spirit of speech act theory, identifies a number of message types - informing, requesting, offering, and so on. AOP is a general framework. In this paper we present a specific and simple language called AGENTO; we define its syntax, present its interpreter, and illustrate both through an example.

TARK Conference 1990 Conference Paper

Epistemic Semantics for Fixed-Points Non-Monotonic Logics

• Fangzhen Lin
• Yoav Shoham

Default Logic and Autoepistemic Logic are the two best-known fixed-points nonmonotonic logics. Despite the fact that they are known to be closely related and that the epistemic nature of Autoepistemic Logic is obvious, the only semantics that have been offered for Default Logic to date are complex and have little to do with epistemic notions [Etherington 1987]. In this paper we provide simple uniform epistemic semantics for the two logics. We do so by translating them both into a new logic, called GK, of Grounded Knowledge, which embodies a modification of preference semantics [Shoham 1987]. Beside their simplicity and uniformity, the semantics have two other advantages: They allow easy proofs of the connections between Default Logic and Autoepistemic Logic, and suggest a general class of logics of which the two logics are special cases.

IJCAI Conference 1989 Conference Paper

Belief as Defeasible Knowledge

• Yoav Shoham
• Yoram Moses

NMR Workshop 1989 Conference Paper

New Results on Semantical Non-Monotonic Reasoning

• Allen L. Brown Jr.
• Yoav Shoham

Abstract In earlier reports we presented a semantical account of nonmonotonic reasoning based on the partial ordering of interpretations of standard logics. In this article we generalize and extend the earlier work. We elucidate the structural relation between the new work and the old. Finally, we apply the new results to give a logical semantical account of justification-based truth maintenance.

IJCAI Conference 1989 Conference Paper

Time for Action: On the Relation Between Time, Knowledge and Action

• Yoav Shoham

We consider the role played by the concept of action in AI. We first briefly summarize the advantages and limitations of past approaches to taking the concept as primitive, as embodied in the situation calculus and dynamic logic. We also briefly summarize the alternative, namely adopting a temporal framework, and point out its complementary advantages and limitations. We then propose a framework that retains the advantages of both viewpoints, and that ties the notion of action closely to that of knowledge. Specifically, we propose starting with the notion of time lines, and defining the notion of action as the ability to make certain choices among sets of time lines. Our definitions shed new light on the connection between time, action, knowledge and ignorance, choice-making, feasibility, and simultaneous reasoning about the same events at different levels of detail.

AIJ Journal 1988 Journal Article

Chronological ignorance: Experiments in nonmonotonic temporal reasoning

• Yoav Shoham

We offer solutions to two problems in formal temporal reasoning, the qualification problem and the extended prediction problem, which, as argued in [22], subsume the infamous frame problem. The solutions make use of nonmonotonic logics. In particular, we advocate the use of a new nonmonotonic logic, the logic of chronological ignorance. On the practical level, we demonstrate the utility of the logic in specific cases. On the more theoretical level, we identify classes of theories in the logic that have nice properties: they each have a model that is (in a certain sense) unique, and those models can be computed very easily. The first class, causal theories, is sufficiently expressive to solve the qualification problem. It also suggests a new account of the intuitive notion of causation, although we do not discuss that in depth. This class is then generalized to the class of inertial theories, which are sufficiently expressive to solve also the extended prediction problem. Inertial theories embody the concept of potential histories, which are the way the world tends to behave “naturally. ”

AIJ Journal 1988 Journal Article

Problems in formal temporal reasoning

• Yoav Shoham
• Drew McDermott

Ever since its introduction by McCarthy and Hayes in 1969, the so-called frame problem has been the object of much fascination and debate. Although it was defined in the narrow context of the situation calculus, a specific temporal formalism, it was clear from the start that it is in fact a manifestation of some fundamental problem in temporal reasoning. Our aim in this informal paper is to identify the general form of certain classes of problems that arise in formal temporal reasoning. We argue that problems such as the frame problem arise from the conflicting desires to reason both rigorously and efficiently about the future. This conflict does not depend on the particular underlying temporal formalism. In particular, we identify two formalism-independent problems, called the qualification problem and the extended prediction problem, which subsume the frame problem. To illustrate the fact that these problems are indeed inherent to the prediction task and not to a particular formalism, we show that they arise in two distinct frameworks: classical mechanics, and Hayes' histories notation.

IJCAI Conference 1987 Conference Paper

Nonmonotonic Logics: Meaning and Utility

• Yoav Shoham

We propose a unifying framework for nonmonotonic logics, which subsumes previously published systems, and at the same time is very simple. We discuss some of the technicalities of the new general framework, illustrate briefly how some previous systems are special cases of it, and finish an informal discussion of the intuitive meaning of nonmonotonic inferences.

ECAI Conference 1987 Conference Paper

Reified Temporal Logics: Semantical and Ontological Considerations

• Yoav Shoham

AIJ Journal 1987 Journal Article

Temporal logics in AI: Semantical and ontological considerations

• Yoav Shoham

One way to represent temporal information in a logical formalism is by associating “proposition types” with time points or time intervals. The way this is usually done in AI is by “reifying” propositions, so that what otherwise would have been formulas actually appear as arguments to some “predicate, ” say TRUE, as in TRUE( t 1, t 2, COLOR(HOUSE, RED)). This way time is referred to explicitly, while retaining its special notational and conceptual status. We examine this method by looking closely at two of the more influential formalisms featuring reified propositions, those of Allen and McDermott. We show that these do not have completely clear semantics, and that they make some unfortunate and unnecessary ontological commitments. Finally, we present a new formalism and demonstrate that it does not suffer from these disadvantages.

AAAI Conference 1986 Conference Paper

Chronological Ignorance: Time, Nonmonotonicity, Necessity and Causal Theories

• Yoav Shoham

Concerned with the problem of reasoning efficiently about change within a formal system, we identify the initiation problem. The solution to it which we offer, called the logic of chronological ignorance, combines temporal logic, nonmonotonic logic, and the modal logic of necessity. We identify a class of theories, called causal theories, which have elegant model-theoretic and complexity properties in the new logic.

IJCAI Conference 1985 Conference Paper

Naive Kinematics: One Aspect of Shape

• Yoav Shoham

AAAI Conference 1984 Conference Paper

Knowledge Inversion

• Yoav Shoham

We define the direction of knowledge, and what it means to extend that direction. A special case is function inversion, and we give three algorithms for function inversion. Their performance on non-trivial problems and their shortcomings are demonstrated. All algorithms are implemented in Prolog-