Selected Papers

Books

Multiagent Systems:

Algorithmic, Game Theoretic

and Logical Foundations

Essentials of Game Theory:

A Concise, Multidisciplinary Introduction

Combinatorial Auctions

Artificial Intelligence Techniques

in Prolog

Reasoning about Change:

Time and Causation from the Standpoint of Artificial Intelligence

Y. Shoham and K. Leyton-Brown

Cambridge University Press, 2009

K. Leyton-Brown and Y. Shoham

Morgan Claypool Publishers, 2008

P. Cramton, Y. Shoham,

and R. Steinberg (editors)

MIT Press, 2006

Y. Shoham

Morgan Kaufman Publishers, 1994

Y. Shoham

MIT Press, 1988

book home page: click on cover...

(that was before the Web)

((that was before computers))

Articles

2009

Logical Theories of Intention and the Database Perspective. Y. Shoham. J. Philosophical Logic 38(6): 633-648, December 2009. [PDF]
Analysis of a Winning Computational Billiards Player. C. Archibald, A. Altman and Y. Shoham. Proceedings of IJCAI-09. [PDF]
Eliciting Truthful Answers to Multiple-Choice Questions. N. Lambert and Y. Shoham. Proceedings of EC-09. [PDF]
On the Complexity of Schedule Control Problems for Knockout Tournaments. T. Vu, A. Altman and Y. Shoham. Proceedings of AAMAS-09. [PDF]
Team Competition. P. Tang, Y. Shoham and F. Lin. Proceedings of AAMAS-09. [PDF]
Empirical Hardness Models: Methodology and a Case Study on Combinatorial Auctions. K. Leyton-Brown, E. Nudelman and Y. Shoham. Journal of the ACM, 56(4): 1-52, 2009. [PDF]
Modeling Billiards Games. C. Archibald and Y. Shoham. Proceedings of AAMAS-09. [PDF]
A Framework for the Quantitative Evaluation of Voting Rules. M. Munie, P. Tang and Y. Shoham. Proceedings of LGS6. [PDF]
Ranking Games. F. Brandt, F. Fischer, P. Harrenstein and Y. Shoham. Journal of Artificial Intelligence, 173(2): 221-239, 2009. [PDF]
Can Computers Think? Can they Feel? Y. Shoham. Non-technical. Stanford School of Engineering "Ask the Expert" column. [PDF].

2008

Simple Search Methods for Finding a Nash Equilibrium. R. W. Porter, E. Nudelman and Y. Shoham. Games and Economic Behavior, 63(2): 642-662. [PDF]
Bayesian Coalitional Games. S. Ieong and Y. Shoham. Proceedings of AAAI-08. [PDF]
Optimal Testing of Structured Knowledge. M. Munie and Y. Shoham. Proceedings of AAAI-08. [PDF]
Eliciting Properties of Probability Distributions. N. Lambert, D. M. Pennock and Y. Shoham. Proceedings of EC-08. [PDF]
Eliciting Properties of Probability Distributions: the Highlights. N. Lambert, D. M. Pennock and Y. Shoham. SIGEcom Exchange, November 2008. A summary of the results in the above paper. t [PDF]
Self-Financed Wagering Mechanisms for Forecasting. N. Lambert, J. Langford, J. Wortman, Y. Chen, D. Reeves, Y. Shoham and D. M. Pennock. Proceedings of EC-08. [PDF]
Game Theory Pragmatics: A Challenge for AI. Y. Shoham. Proceedings of AAAI-08. A subset of the next paper.
Computer Science and Game Theory. Y. Shoham. Communications of the ACM, 51(5), August, 2008. [PDF]
Fault Tolerant Mechanism Design. R. Porter, A. Ronen, Y. Shoham and M. Tennenholtz, Artificial Intelligence, 172(15), 1783-1799, 2008. [PDF]
Truthful Surveys. N. Lambert and Y. Shoham. In Proceedings of WINE-08. [PDF]
On the Agenda Control Problem in Knockout Tournaments. T. Vu, A. Altman and Y. Shoham. In Proceedings of COMSOC-08. Superseded by paper above.

