University Paris Dauphine, France

**Organizers:****Ulle Endriss**, ILLC, University of Amsterdam, ulle@illc.uva.nl**Nicolas Maudet**, Lamsade, Université Paris Dauphine, maudet@lamsade.dauphine.fr**Fred Roberts**, DIMACS, froberts@dimacs.rutgers.edu**Alexis Tsoukiàs**, LAMSADE, tsoukias@lamsade.dauphine.fr

LAMSADE Cost Action Workshop Website

Title: Game Theoretic Solutions and How to Compute Them

When multiple self-interested agents act in the same environment, what is optimal for one agent to do generally depends on what the other agents do. Example environments are numerous but include auctions, elections, and games such as poker. Game theory provides a number of solution concepts that prescribe how each agent should act in such a setting. In this tutorial, we will review several of these concepts, including dominance, iterated dominance, minimax strategies, Nash equilibrium, and Stackelberg strategies. We will also review some basic algorithms for computing these solutions. No prior background in game theory is required.

Vincent Conitzer is an Assistant Professor of Computer Science and Economics at Duke University. His research focuses on computational aspects of microeconomics, in particular game theory, mechanism design, voting/social choice, and auctions; his work also involves techniques from artificial intelligence and multiagent systems. He received Ph.D. (2006) and M.S. (2003) degrees in Computer Science from Carnegie Mellon University, and an A.B. (2001) degree in Applied Mathematics from Harvard University. He also received an Alfred P. Sloan Research Fellowship (2008), an Honorable Mention for the 2007 ACM Doctoral Dissertation Award, the 2006 IFAAMAS Victor Lesser Distinguished Dissertation Award, the AAMAS Best Program Committee Member Award (2006), and an IBM Ph.D. Fellowship (2005). He is a co-author on papers winning a AAAI-08 Outstanding Paper Award and the AAMAS-08 Pragnesh Jay Modi Best Student Paper Award.

Title: Optimal Scheduling of Stochastically Independent Tests

(joint work with Endre Boros)

For many situations of interest (disease, narcotics, steroid use, nuclear contraband) there are diverse tests that can be applied to any specific case. Each test has a cost of application, and a performance characteristic, compactly expressed by an ROC relation between false alarm rate and detection rate. In addition to costs of applying the tests, there may be collateral costs associated with false positives (e.g. biopsy costs and discomfort, in the case of cancer tests). The problem, under these conditions, can be formulated as a very large linear programming problem. With the additional assumption that the randomness in the performance of a test is due to the hidden variation in the cases themselves (rather than some randomness in the observational process), the problem can be dramatically reduced to a dynamic programming problem. The formulation, solution method, and a discussion of some implications and open problems will be presented.

This research is supported in Part by the United States Department of Homeland Security administered through NSF Grant 0735910) by the United States Office of Naval Research under Grant Office of Naval Research (Grant N00014-05-1-0237), and U.S. Department of Homeland Security through the Center for Dynamic Data Analysis for Homeland Security administered through ONR grant number N00014-07-1-0150 to Rutgers University.

Bio Note: Paul Kantor is Prof. of Information Science at Rutgers, the State University of New Jersey, where he is a member of the LIS department, of DIMACS, RUTCOR, and of the CS Graduate Faculty. http://scils.rutgers.edu/~kantor

Title: Auctions as Information Aggregation Mechanisms.

This tutorial will introduce auction mechanisms that are becoming a standard decision-making tool in presence of large amounts of information that is held diversely by self-interested parties. Auctions are used to allocate and price goods by efficiently eliciting and aggregating (often minimal amounts of) information needed to make an optimal decision. Basic concepts from economic theory of auctions will be introduced, but the focus will be on issues and mechanisms that are relevant in practical decision-making, i.e., on auctions that are conducted electronically (e.g., procurement auctions, ad auctions, etc.). Since auctions research today is way beyond pure economics, the tutorial will review some of the most exciting topics that are within areas of optimization and algorithmics. Finally, the tutorial will briefly introduce some auction and information aggregation extensions such as prediction markets recommender systems.

Title: From Decision Theory to combinatorial optimization: problems and algorithms in graphs

The recent developments of Decision Theory have provided various sophisticated preference models for decision making (DM) in complex environments (DM under uncertainty and risk, Mutlicriteria DM and collective DM). In this area, much effort is spent on the axiomatic analysis of models, providing theoretical justifications for descriptive and normative points of view. However, when the set of alternatives has a combinatorial structure, the size of the search space requires significant additional efforts to determine the most-preferred solutions with respect to a given preference model. Moreover, simple constructive approaches used in classical combinatorial optimization (e.g. dynamic programming, greedy search) do not automatically extend to cope with non-classical preferences models (e.g. partial order on solutions, non-linear cost functions). Hence, designing new search algorithms to determine the most-preferred solutions becomes a critical issue.

Using classical graphs problems as illustrative examples (e.g. shortest paths, minimal spanning trees), the aim of this presentation is 1) to introduce preference-based search problems in graphs in various contexts such as multiobjective optimization, robust optimization and fair decision making, 2) to discuss complexity issues and to suggest some preliminary solution algorithms.

Title: Challenges in Business Analytics; an industrial research perspective.

The Mathematical Sciences group at IBM Research is involved in a number of internal and client external projects. In this tutorial we will present some of these projects and describe the challenges and issues we encounter in an environment where information technology becomes more prevalent. With the greater availability of data and the sophistication of clients, there is a growing need to tackle aspects not only from a mathematical perspective, but also from a computer science perspective. Data analysis must now consider aspects of data models, software architecture, data security, dynamic learning, just to name a few. Our optimization models need to take advantage of this abundance of data, incorporate stochastic aspects, be adaptive and dynamic and deal with data uncertainty. Furthermore, we see a growing client willingness to use mathematical models to address business problems. However, it is not always easy to understand and translate their needs into our models and often the inability to articulate our capabilities in a business language can hinder a project and produce negative results.

Eleni Pratsini is the head of the Mathematical and Computational Sciences Department at IBM Zürich Research Laboratories, Switzerland.

Previous: Program

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on September 18, 2008.