Workshop on Decision Making
in Adversarial Domains

Program

Monday, May 23:

Tuesday, May 24:

Wednesday, May 25:

  

Keynote talks

Monday, May 23:

Algorithm and complexity issues in discrete multistage games

Michael Littman, Rutgers University

    A powerful formulation of the problem of decision making in a multiagent game is that each player attempts to maximize its long-term utility with respect to the behavior of the other players. I will introduce a set of related discrete models, define a solution concept for these models, and survey what is known about algorithmic approaches and the computational complexity of solving the resulting models.

Tuesday, May 24:

Raising the Stakes

Jonathan Schaeffer, University of Alberta

    Poker is a challenging problem for AI research: multiple agents (up to 10), stochastic element (cards being dealt), imperfect information (don't know the opponent's cards), user modelling (identifying player patterns), and risk management (betting decisions).
    For over 10 years the University of Alberta Computer Poker Group has been been working on building a high-performance poker program. This work has led us through knowledge-based systems, simulations, game theory, and tree searching with learning.
    The prospects of a program successfully challenging the best human players in the near future is excellent. In this talk we will motivate the research, compare the different program designs, and discuss future directions.

Wednesday, May 25:

Attacker-Defender Models

Matthew Carlyle, Naval Postgraduate School

    Bilevel programming is a natural modeling approach for situations involving conflict where there is a leader, who must make an initial decision, and a follower, who makes his decision with complete knowledge of the leader's decision. I'll illustrate the formulation and solution of large "attacker-defender" models using zero-sum bilevel programming. I'll then discuss how max-min (or min-max) soluions to these problems can inform policy and tactical decision making in such areas as counter-proliferation of WMDs, ballistic missile defense, and critical civil infrastructure protection. In all of our applications we model adversaries who are malicious and very well-informed; preparing for randomly distributed attacks or counting on a successful surprise attack is a tremendous mistake. I will conclude with comments on the value of secrecy and of deception, and how we can use our models to provide quantitative estimates of these.