2007

If Multi-Agent Learning is the Answer, What is the Question? Y. Shoham, R. Powers and T. Grenager. Artificial Intelligence 171(7), pages 365-377, special issue on Foundations of Multi-Agent Learning (R. Vohra and M. Wellman, eds.). [PDF].
A general criterion and an algorithmic framework for learning in multi-agent systems. R. Powers, Y. Shoham and T. Vu. Machine Learning 67, pages 45-76. [PDF]
Near-Optimal Search in Continuous Domains. S. Ieong, N. Lambert, Y. Shoham and R. Brafman. Proceedings of AAAI-07. [PDF]
Asymptotically Optimal Repeated Auctions for Sponsored Search. N. Lambert and Y. Shoham. Proceedings of ICEC-07. [PDF]
A Game-Theoretic Analysis of Strictly Competitive Multiagent Scenarios. F. Brandt, F. Fischer, P. Harrenstein, and Y. Shoham. Proceedings of IJCAI-07. [PDF]
Spiteful Bidding in Sealed-Bid Auctions. F. Brandt, T. Sandholm, and Y. Shoham. Proceedings of IJCAI'07. Preliminary versions appeared at the 7th IJCAI Workshop on Game Theoretic and Decision Theoretic Agents and the 2005 Dagstuhl Seminar on Computing and Markets. [PDF]

2006

Multi-Attribute Coalitional Games. S. Ieong and Y. Shoham. Proceedings of EC'06.
Learning in Games with More than Two Players. T. Vu, R. Powers and Y. Shoham. Proceedings of the AAMAS-06.[PDF]
On strictly competitive multi-player games. F. Brandt, F. Fischer, and Y. Shoham. In Proceedings AAAI 2006, pages 605-612. Also appeared at the 17th International Conference on Game Theory (Stony Brook). [PDF]
A Test Suite for Combinatorial Auctions. K. Leyton-Brown and Y. Shoham. Chapter 19 of Combinatorial Auctions. [PDF]
Empirical Hardness Models for Combinatorial Auctions. K. Leyton-Brown, E. Nudelman and Y. Shoham. Chapter 20 of Combinatorial Auctions. [PDF]

2005

Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games. S. Ieong and Y. Shoham. Proceedings of EC'05. [PDF]
Fast and Compact: A Simple Class of Congestion Games. S. Ieong, R. McGrew, E. Nudelman, Y. Shoham, and Q. Sun. AAAI-2005. [PDF]
Learning Against Opponents with Bounded Memory. R. Powers and Y. Shoham. Proceedings of IJCAI 2005. [PDF]
Non-Cooperative Computing: Boolean Functions with Correctness and Exclusivity. Y. Shoham and M. Tennenholtz. Journal of Theoretical Computer Science, 343, 97-113. [PDF]
Introduction to Combinatorial Auctions. P. Cramton, Y. Shoham and R. Steinberg [PDF]. Introductory chapter of Combinatorial Auctions.

2004

