On Rational Computability and Communication Complexity \Lambda (2009)
Yoav Shoham, Moshe Tennenholtz
1
Introduction to Combinatorial Auctions (2009)
Peter Cramton, Yoav Shoham, Richard Steinberg
Combinatorial auctions are those auctions in which bidders can place bids on combinations of items, called ‘‘packages,’ ’ rather than just individual items. The study of combinatorial...
Felix Brandt, Felix Fischer, Yoav Shoham
We embark on an initial study of a new class of strategic (normal-form) games, so-called ranking games, in which the payoff to each agent solely depends on his position in a ranking of the agents...
CHAPTER 13 An Overview of Agent-Oriented Programming (2008)
have been working in areas related to software agents for a number of years 1now, together with many students and other colleagues. Recently, terms such as "(intelligent) (software) agents,...
Near-Optimal Search in Continuous Domains (2008)
Samuel Ieong, Nicolas Lambert, 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)....
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...
Abstract On Cheating in Sealed-Bid Auctions (2008)
Motivated by the rise of online auctions and their relative lack of security, this paper analyzes two forms of cheating in sealed-bid auctions. The first type of cheating we consider occurs when the...
Abstract Simple Search Methods For Finding A Nash (2008)
Ryan Porter, Eugene Nudelman, Yoav Shoham
We present two simple search methods for computing a sample Nash equilibrium in a normal-form game: one for 2-player games and one for n-player games. Both algorithms bias the search towards supports...
General Terms Economics, Design (2008)
In many online domains, agents share goods or services that are both cheap to provide and valuable to receive. Examples include ratings in a recommender system, forwarding a message to node closer to...
Spiteful Bidding in Sealed-Bid Auctions (2008)
Felix Br, Tuomas S, Yoav Shoham
Abstract. We study the bidding behavior of spiteful agents who, contrary to the common assumption of self-interest, maximize the weighted difference of their own profit and their competitors ’...
Introduction to Combinatorial Auctions (2008)
Peter Cramton, Yoav Shoham, Richard Steinberg
Combinatorial auctions are those auctions in which bidders can place bids on combinations of items, called “packages, ” rather than just individual items. The study of combinatorial auctions is...
An Overview of Combinatorial Auctions 1 (2008)
Peter Cramton, Yoav Shoham, Richard Steinberg
An auction is combinatorial when bidders can place bids on combinations of items, called “packages, ” rather than just individual items. Computer scientists are interested in combinatorial...
Incentive Mechanisms for Smoothing Out A Focused Demand for Network Resources Abstract (2008)
Kevin Leyton-brown, Ryan Porter, Balaji Prabhakar, Yoav Shoham, Shobha Venkataraman
We explore the problem of sharing network resources when users ’ preferences lead to temporally concentrated loads, resulting in an inefficient use of the network. In such cases external incentives...
Incentive Mechanisms for Smoothing Out A Focused Demand for Network Resources Abstract (2008)
Kevin Leyton-brown, Ryan Porter, Balaji Prabhakar, Yoav Shoham, Shobha Venkataraman
We explore the problem of sharing network resources when users ’ preferences lead to temporally concentrated loads, resulting in an inefficient use of the network. In such cases external incentives...
Bidding Clubs in First-Price Auctions Extended Abstract (2008)
Kevin Leyton-brown, Yoav Shoham, Moshe Tennenholtz
We introduce a class of mechanisms, called bidding clubs, that allow agents to coordinate their bidding in auctions. Bidding clubs invite a set of agents to join, and each invited agent freely...
His Group, Yoav Shoham, Fausto Giunchiglia, His Group
Here, we survey the problem of formalizing context and explore what is needed for an acceptable account of this abstract notion. The issue of context arises in various areas of AI, including...
Empirical hardness models: Methodology and a case study on combinatorial auctions (2008)
Kevin Leyton-brown, Eugene Nudelman, Yoav Shoham
Is it possible to predict how long an algorithm will run on a previouslyunseen instance of an N P-hard problem? If so, what uses can be found for models that make such predictions? This paper...
Bidding Clubs in First-Price Auctions Extended Abstract (2008)
Kevin Leyton-brown, Yoav Shoham, Moshe Tennenholtz
We introduce a class of mechanisms, called bidding clubs, that allow agents to coordinate their bidding in auctions. Bidding clubs invite a set of agents to join, and each invited agent freely...
Boosting as a Metaphor for Algorithm Design Kevin Leyton-Brown, Eugene Nudelman, (2008)
Galen Andrew, Jim Mcfadden, Yoav Shoham
Abstract. Hard computational problems are often solvable by multiple algorithms that each perform well on different problem instances. We describe techniques for building an algorithm portfolio that...
Chapter 18 A Test Suite for Combinatorial (2008)
Kevin Leyton-brown, Yoav Shoham
Many researchers have proposed algorithms for determining the winners of general combinatorial auctions, with encouraging results. (Some of these algorithms are described in Chapter 14 of this book.)...
Empirical hardness models: Methodology and a case study on combinatorial auctions (2008)
Kevin Leyton-brown, Eugene Nudelman, Yoav Shoham
Is it possible to predict how long an algorithm will run on a previouslyunseen instance of an N P-hard problem? If so, what uses can be found for models that make such predictions? This paper...
Chapter 18 A Test Suite for Combinatorial (2008)
Kevin Leyton-brown, Yoav Shoham
Many researchers have proposed algorithms for determining the winners of general combinatorial auctions, with encouraging results. (Some of these algorithms are described in Chapter 14 of this book.)...
Computational Complexity (2007)
Daniel Lehmann, Liadan Ita O'callaghan, Yoav Shoham
Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a dicult optimization problem. This is true of mechanisms for combinatorial auctions, which...
On the Persistence of Knowledge and Ignorance: A Preliminary Report (2007)
We study a particular model of the way in which a single agent's knowledge evolves over time. The two fundamental properties of the model are that knowledge always persists (i.e., agents have...
Representing Time and Action in Artificial Intelligence (2007)
Introduction In one way or another, every area of AI has to do with time. Medical diagnosis systems reason about the time at which the virus infected the blood system. Device troubleshooting systems...
Knowledge, Certainty, Belief, and Conditionalisation (2007)
We offer a system to capture the relationship between knowledge and belief, which also sheds new light on each of them in isolation. In the case of knowledge, we strongly reject the property of...
In its early days AI played an important role in the development of novel programming paradigms. There is an opportunity now to do it again, by inventing new programming languages and systems that...
Using Contracts to Influence the Outcome of a Game # (2007)
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...
General Terms Economics, Design (2007)
In many online domains, agents share goods or services that are both cheap to provide and valuable to receive. Examples include ratings in a recommender
Ryan Porter, Yoav Shoham, Moshe Tennenholtz
We introduce a new mechanism-design problem called fair imposition. In this setting a center wishes to fairly allocate tasks among a set of agents whose cost structures are known only to them, and...
Please Do Not Distribute An Adaptive Agent for Automated Web Browsing (2007)
Marko Balabanovid, Yoav Shoham, Yeogirl Yun
The current exponential growth of the Internet precipitates a need for new tools to help people cope with the volume of information. To complement recent work on creating searchable indexes of the...
Boosting as a Metaphor for Algorithm Design (2007)
Galen Andrew, Jim Mcfadden, Yoav Shoham
Abstract. Hard computational problems are often solvable by multiple algorithms that each perform well on different problem instances. We describe techniques for building an algorithm portfolio that...
Ryan Porter, Yoav Shoham, Moshe Tennenholtz
We introduce a new mechanism-design problem called fair imposition. In this setting a center wishes to fairly allocate tasks among a set of agents whose cost structures are known only to them, and...
Incentive Mechanisms for Smoothing Out A Focused Demand for Network Resources (2007)
Kevin Leyton-brown, Ryan Porter, Balaji Prabhakar, Yoav Shoham, Shobha Venkataraman
We explore the problem of sharing network resources when users ' preferences lead to temporally concentrated loads, resulting in an ine#cient use of the network. In such cases external...
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...
Bidding Clubs in First-Price Auctions Extended Abstract (2007)
Kevin Leyton-brown, Yoav Shoham, Moshe Tennenholtz
We introduce a class of mechanisms, called bidding clubs, that allow agents to coordinate their bidding in auctions. Bidding clubs invite a set of agents to join, and each invited agent freely...
John Mitchell, Yoav Shoham, Vanessa Teague
algorithmic mechanism design and network security
Computational Complexity (2007)
Daniel Lehmann, Liadan Ita O'callaghan, Yoav Shoham
Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a dicult optimization problem. This is true of mechanisms for combinatorial auctions, which...
Computational Complexity (2007)
Daniel Lehmann, Liadan Ita O'callaghan, Yoav Shoham
Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a dicult optimization problem. This is true of mechanisms for combinatorial auctions, which...
Motivated by the rise of online auctions and their relative lack of security, this paper analyzes two forms of cheating in sealed-bid auctions. The first type of cheating we consider occurs when the...
From Belief Revision to Belief Fusion (2007)
We introduce a new operator|belief fusion|which is a generalization of the classical AGM revision operator to the multi-agent case. In the process we dene pedigreed belief states, which enrich...
Boosting as a Metaphor for Algorithm Design (2007)
Galen Andrew, Jim Mcfadden, Yoav Shoham
Introduction Although some algorithms are better than others on average, there is rarely a best algorithm for a given problem. Instead, different algorithms often perform well on different problem...
Asymptotically Optimal Repeated Auctions for Sponsored Search (2007)
that is, auctions which maximize revenue as the number of bidders grows. We do so under two alternative behavioral assumptions. The first explicitly models the repeated nature of keyword auctions. It...
A general criterion and an algorithmic framework for learning in multi-agent systems (2007)
Rob Powers, Yoav Shoham, Thuc Vu
in multi-agent systems
If multi-agent learning is the answer, what is the question (2006)
Yoav Shoham, Rob Powers, Trond Grenager
www.elsevier.com/locate/artint 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...
Fast and Compact: A Simple Class of Congestion Games (2005)
Samuel Ieong, Robert Mcgrew, Eugene Nudelman, Yoav Shoham, Qixiang Sun
We study a simple, yet rich subclass of congestion games that we call singleton games. These games are exponentially more compact than general congestion games. In contrast with some other compact...
Spiteful Bidding in Sealed-Bid Auctions (2005)
Brandt, Felix, Sandholm, Tuomas, Shoham, Yoav
We study the bidding behavior of spiteful agents who, contrary to the common assumption of self-interest, maximize the weighted difference of their own profit and their competitors' profit. This...
Simple search methods for finding a Nash equilibrium (2004)
Ryan Porter, Eugene Nudelman, Yoav Shoham
We present two simple search methods for computing a sample Nash equilibrium in a normal-form game: one for 2player games and one for n-player games. We test these algorithms on many classes of...
Understanding random sat: Beyond the clauses-to-variables ratio (2004)
Eugene Nudelman, Alex Devkar, Yoav Shoham, Kevin Leyton-brown
Abstract. It is well known that the ratio of the number of clauses to the number of variables in a random k-SAT instance is highly correlated with the instance's empirical hardness. We consider...
Simple search methods for finding a Nash equilibrium (2004)
Ryan Porter, Eugene Nudelman, Yoav Shoham
Nash equilibrium (NE) is arguably the most important concept in game theory, and yet remarkably little is known about the problem of computing a sample NE in a normal-form game. All evidence points...
Run the GAMUT: A comprehensive approach to evaluating game-theoretic algorithms (2004)
Eugene Nudelman, Jennifer Wortman, Yoav Shoham, Kevin Leyton-brown
We present GAMUT 1, a suite of game generators designed for testing game-theoretic algorithms. We explain why such a generator is necessary, offer a way of visualizing relationships between the sets...
Understanding random sat: Beyond the clauses-to-variables ratio (2004)
Eugene Nudelman, Alex Devkar, Yoav Shoham, Kevin Leyton-brown
Abstract. It is well known that the ratio of the number of clauses to the number of variables in a random k-SAT instance is highly correlated with the instance’s empirical hardness. We consider the...
Run the GAMUT: A Comprehensive Approach To Evaluating Game-Theoretic Algorithms (2004)
Eugene Nudelman, Jennifer Wortman, Yoav Shoham, Kevin Leyton-Brown
We present GAMUT , a suite of game generators designed for testing game-theoretic algorithms. We explain why such a generator is necessary, offer a way of visualizing relationships between the sets...
Run the GAMUT: A Comprehensive Approach To Evaluating Game-Theoretic Algorithms (2004)
Eugene Nudelman, Jennifer Wortman, Yoav Shoham, Kevin Leyton-Brown
We present GAMUT , a suite of game generators designed for testing game-theoretic algorithms. We explain why such a generator is necessary, offer a way of visualizing relationships between the sets...
SATzilla: An Algorithm Portfolio for SAT (2004)
Eugene Nudelman, Alex Devkar, Yoav Shoham, Kevin Leyton-Brown, Holger Hoos
Introduction Inspired by the success of recent work in the constraint programming community on typical-case complexity, in [3] we developed a new methodology for using machine learning to study...
SATzilla: An Algorithm Portfolio for SAT (2004)
Eugene Nudelman Alex, Alex Devkar, Yoav Shoham, Kevin Leyton-brown, Holger Hoos
Introduction Inspired by the success of recent work in the constraint programming community on typical-case complexity, in [3] we developed a new methodology for using machine learning to study...
SATzilla: An algorithm portfolio for SAT (2004)
Eugene Nudelman, Alex Devkar, Yoav Shoham, Kevin Leyton-brown, Holger Hoos
Understanding random sat: Beyond the clauses-to-variables ratio (2004)
Eugene Nudelman, Kevin Leyton-brown, Holger H. Hoos, Alex Devkar, Yoav Shoham
Abstract. It is well known that the ratio of the number of clauses to the number of variables in a random k-SAT instance is highly correlated with the instance’s empirical hardness. We consider the...
On the agenda(s) of research on multi-agent learning (2004)
Yoav Shoham, Rob Powers, Trond Grenager
We survey the recent work in AI on multi-agent reinforcement learning (that is, learning in stochastic games). After tracing a representative sample of the recent literature, we argue that, while...
SATzilla: An algorithm portfolio for SAT (2004)
Eugene Nudelman, Alex Devkar, Yoav Shoham, Kevin Leyton-brown, Holger Hoos
Understanding random sat: Beyond the clauses-to-variables ratio (2004)
Eugene Nudelman, Kevin Leyton-brown, Holger H. Hoos, Alex Devkar, Yoav Shoham
Abstract. It is well known that the ratio of the number of clauses to the numberof variables in a random k-SAT instance is highly correlated with the instance'sempirical hardness. We consider...
Run the GAMUT: A comprehensive approach to evaluating game-theoretic algorithms (2004)
Eugene Nudelman, Jennifer Wortman, Yoav Shoham, Kevin Leyton-brown
We present GAMUT 1, a suite of game generators designed for testing game-theoretic algorithms. We explain why such a generator is necessary, offer a way of visualizing relationships between the sets...
On the agenda(s) of research on multi-agent learning (2004)
Yoav Shoham, Rob Powers, Trond Grenager
We survey the recent work in AI on multi-agent reinforcement learning (that is, learning in stochastic games). After tracing a representative sample of the recent literature, we argue that, while...
Simple search methods for finding a Nash equilibrium (2004)
Ryan Porter, Eugene Nudelman, Yoav Shoham
We present two simple search methods for computing a sample Nash equilibrium in a normal-form game: one for 2player games and one for n-player games. We test these algorithms on many classes of...
Ryan Porter, Yoav Shoham, Moshe Tennenholtz
We introduce a new mechanism-design problem called fair imposition. In this setting a center wishes to fairly allocate tasks among a set of agents whose cost structures are known only to them, and...
Control Coordination of Multiple Agents Through Decision Theoretic and Economic Methods (2003)
The control and coordination of multi-agent systems is a major scientific and technological challenge. When facing large-scale multi-agent settings where the agents are to act in flexible, hostile...
Towards a General Theory of Non-Cooperative Computation (2003)
Robert Mcgrew, 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...
A portfolio approach to algorithm selection (2003)
Kevin Leyton-brown, Eugene Nudelman, Galen Andrew, Jim Mcfadden, Yoav Shoham
Although some algorithms are better than others on average, there is rarely a best algorithm for a given problem. Instead, it is often the case that different algorithms perform well on different
Multi-agent reinforcement learning: a critical survey (2003)
Yoav Shoham, Rob Powers, Trond Grenager
We survey the recent work in AI on multi-agent reinforcement learning (that is, learning in stochastic games). We then argue that, while exciting, this work is flawed. The fundamental flaw is...
Towards a General Theory of Non-Cooperative Computation (2003)
Robert Mcgrew, 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...
On cheating in sealed-bid auctions (2003)
Motivated by the rise of online auctions and their relative lack of security, this paper analyzes two forms of cheating in sealed-bid auctions. The first type of cheating we consider occurs when the...
Multi-Agent Reinforcement Learning: a critical survey (2003)
Yoav Shoham, Rob Powers, Trond Grenager
We survey the recent work in AI on multi-agent reinforcement learning (that is, learning in stochastic games). We then argue that, while exciting, this work is flawed. The fundamental flaw is...
A portfolio approach to algorithm selection (2003)
Kevin Leyton-brown, Eugene Nudelman, Galen Andrew, Jim Mcfadden, Yoav Shoham
Although some algorithms are better than others on average, there is rarely a best algorithm for a given problem. Instead, it is often the case that different algorithms perform well on different...
A portfolio approach to algorithm selection (2003)
Kevin Leyton-brown, Eugene Nudelman, Galen Andrew, Jim Mcfadden, Yoav Shoham
Although some algorithms are better than others on average, there is rarely a best algorithm for a given problem. Instead, it is often the case that different algorithms perform well on different...
Towards a General Theory of Non-Cooperative Computation (2003)
Robert Mcgrew, 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...
Truth Revelation in Approximately Efficient Combinatorial Auctions (2002)
Lehmann, Daniel, O'Callaghan, Liadan Ita, Shoham, Yoav
Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem. This is true of mechanisms for combinatorial auctions, which...
Bidding Clubs in First-Price Auctions (2002)
Leyton-Brown, Kevin, Shoham, Yoav, Tennenholtz, Moshe
We introduce a class of mechanisms, called {\em bidding clubs}, that allow agents to coordinate their bidding in auctions. Bidding clubs invite a set of agents to join, and each invited agent freely...
Mechanism design with execution uncertainty (2002)
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...
Learning the empirical hardness of optimization problems: The case of combinatorial auctions (2002)
Kevin Leyton-brown, Eugene Nudelman, Yoav Shoham
Abstract. We propose a new approach to understanding the algorithm-specific empirical hardness of NP-Hard optimization problems. In this work we focus on the empirical hardness of the winner...
Polynomial-time reinforcement learning of near-optimal policies (2002)
Inspired by recent results on polynomial time reinforcement algorithms that accumulate near-optimal rewards, we look at the related problem of quickly learning near-optimal policies. The new problem...
Dispersion games: general definitions and some specific learning results (2002)
Trond Grenager, Rob Powers, Yoav Shoham
Dispersion games are the generalization of the anticoordination game to arbitrary numbers of agents and actions. In these games agents prefer outcomes in which the agents are maximally dispersed over...
Learning the Empirical Hardness of Optimization Problems: The case of combinatorial auctions (2002)
Kevin Leyton-Brown, Eugene Nudelman, Yoav Shoham
We propose a new approach for understanding the algorithm-specific empirical hardness of problems. In this work we focus on the empirical hardness of the winner determination problem---an...
Dispersion games: general definitions and some specific learning results (2002)
Trond Grenager, Rob Powers, Yoav Shoham
Dispersion games are the generalization of the anticoordination game to arbitrary numbers of agents and actions. In these games agents prefer outcomes in which the agents are maximally dispersed over...
Mechanism Design with Execution Uncertainty (2002)
Ryan Porter Amir, 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.
Bidding clubs in firstprice auctions (2002)
Kevin Leyton-brown, Yoav Shoham, Moshe Tennenholtz
We introduce a class of mechanisms, called bidding clubs, that allow agents to coordinate their bidding in auctions. Bidding clubs invite a set of agents to join, and each invited agent freely...
Yoav Shoham, Moshe Tennenholtz
We introduce a new notion, related to auctions and mechanism design, called fair imposition.
Yoav Shoham, Moshe Tennenholtz
We introduce a new notion, related to auctions and mechanism design, called fair imposition. 1 In this setting a center wishes to fairly and efficiently allocate tasks among a set of agents, not...
On rational computability and communication complexity (2001)
Yoav Shoham, Moshe Tennenholtz
We investigate the power of market mechanisms-- and auctions in particular-- to compute various functions. The specific contributions of this paper are twofold. From the conceptual standpoint, we...
Towards a universal test suite for combinatorial auction algorithms (2000)
Kevin Leyton-brown, Mark Pearson, Yoav Shoham
General combinatorial auctions---auctions in which bidders place unrestricted bids for bundles of goods---are the subject of increasing study. Much of this work has focused on algorithms for finding...
An Algorithm for Multi-Unit Combinatorial Auctions (2000)
Kevin Leyton-Brown, Yoav Shoham, Moshe Tennenholtz
We present a novel algorithm for computing the optimal winning bids in a combinatorial auction (CA), that is, an auction in which bidders bid for bundles of goods. All previously published algorithms...
Towards a Universal Test Suite for Combinatorial Auction Algorithms (2000)
Kevin Leyton-Brown, Mark Pearson, Yoav Shoham
General combinatorial auctions -- auctions in which bidders place unrestricted bids for bundles of goods -- are the subject of increasing study. Much of this work has focused on algorithms for...
Bidding clubs: Institutionalized collusion in auctions (2000)
Yoav Shoham, Moshe Tennenholtz
�Ò�ÔÖ�×Ö����Û�Ý��Ò��Ò×ÓÑ��×�×�ÖØ��ÒÑÓÒ�Ø�ÖÝ...
An algorithm for multi-unit combinatorial auctions (2000)
Kevin Leyton-brown, Yoav Shoham, Moshe Tennenholtz
We present a novel algorithm for computing the optimal winning bids in a combinatorial auction (CA), that is, an auction in which bidders bid for bundles of goods. All previously published algorithms...
Yuzo Fujishima, Kevin Leyton-brown, Yoav Shoham
In combinatorial auctions, multiple goods are sold simultaneously and bidders may bid for arbitrary combinations of goods. Determining the outcome of such an auction is an optimization problem that...
Truth revelation in rapid, approximately efficient combinatorial auctions (1999)
Daniel Lehmann, Liadan Ita O'callaghan, Yoav Shoham
Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem. This is true of mechanisms for combinatorial auctions, which...
What Can a Market Compute, and At What Expense? (1999)
Yoav Shoham, Moshe Tennenholtz
We investigate the power of market mechanisms -- and auctions in particular -- to compute various functions. The specific contributions of this paper are twofold. From the conceptual standpoint, we...
From Belief Revision to Belief Fusion (1999)
Pedrito Maynard-Reid, Yoav Shoham
We introduce a new operator|belief fusion|which is a generalization of the classical AGM revision operator to the multi-agent case. In the process we dene pedigreed belief states, which enrich...
Yuzo Fujishima, Kevin Leyton-brown, Yoav Shoham
In combinatorial auctions, multiple goods are sold simultaneously and bidders may bid for arbitrary combinations of goods. Determining the outcome of such an auction is an optimization problem that...
Speeding up ascending-bid auctions (1999)
Yuzo Fujishima, David Mcadams, Yoav Shoham
In recent years auctions have grown in interest within the AI community as innovative mechanisms for resource allocation. The primary contribution of this paper is to identify a family of hybrid...
Intelligent Real-Time Problem Solving: Conceptual Analysis of Issues, Ideas and Results. (1998)
Shoham, Yoav, Hayes-Roth, Barbara
Our final report consists of four parts. The first two address the issues as defined by the Air Force in the call for proposals, and as discussed in the kickoff meeting. In the first document,...
Nonmonotonic Temporal Reasoning. (1998)
In research carried out to this date under this grant they investigated a number of issues, semantical and algorithmic, in the design of agents in a multi-agent environment. The issues that were...
Intelligent Real-time Problem Solving. (1998)
The researchers proposed to develop and test a framework for designing and analyzing complex control systems consisting of independent modules, called agents, that communicate through fixed channels....
Designing Efficient Multi-Agent Systems. (1998)
The research carried out during 1994 under this grant expands our previous work on two central design issues in multi-agent systems and begins to develop two new tools for multi-agent systems. As...
Representation and Computation With Decision - and Game - Theoretic Agents (1998)
This project aimed at working towards a theory of representation and computation in decision and game-theoretic models. In many domains, such as the ones faced by the military, or in e-commerce, task...
On the Knowledge Requirements of Tasks (1998)
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...
On the Knowledge Requirements of Tasks (1998)
Ronen 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...
On the Knowledge Requirements of Tasks (1998)
Ronen Brafman, Joseph Y. Halpern, Yoav Shoham
Sensors In [Erd94], Erdmann argues that the role of sensors is to provide sufficient information to choose "good" actions, and that they should be constructed to fulfill this task. An...
Agent oriented programming was proposed as a high-level programming language, in which a programmer is given the opportunity to communicate with other programs in a uniform, high-level language....
Motivated largely by tasks that require control of complex processes in a dynamic environment, we introduce a new computational construct called a protogram. A protogram is a program specifying an...
Co-Learning and the Evolution of Social Activity, (1997)
Shoham, Yoav, Tennenholtz, Moshe
We introduce the notion of co-learning, which refers to a process in which several agents simultaneously try to adapt to one another's behavior so as to produce desirable global system properties. Of...
Lavignon, Jean-Francois, Shoham, Yoav
We present a new model of machines and their operation, called temporal automata. Characteristics of this model include explicit representation of process time, symmetric representation of a machine...
Fab: Content-based, collaborative recommendation (1997)
Marko Balabanovic, Yoav Shoham
Fab is a recommendation system designed to help users sift through the enormous amount of information available in the World Wide Web. Operational since Dec. 1994, this system combines the...
Content-based, collaborative recommendation (1997)
Marko Balabanović, Yoav Shoham
By combining both collaborative and content-based filtering systems, Fab may eliminate many of the weaknesses found in each approach. ONLINE READERS ARE IN NEED OF TOOLS TO HELP THEM COPE with the...
On the emergence of social conventions: modeling, analysis, and simulations (1997)
Yoav Shoham, Moshe Tennenholtz
We define the notion of social conventions in a standard gametheoretic framework, and identify various criteria of consistency of such conventions with the principle of individual rationality. We...
Qualitative reasoning about perception and belief (1997)
We present a qualitative model for reasoning about perceptions, sensors, and belief, and a logic to reason about this model. Basic to our model is a distinction between precision and accuracy, for...
Some Recent Ideas on Utility (1997)
This note is a glueing together of two recent conference papers of mine, one from UAI-97 [8] and from IJCAI-97 [7], with minimal additional editing or quality control on the glueing process. Since...
On the Emergence of Social Conventions: modeling, analysis, and simulations (1997)
Yoav Shoham, Moshe Tennenholtz
We define the notion of social conventions in a standard gametheoretic framework, and identify various criteria of consistency of such conventions with the principle of individual rationality. We...
Qualitative Reasoning about Perception and Belief (1997)
Alvaro Del, Alvaro Del Val, Yoav Shoham
We present a qualitative model for reasoning about perceptions, sensors, and belief, and a logic to reason about this model. Basic to our model is a distinction between precision and accuracy, for...
Combining Content-Based and Collaborative Recommendation (1997)
Marko Balabanovic, Yoav Shoham
this paper we describe the two approaches of content-based and collaborative recommendation, explain how a hybrid system can be created and then describe Fab, an implementation of such a system. We...
Qualitative Reasoning about Perception and Belief (1997)
Alvaro Del Val, Pedrito Maynard-Reid, Yoav Shoham
We present a qualitative model for reasoning about perceptions, sensors, and belief, and a logic to reason about this model. Basic to our model is a distinction between precision and accuracy, for...
Strategic directions for artificial intelligence (1996)
Jon Doyle, Thomas Dean, Et Al, Thomas Dean (co, Johan De Kleer, Thomas Dietterich, ...
The field of artificial intelligence (AI) consists of long-standing intellectual and technological efforts addressing several interrelated scientific and practical aims: —constructing intelligent...
A Propositional Modal Logic of Time Intervals (1996)
Joseph Y. Halpern, Yoav Shoham
: In certain areas of artificial intelligence there is need to represent continuous change and to make statements that are interpreted with respect to time intervals rather than time points. To this...
Nonmonotonic Temporal reasoning (1995)
Both nonmonotonic reasoning and temporal reasoning are rich and multifaceted subjects, with relevance to many areas of artificial intelligence. The Handbook deals with each in detail, but, with the...
Learning Information Retrieval Agents: Experiments with Automated Web Browsing (1995)
Marko Balabanovic, Yoav Shoham
The current exponential growth of the Internet precipitates a need for new tools to help people cope with the volume of information. To complement recent work on creating searchable indexes of the...
On Social Laws for Artificial Agent Societies: Off-Line Design (1995)
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...
An Adaptive Agent for Automated Web Browsing (1995)
Marko Balabanovic, Yoav Shoham, Yeogirl Yun
The current exponential growth of the Internet precipitates a need for new tools to help people cope with the volume of information. To complement recent work on creating searchable indexes of the...
Adaptive Load Balancing: A Study in Multi-Agent Learning (1995)
Andrea Schaerf, Yoav Shoham, Moshe Tennenholtz
We study the process of multi-agent reinforcement learning in the context of load balancing in a distributed system, without use of either central coordination or explicit communication. We first...
Wrappers For Performance Enhancement And Oblivious Decision Graphs (1995)
Ron Kohavi, Yoav Shoham, Jerry Friedman, Nils Nilsson
In this doctoral dissertation, we study three basic problems in machine learning and two new hypothesis spaces with corresponding learning algorithms. The problems we investigate are: accuracy...
Knowledge Considerations in Robotics and Distribution of Robotic Tasks (1995)
We develop a formal tool for representing and analyzing informational aspects of robotic tasks, based on the formal concept of `knowledge. ' Specifically, we adopt the notion of knowledge-based...
Adaptive load balancing: A study in multi-agent learning (1995)
Andrea Schaerf, Yoav Shoham, Moshe Tennenholtz
We study the process of multi-agent reinforcement learning in the context of load balancing in a distributed system, without use of either central coordination or explicit communication. We rst de ne...
Knowledge as a Tool in Motion Planning under Uncertainty (1994)
Ronen 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 about distributed protocols, we aim for a similarly powerful and high-level...
Logics of Mental Attitudes in AI (1994)
. There has been a growing interest in AI in formal, qualitative models of various mental attitudes, starting with the well-researched concepts of knowledge and belief, and continuing with more...
Deriving Properties of Belief Update from Theories of Action (1994)
We present an approach to database update as a form of non monotonic temporal reasoning, the main idea of which is the (circumscriptive) minimization of changes with respect to a set of facts...
A Unified View of Belief Revision and Update (1994)
Alvaro Del, Alvaro Del Val, Yoav Shoham
Belief revision and belief update have been considered as two distinct types of belief modification. In this paper, we show that both can be captured within an unified formalism, in which revision is...
A Unified View of Belief Revision and Update (1994)
Belief revision and belief update have been considered as two distinct types of belief modification. In this paper, we show that both can be captured within an unified formalism, in which revision is...
A Unified View of Belief Revision and Update (1994)
Belief revision and belief update have been considered as two distinct types of belief modification. In this paper, we show that both can be captured within a unified formalism, in which revision is...
Co-Learning and the Evolution of Social Activity (1993)
Yoav Shoham, Moshe Tennenholtz
We introduce the notion of co-learning, which refers to a process in which several agents simultaneously try to adapt to one another's behavior so as to produce desirable global system...
Co-Learning and the Evolution of Social Activity (1993)
Yoav Shoham And, Yoav Shoham, Moshe Tennenholtz
We introduce the notion of co-learning, which refers to a process in which several agents simultaneously try to adapt to one another's behavior so as to produce desirable global system...
Deriving Properties of Belief Update from Theories of Action (II) (1993)
In [ del Val and Shoham, 1992 ] we showed that the postulates for belief update recently proposed by Katsuno and Mendelzon [ 1991 ] can be analytically derived using the formal theory of action...
Towards Knowledge-Level Analysis of Motion Planning (1993)
Ronen I. Brafman, Jean-claude Latombe, Yoav Shoham
Inspired by the success of the distributed computing community in applying logics of knowledge and time to reasoning about distributed protocols, we aim for a similarly powerful and high-level...
A symbolic generalization of probability theory (1992)
Adnan Y. Darwiche, Matthew L. Ginsberg, Yoav Shoham, Ross Shachter
ii I certify that I have read this thesis and that in my opinion it is fully adequate, in scope and in quality, as a dissertation for the degree of Doctor of Philosophy.
Deriving Properties of Belief Update from Theories of Action (1992)
Alvaro Del, Alvaro Del Val, Yoav Shoham
. We present an approach to database update as a form of non monotonic temporal reasoning, the main idea of which is the (circumscriptive) minimization of changes with respect to a set of facts...
Deriving Properties of Belief Update from Theories of Action (1992)
Two areas that have attracted much interest in recent years, belief update and reasoning about action, have so far been largely disjoint. Indeed, at first glance there appears to be little connection...
Elsevier ARTINT 931 Agent-oriented programming (1991)
Shoham, Y., Agent-oriented programming, Artificial Intelligence 60 (1993) 51-92. A new computational framework is presented, called agent-oriented programming (AOP), which can be viewed as a...
A Logic of Relative Desire (1991)
Jon Doyle, Yoav Shoham, Michael P. Wellman
: Although many have proposed formal characterizations of belief structures as bases for rational action, the problem of characterizing rational desires has attracted little attention. AI relies...
A Logic for Perception and Belief (1991)
We present a modal logic for reasoning about perception and belief, captured respectively by the operators P and B. The B operator is the standard belief operator used in recent years, and the P...
Provably Correct Theories of Action (1991)
We investigate logical formalization of the effects of actions in the situation calculus. We propose a formal criterion against which to evaluate theories of deterministic actions. We show how the...
A Logic of Relative Desire (1991)
Preliminary Report, Jon Doyle, Yoav Shoham, Michael P. Wellman
: Although many have proposed formal characterizations of belief structures as bases for rational action, the problem of characterizing rational desires has attracted little attention. AI relies...
Nonmonotonic reasoning and causation (1990)
It is suggested that taking into account considerations that traditionally fall within the scope of computer science in general. and artificial intelligence in particular, sheds new light on the...
Epistemic semantics for fixed-point non-monotonic logics (1990)
Default Logic and Autoepistemic Logic are the two best-known fixed-points non-monotonic logics. Despite the fact that they are known to be closely related and that the epistemic nature of...
Peter Cramton, Yoav Shoham, Richard Steinberg
A comprehensive book on combinatorial auctions?auctions in which bidders can bid on packages of items. The book consists of original material intended for researchers, students, and practitioners of...
Simple search methods for finding a Nash equilibrium
Porter, Ryan, Nudelman, Eugene, Shoham, Yoav
We present two simple search methods for computing a sample Nash equilibrium in a normal-form game: one for 2-player games and one for n-player games. Both algorithms bias the search towards supports...
Bidding Clubs: Institutionalized Collusion in Auctions
Kevin Leyton-Brown, Yoav Shoham, Moshe Tennenholtz
We introduce a class of mechanisms, called bidding clubs, for agents to coordinate their bidding in auctions. In a bidding club agents rst conduct a \pre-auction" internally within the club;...
Applications of a Logic of Knowledge to Motion Planning under 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 about distributed protocols, we aim for a similarly powerful and high-level...
Understanding Random SAT: Beyond the Clauses-to-Variables Ratio
Eugene Nudelman, Alex Devkar, Yoav Shoham, Kevin Leyton-Brown
It is well known that the ratio of the number of clauses to the number of variables in a random k-SAT instance is highly correlated with the instance's empirical hardness. We consider the...
Bidding Clubs: Institutionalized Collusion in Auctions
Kevin Leyton-Brown, Yoav Shoham, Moshe Tennenholtz
We introduce a class of mechanisms, called bidding clubs, for agents to coordinate their bidding in auctions. In a bidding club agents first conduct a "pre-auction" within the club;...
An Overview of Combinatorial Auctions
Peter Cramton, Yoav Shoham, Richard Steinberg
An auction is combinatorial when bidders can place bids on combinations of items, called “packages,” rather than just individual items. Computer scientists are interested in combinatorial...
Peter Cramton, Yoav Shoham, Richard Steinberg
The study of combinatorial auctions -- auctions in which bidders can bid on combinations of items or "packages" -- draws on the disciplines of economics, operations research, and computer science....