Title: Algorithmic Decision Theory and Preference-based Optimization
Speaker: Patrice Perny, University Pierre and Marie Curie, Paris, France
Date: Monday, April 25, 2011 3:00 pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Sponsored Jointly by Rutcor and the DIMACS/CCICADA Interdisciplinary Seminar Series.
Abstract:
The developments of Decision Theory in the last decades have provided a variety of sophisticated preference models for decision making in complex environments (uncertainty and risk, multicriteria decision making, collective decision making). In this area, much effort is devoted to the axiomatic analysis of preferences and the theoretical justification of mathematical models, for descriptive or prescriptive purpose. In most cases, less attention is devoted to the determination of the preferred solutions, that can easily be deduced from the model. However, when the set of feasible solutions has a combinatorial structure and/or is implicitly defined (e.g. by a set of constraints), the specification of the preference model is not sufficient. The determination of the preferred solutions requires a computational effort and raises new algorithmic issues due to the particular structure of preference models. For example, simple constructive approaches used in combinatorial optimization (e.g. dynamic programming, greedy search) do not automatically extend to cope with non-standard preferences models (e.g. partial order on solutions, non-linear cost functions). This suggests revisiting standard optimization problems considered in Operations Research textbooks, in the light of Decision Theory, and developing new algorithms for preference-based optimization. The aim of this presentation is to provide an overview of problems currently investigated along this line in Algorithmic Decision Theory. We will introduce preference-based optimization problems in various contexts such as compromise search in multiobjective optimization, fair optimization for multi-agents decision making, robust optimization and dynamic decision making under uncertainty. For some of these problems, we will discuss complexity issues and propose some solution algorithms.