Principal Investigators:
Other Participants:
Our Project:
One area of focus is on machine learning approaches for coordination and adaptation,
with application to the TASK project's UAV domain. Examples of the problems we address and our approaches to solve them are as follows.
| |
Problem: Dividing tasks across agents without initial
coordination or communication
Approach: Dispersion Games: a novel class of games in which agents
attempt to disperse across actions to maximize a shared utility functionProblem:
Tracking intelligent, moving targets that can adapt to fixed strategies, in
the face of uncertainty and large problem sizes
Approach: Multiagent reinforcement learning
Problem: Deciding which of several algorithms to use for solving
a time-critical computational problem
Approach: Use machine learning to build a model of each algorithm's
running time
|
For more information, please see our our group webpage, and also our
briefing
from October 2002.
Relevant Papers:
- Boosting as a Metaphor for Algorithm Design. K. Leyton-Brown,
E. Nudelman, G. Andrew, J. McFadden, Y. Shoham. Short version in
Constraint Programming (2003). Full version (working paper) [ PS | PDF]
- Value Lattices for Anytime Optimal Policy Computation in Games. K. Pivazyan and Y.
Shoham. (working paper). [PS]
- Mechanism Design for Online Scheduling. R. Porter. (under review) [PDF]
- Addressing the Free-Rider Problem in File-Sharing Systems: A Mechanism-Design Approach. R. Porter and Y. Shoham. (under review) [PDF]
- Dispersion Games. T. Grenager, R. Powers and Y.
Shoham. AAAI-02. [PS
| 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]
- Mechanism Design with Execution Uncertainty.
R. Porter, A. Ronen, Y. Shoham and M. Tennenholtz. UAI-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]
- On Approximating Optimal Auctions. A. Ronen. In proceedings of
the Third ACM Conference on Electronic Commerce (EC01). [PS
| PDF]
- 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 and IEEE
Computer Communications Workshop 2002. Full version ACM Computer Communications Review, 2002.
Full version: [PS |
PDF]
Short
version: [PS |
PDF]
- Bundling Equilibrium in Combinatorial Auctions. M.
Tennenholtz, R. Holzman, N. Kfir-Dahav, D. Monderer. Working paper, 2001
[PS]
- Incentives for Sharing in Peer-to-Peer Networks: P. Golle,
K. Leyton-Brown, I. Mironov, M. Lillibridge. Short version: 2001 ACM Conference
on Electronic Commerce (EC'01). Full version: WELCOM'01. Full version: [PS |
PDF] Short version: [PS |
PDF]
- Fair Imposition. Y. Shoham, M. Tennenholtz. IJCAI-01,
2001. [PS]
- R-max - A general polynomial time algorithm for near-optimal
reinforcement learning. R. Brafman, M. Tennenholtz. IJCAI-01, 2001.
[PS]
- Rational Competitive Analysis. M. Tennenholtz. IJCAI-01,
2001 [PS]
- Mechanism Design with Incomplete Languages [PS]
- Computationally Feasible VCG Mechanisms, N. Nisan, A. Ronen. [PS]
- Algorithmic Mechanism Design, N. Nisan and A. Ronen. [PS]
- Algorithms for Rational Agents, A. Ronen. [PS]
- Bidding Clubs: Institutionalized Collusion in Auctions: K. Leyton-Brown,
M. Tennenholtz, Y. Shoham, Proceedings of EC'00, Minneapolis, 2000. [PS
| PDF]
- Probabilistic
Models for Agents' Beliefs and Decisions, B. Milch and D. Koller. Proceedings
of the 16th Annual Conference on Uncertainty in AI (UAI), Stanford,
California, June 2000. [Link]
- Towards a Universal Test Suite for Combinatorial Auctions: K. Leyton-Brown,
M. Pearson, Y. Shoham, Proceedings of EC'00, Minneapolis, 2000. [PS |
PDF]
- Rational Computation and the Communication Complexity
of Auctions, Y. Shoham and M. Tennenholtz, 2000.
- An Algorithm for Multi-Unit Combinatorial Auctions: K. Leyton-Brown, M. Tennenholtz,
Y. Shoham, Proceedings of AAAI-2000, Austin, 2000. [PS |
PDF]
- Speeding Up Ascending-Bid Auctions, Y. Fujisima,
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. Fujishjima, K. Leyton-Brown and Y. Shoham,
Proceedings of IJCAI-99, Stockholm, 1999. [PS |
PDF]
- Conditional, Hierarchical Multi-Agent Preferences,
P. La Mura and Y. Shoham, Proceedings of TARK VII,
Evanston, IL, 1998.
- Minmax
equilibria in team games, B. von Stengel and D. Koller. Games and
Economic Behavior, 21, December 1997, pages 309-321. [Link]
- Economic Principles of Multi-Agent Systems (editorial),
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.
- A Dynamic Theory of Incentives in Multi-Agent Systems
(Preliminary Report), Y. Shoham and K. Tanaka, Proceedings
of IJCAI-97, Nagoya, 1997.
- Representations
and Solutions for Game-Theoretic Problems, D. Koller and A.J. Pfeffer. Artificial
Intelligence, 94(1), July 1997, pages 167--215. [Link]
- Finding
mixed strategies with small supports in extensive form games, D. Koller
and N. Megiddo. International Journal of Game Theory, 25:1,
March 1996, pages 73-92. [Link]
- Information
agents: A new challenge for AI, D. Koller and Y. Shoham. IEEE
Expert, June 1996, pages 8-10. [Link]
- Generating
and solving imperfect information games, D. Koller and A.J. Pfeffer. Proceedings
of the 14th International Joint Conference on Artificial Intelligence (IJCAI),
Montreal, Canada, August 1995, pages 1185--1192. [Link]
-
Fast
algorithms for finding randomized strategies in game trees, D. Koller,
N. Megiddo and B. von Stengel. STOC '94. [Link]
- The
complexity of two-person zero-sum games in extensive form, D. Koller and
N. Megiddo. Games and Economic Behavior 4:4, October 1992,
pages 528--552. [Link]
- Emergent Conventions in Multi-Agent Systems, Y.
Shoham and M. Tennenholtz, Proc. KR,
Boston, 1992.
- Efficient
computation of equilibria for extensive two-person games, D. Koller, N.
Megiddo, and B. von Stengel. Games and Economic Behavior, to appear.
[Link]
Modified 12/12/03