New Criteria and a New Algorithm for Learning in Multi-Agent Systems. R. Powers and Y. Shoham. Proceedings of NIPS-2004/5. [PDF]
Understanding Random SAT: Beyond the Clauses-to-Variables Ratio. E. Nudelman, K. Leyton-Brown, A. Devkar, H. Hoos and Y. Shoham. Proceedings of CP-2004. [PDF]
SATzilla: An Algorithm Portfolio for SAT. E. Nudelman, A. Devkar, Y. Shoham, K. Leyton-Brown and H. Hoos. In conjunction with SAT 2004. [PDF]
Run the GAMUT: A Comprehensive Approach to Evaluating Game-Theoretic Algorithms. K. Leyton-Brown, E. Nudelman, J. Wortman and Y. Shoham. Proceedings of AAMAS-04. [PDF | website]
Simple Search Methods for Finding a Nash Equilibrium. R. W. Porter, E. Nudelman and Y. Shoham. Proceedings of AAAI-04. Superseded by journal version above.
Using Contracts to Influence the Outcome of a Game. R. McGrew and Y. Shoham. Proceedings of AAAI-04. [PDF]
Fair Imposition. R. Porter, Y. Shoham and M. Tennenholtz. Journal of Economic Theory, 118(2), October 2004, Pages 209-228. [PDF] (a shorter version appeared in IJCAI'01)
Addressing the Free-Rider Problem in File-Sharing Systems: A Mechanism-Design Approach. R. Porter and Y. Shoham. Long version [PDF]. Short version in proceedings of EC'04, New York, 2004.
On Cheating in Sealed-Bid Auctions. R. W. Porter and Y. Shoham. Journal of Decision Support Systems, 39, 41-54. [PDF] (A short version appeared in EC'03)

2003

On Cheating in Sealed-Bid Auctions. R. Porter and Y. Shoham. Proceedings of EC'03, San Diego, 2003; superseded by 2004 journal version above.
Towards a General Theory of Non-Cooperative Computing. R. McGrew, R. Porter and Y. Shoham. Proceedings of TARK IX, Bloomington, 2003. [PDF]
Boosting as a Metaphor for Algorithm Design. K. Leyton-Brown, E. Nudelman, G. Andrew, J. McFadden, and Y. Shoham [PDF]. Working paper.
Parts of this paper appeared as:
- Boosting as a Metaphor for Algorithm Design. Constraint Programming 2003. [PDF ]
- A Portfolio Approach to Algorithm Selection. IJCAI 2003. [PDF ]

2002

Truth Revelation in Approximately Efficient Combinatorial Auctions. D. Lehmann, L. I. O'Callaghan, Y. Shoham. Journal of the ACM , 49 (5), September 2002, 577-602. [PDF]
Learning the Empirical Hardness of Optimization Problems: the case of combinatorial auctions. K. Leyton-Brown, E. Nudelman, Y. Shoham (thanks also to Yannis Vetsikas, Ramon Bejar, Carla Gomes, Bart Selman). In Constraint Programming (2002). [PS | PDF | Slides]
Mechanism Design with Execution Uncertainty. R. Porter, A. Ronen, Y. Shoham, M. Tennenholtz. UAI-02. Superseded by the 2008 journal paper.
Dispersion Games. T. Grenager, R. Powers and Y. Shoham. AAAI-02. [PS | PDF]
Bidding Clubs in First-Price Auctions. K. Leyton-Brown, Y. Shoham, M. Tennenholtz. Extended abstract: AAAI-02. Full version: working paper. Full version: [PS | PDF] Extended abstract: [PS | PDF]
Polynomial-Time Reinforcement Learning of Near-Optimal Policies. K. Pivazyan, Y. Shoham. AAAI-02. [PS]
Searle and the Art of Motorcycle Maintenance. Y. Shoham. Unpublished. [PDF]

2001

Smoothing Out Focused Demand for Network Resources: K. Leyton-Brown, R. Porter, S. Venkataraman, B. Prabhakar. Short version presented at the 2001 ACM Conference on Electronic Commerce (EC'01); also presented at ITCom 2001. Full version to be published in ACM Computer Communications Review, 2002. Full version: [PS | PDF] Short version: [PS | PDF]
Fair Imposition. Y. Shoham, M. Tennenholtz. IJCAI-01, 2001. Superseded by 2004 journal version above.
Rational Computation and the Communication Complexity of Auctions. Y. Shoham and M. Tennenholtz, Games and Economic Behavior, Vol. 35, 2001 [PS]

2000

Bidding Clubs: Institutionalized Collusion in Auctions. K. Leyton-Brown, M. Tennenholtz, Y. Shoham, Proceedings of EC'00, Minneapolis, 2000. [PS | PDF]
Towards a Universal Test Suite for Combinatorial Auctions. K. Leyton-Brown, M. Pearson, Y. Shoham, Proceedings of EC'00, Minneapolis, 2000. [PS | PDF]
An Algorithm for Multi-Unit Combinatorial Auctions. K. Leyton-Brown, M. Tennenholtz, Y. Shoham, Proceedings of AAAI-2000, Austin, 2000. [PS | PDF]

1999

Speeding Up Ascending-Bid Auctions. Y. Fujishima, D. McAdams, and Y. Shoham, Proceedings of IJCAI-99, Stockholm, 1999.
Expected Utility Networks. P. La Mura and Y. Shoham, Conference on Uncertainty in Artificial Intelligence, Stockholm, 1999.
Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches. Y. Fujishima, K. Leyton-Brown and Y. Shoham, Proceedings of IJCAI-99, Stockholm, 1999. [PS | PDF]
Rational Programming. Y. Shoham. Unpublished. [PDF]

1998

Agent Oriented Programming. Y. Shoham, in reading in Agents, M.N. Huhns and M.P. Singh (ed.), Morgan-Kaufmann, 1998.
Conditional, Hierarchical Multi-Agent Preferences. P. La Mura and Y. Shoham, Proceedings of TARK VII, Evanston, IL, 1998.
From Belief Revision to Belief Fusion. P. Maynard-Reid II and Y. Shoham, Proceedings of LOFT-98, Torino, 1998.
On the Knowledge Requirements of Tasks. R.I. Brafman, J.Y. Halpern and Y. Shoham, Journal of Artificial Intelligence 98(1-2), pp.317-350, January 1998.

1997

Economic Principles on Multi-Agent Systems (ed.). C.Boutilier, Y. Shoham and M.P. Wellman, Journal of Artificial Intelligence 94(1-2), pp. 1-6, July 1997.
On the Emergence of Social Conventions: modeling, analysis, and simulations. Y. Shoham and M. Tennenholtz, Journal of Artificial Intelligence 94(1-2), pp. 139-166, July 1997.
Fab: Content-based, Collaborative Recommendation. M. Balabanovic and Y. Shoham, Communications of the ACM 40(3), March 1997.
A Dynamic Theory of Incentives in Multi-Agent Systems (Preliminary Report). Y. Shoham and K. Tanaka, Proceedings of IJCAI-97, Nagoya, 1997.
Qualitative Reasoning about Perception and Belief. A. Del Val, Y. Shoham and P. Maynard-Reid II, Proceedings of IJCAI-97, Nagoya, 1997.
A Symmetric View of Probabilities and Utilities. Y. Shoham, Proceedings of IJCAI-97, Nagoya, 1997.
Two Senses of Conditional Utility. Y. Shoham, Proceedings of Thirteenth Conference of Uncertainty in Artificial Intelligence, Providence, 1997.
Agent Oriented Programming: a survey. Y. Shoham, in Software Agents, J.M. Bradshaw (ed.), MIT Press, 1997.

1996

Logics of Knowledge and Robot Motion Planning. R. Brafman, J-C. Latombe, Y. Moses and Y. Shoham, Journal of the ACM, 1996.

1995

Adaptive Load Balancing: a study of multi-agent learning. A. Schaerf, Y. Shoham and M. Tennenholtz, Journal of Artificial Intelligence Research 2, pp. 475-500, 1995.
On Social Laws for Artificial Agent Societies: offline design. Y. Shoham and M. Tennenholtz, Journal of Artificial Intelligence 73(1-2), 1995.
Knowledge Considerations in Robotics and Distribution of Robotic Tasks. R. Brafman and Y. Shoham, Proceedings of IJCAI-95, Montreal, 1995.
Nonmonotonic Temporal Reasoning. E.J. Sandwall and Y. Shoham, in the Handbook of Login in Artificial Intelligence and Logic Programming (D. Gabbai, ed.), Elsevier, 1995.

1994

A Unified View of Belief Revision and Update. A. Del Val and Y. Shoham, Journal of Logic and Computation, 1994.
Deriving Properties of Belief Update from Theories of Action. A. Del Val and Y. Shoham, Journal of Logic, Language and Information, 1994.
Belief as Defeasible Knowledge. Y. Moses and Y. Shoham, Journal of Artificial Intelligence, 1994.
Applying Knowledge to Motion Planning Under Uncertainty. R.I. Brafman, J-C. Latombe, Y. Moses and Y. Shoham, Proceedings of TARK-V, 1994.
Logics of Mental Attitudes in AI. Y. Shoham and S.B. Cousins, in G. Lakemeyer and B. Mebel (eds.), Advances in Knowledge Representation and Reasoning, Springer-Verlag, 1994.

1993

Agent Oriented Programming. Y. Shoham, Journal of Artificial Intelligence 60 (1), pp. 51-92, 1993. [PDF]
Reasoning Precisely with Vague Concepts. N. Goyal and Y. Shoham, Proceedings of AAAI, Washington, 1993.
Towards Knowledge-Level Analysis of Motion Planning. R.I. Brafman, J-C. Latombe, and Y. Shoham, Proceedings of AAAI, Washington, 1993.
Deriving Properties of Belief Update from Theories of Action II. A. Del Val and Y. Shoham, Proceedings of IJCAI, Chambery, France, 1993.
Agent Oriented Programming. Y. Shoham and B. Thomas, in The Encyclopedia of Computer Science and Technology, A. Kent and J.G. Williams (eds.), Marcel Dekkar, Inc. 1993.

1992

A Logic of Knowledge and Justified Assumptions. F. Lin and Y. Shoham, Journal of Artificial Intelligence 57(2-3), pp. 271-290, 1992.
Emergent Conventions in Multi-Agent Systems. Y. Shoham and M. Tennenholtz, Proceedings of KR, Boston, 1992.
Deriving Properties of Belief Update from Theories of Action. A Del Val and Y. Shoham, Proceedings of AAAI, San Jose, 1992.
Concurrent Actions in the Situation Calculus. F. Lin and Y. Shoham, Proceedings of AAAI, San Jose, 1992.
On the Synthesis of Useful Social Laws. Y. Shoham and M. Tennenholtz, Proceedings of AAAI, San Jose, 1992.
Protograms (abstract only). E. Moses and Y. Shoham, First International Conference on Planning, 1992.
On Traffic Laws for Mobile Robots (abstract only). Y. Shoham and M. Tennenholtz, First International Conference on Planning, 1992.
A Mechanism for Reasoning about Time and Belief. H. Isozaki and Y. Shoham, Proceedings of International Conference on Fifth Generation Computer Systems, Japan, 1992.
Agent Oriented Programming: an overview and summary of recent research. Y. Shoham, Proceedings of Workshop on Distributed Artificial Intelligence, 1992.

1991

Preliminary Thoughts on an Agent Description Language. B. Thomas, A. Schwartz, S. Kraus and Y. Shoham, International Journal of Intelligent Systems 6(5), 1991.
A Propositional Modal Logic of Time Intervals. J.Y. Halpern and Y. Shoham, Journal of the ACM 38(4), pp. 935-962, 1991.
Remarks on Simon's Comments. Y. Shoham, Journal of Cognitive Science, 15(2), pp. 301-303, 1991.
AGENTO: a simple agent language and its interpreter. Y. Shoham, Proceedings of AAAI, Anaheim, 1991.
Provably Correct Theories of Action. F. Lin and Y. Shoham, Proceedings of AAAI, Anaheim, 1991.
Implementing the Intentional Stance. Y. Shoham, in Philosophy and Artificial Intelligence (R. Cummins and J. Pollock, eds.), MIT Press, 1991.

1990

Nonmonotonic Temporal Reasoning and Causation. Y. Shoham, Journal of Cognitive Science 14(2), pp. 213-252, 1990.
On the Complexity of Inheritance Networks and Roles. A. Hemerely, R. Guerreiro and Y. Shoham, Proceedings of AAAI, Boston, 1990.
Epistemic Semantics for Fixpoint Nonmonotonic Logics. F. Lin and Y. Shoham, Proceedings of TARK III, Monterey, 1990.

1989

Belief as Defeasible Knowledge. Y. Shoham and Y. Moses, Proceedings of the 11th IJCAI, 1168-1173, Detroit, 1989.
Time for Action. Y. Shoham, Proceedings of the 11th IJCAI, 333-342, Detroit, 1989.

1988

Efficient Reasoning about Rich Temporal Domains. Y. Shoham, Journal of Philosophical Logic 17(4), pp. 443-474, (invited article), 1988.
Chronological Ignorance: Experiments in Nonmonotonic Temporal Reasoning. Y. Shoham, Journal of Artificial Intelligence 36(3), pp. 279-331, 1988.
Problems in Nonmonotonic Temporal Reasoning. Y. Shoham and D. McDermott, Journal of Artificial Intelligence 36(1), pp. 49-61, 1988.
Temporal Reasoning in AI. Y. Shoham and N. Goyal, in Exploring Artificial Intelligence, pp.419-438, Morgan-Kaufmann, 1988.

1987

Temporal Logics in AI. Y. Shoham, Journal of Artificial Intelligence 33(1), pp. 89-104, 1987.
A Semantical Approach to Nonmonotonic Logics. Y. Shoham, Proceedings of 2nd Symposium on Logic in Computer Science, 275-279, Ithaca, N.Y., 1987.
Nonmonotonic Logics: meaning and utility. Y. Shoham, Proceedings of 10th IJCAI, 388-393, Milan, 1987.
Chronological Ignorance: time, knowledge, nonmonotonicity, and casual theories. Y. Shoham, in M. Ginsberg (ed.), Readings in Nonmonotonic Reasoning, pp.396-409, Morgan-Kaufmann, 1987.
Temporal Reasoning. Y. Shoham and D.V. McDermott, in The Encyclopedia of Artificial Intelligence, Shapiro, S.C. (ed.), pp.967-981, Wiley-Interscience, New York, 1987.

1986

Chronological Ignorance: time, knowledge, nonmonotonicity and casual theories. Y. Shoham, Proceedings of the AAAI, 389-393, Philadelphia, PA, 1986.
Reified Temporal Logics: semantical and ontological considerations. Y. Shoham, Proceedings of 7th ECAI, 108-123, Brighton, U.K., July 1986 (best paper award).
A Propositional Modal Logic of Time Intervals (short version). J.Y. Halpern and Y. Shoham, Proceedings of 1st Symposium on Logic in Computer Science, 279-292, Boston, MA, June 1986.

1985

Ten Requirements from a Theory of Change. Y. Shoham, Journal of New Generation Computing 3(4), 467-477, special issue on knowledge representation, 1985.
Reasoning about Causation in Knowledge-Based Systems. Y. Shoham, Proceedings of IEEE Conference on Artificial Intelligence Applications, 297-303, Miami, FL, 1985.
Naive Kinematics: One Aspect of Shape. Y. Shoham, Proceedings of 9th IJCAI, 436-442, Los Angeles, CA, 1985.
Temporal Notation and Causal Terminology. Y. Shoham and T. Dean, Proceedings of 7th Annual Conference of the Cognitive Science Society, 90-99, Irvine, CA, 1985.

1984

Prolog Predicates as Denoting Directed Relations. Y. Shoham and D.V. McDermott, Proceedings of FGCS, 307-316, Tokyo, Japan, 1984.
Knowledge Inversion. Y. Shoham and D.V. McDermott, Proceedings of AAAI, 295-329, Austin, TX, 1984.
FAME: A Prolog Program That Solves Problems in Combinatorics. Y. Shoham, Proceedings of 2nd International Logic Programming Conference, 277-288, Uppsala, Sweden, 1984.

last updated on 04/06/2009