Chargement...
 

About this project

BACKGROUND


Today's decision makers in fields ranging from engineering to psychology to medicine to economics to homeland security are faced with remarkable new technologies, huge amounts of information to help them in reaching good decisions, and the ability to share information at unprecedented speeds and quantities. These tools and resources should lead to better decisions. Yet, the tools bring with them daunting new problems: the massive amounts of data available are often incomplete or unreliable or distributed and there is great uncertainty in them; interoperating/distributed decision makers and decision making devices need to be coordinated; many sources of data need to be fused into a good decision; information sharing under new cooperation/competition arrangementsraises security problems. When faced with such issues, there are few highly efficient algorithms available to support decisions. This Action's objective is to improve the ability of decision makers to perform in the face of these new challenges and problems through the use of methods of theoretical computer science, in particular algorithmic methods. The primary goal of the project is to explore and develop algorithmic approaches to decision problems arising in a variety of applications areas. Since many of the decision problems investigated arise in Artificial Intelligence, an important sub-goal is to explore the cross-fertilisation of Decision Theory and Artificial Intelligence.

Examples of such mutual benefits include, but are not limited to:

  • Computational tractability/intractability of consensus functions. Voting procedures and other functions aimed to help in establishing a consensus in different computer science applications (such as merging knowledge bases and information sources or exploring large data sets for patterns) have been shown to be often practically intractable when very large data sets are in question. There is a need for new algorithms and heuristics to handle such problems in similar directions chosen in bio-informatics (where methods of bio-consensus have been developed for sequencing the human genoma).

  • Improvement of decision support and recommender systems. The diffusion of web-based services pushed the development of on-line decision support and recommender systems for a large variety of applications (e-commerce, e-voting, e-services, semantic web, etc.). Such tools have to combine traditional decision making methods with flexible reasoning procedures allowing to handle the large variety of tasks required, to be adaptable to the changing environment where they operate and to perform self-improvement.

  • Development of automatic decision devices including on-line decision procedures. The presence of distributed decision situations where several human or automatic "decision makers" have to contribute and establish a decision, possibly under "hard" time constraints (such as in situations of humanitarian crisis) require, on one hand, the development of specific logical languages for preference modelling and aggregation and, on the other, the study of compact representations for preferences, goals and measures, particularly in presence of combinatorial structures of data. This is also relevant for situations where only uncertain and/or partial information is available, but a decision has, nevertheless, to be established. The existing literature on preference handling requires further expansion in order to handle such new challenges.

  • Robust Decision Making. Robustness is a crucial issue in the development of decision making methods in almost all areas where these are used. Sequential decision making, streaming of data, uncertain future scenarios, "what-if" analysis of decision situations, disruption management are all examples where the requirement of robust conclusions, robust methods, robust solutions is essential. Methods developed within the Multiple Criteria Decision Making methodology can contribute in that direction, but need to be expanded with further features in order to cope with both efficiency and uncertainty issues.

  • Learning for Multi-Agent Systems and other on-line decision devices. The diffusion of multi-agent based software technology for the development of e-services reinforced the necessity to develop learning procedures exploiting past cases (and best practices), existence of patterns in large data sets, instance based decision procedures. Several approaches have been suggested based on Boolean Functions, Rough Sets, Decision Trees, all sharing common algorithmic concerns and a similar conceptual basis found on decision theoretic issues. Such an approach to automatic learning becomes relevant for more general data mining and knowledge extraction issues recently developed.

Although such questions have been addressed for a relatively long time (last 10 years) and several interesting results have been achieved qualitative decision making, robust dynamic programming, new languages for modelling uncertainty, CP-nets and Bayesian networks, constraint programming etc.) based on solid theory developed in Computer Science and Decision Theory (decision under risk and uncertainty, multiple criteria decision making, sequencing and scheduling, pattern recognition, complexity theory, inference and reasoning, learning) there is still missing:
  • a general theoretical framework where approaches developed within such two communities can merge and be unified;
  • a thorough analysis of the impact to methods developed within such research area when very large (huge) data sets and uncertain and/or partial information come into play (as in the case of homeland security applications or in web-based auctions design).

The above issues constitute an emerging area of research as can be seen by a number of research projects recently funded (see section A in the second part of this document) and a number of workshops and meetings recently organised (for examples see:







From the above, it appears that there is an emerging community of researchers engaged in the above initiatives funded by national research projects. Besides there exist bi-lateral agreements and cooperation, but there is no European framework within which such a community could cooperate. Furthermore it should be noted that the proposal aims to put together researchers coming from different horizons: on one side people working in Decision Theory and Operational Research and, on the other, people working in Computer Science and Artificial Intelligence. There is increasing awareness about the necessity to improve cross-fertilisation among these two communities (who share several theoretical and practical concerns). It should also be emphasised that there is an increasing demand coming from end-users of decision support systems and the software industry for joint work between these two communities each of which have a long established tradition, but little international cooperation established. Last, but not least there is still lacking a European community of young researchers committed to this research area.

On the other hand, the novelty of the research subject is such that it is difficult to identify natural leaders at the European level. While within each specific area (Decision Theory or Computer Science) this is possible, it is necessary to work further in order to identify leading laboratories within this joint area. Indeed, the proposed Action aims (among others) to promote scientific competition within this area in order to establish such leadership. Under such a perspective Networks of Excellence, as conceived within the 6th FP, require a maturity not yet reached, and Research Training Networks, within the Marie Curie Actions, would require the existence of training leaders also yet to be identified. COST Actions, therefore, seem to be the most appropriate due to their flexibility and the opening to further potential participants while the project is in progress. It should also be noted that this is a research field with a strong competition for scientific excellence between European and US based researchers. It is therefore the moment to fund the networking of research activities presently undergoing at a national level, creating the appropriate synergies and mobilising competencies sparse all over Europe.

The benefits from this project and its associated activities are expected to be essentially of scientific and potentially technological nature. The Action will help filling the gap between Decision Theory and Computer Science and Artificial Intelligence more specifically. It will also provide a bridge among specialists in the two domains. Besides, the Action will be able to promote in the services industry the use of new technology integrating findings in AI and Decision Theory. These will concern both the end-users and the software industry aiming to implement new decision support packages.

It should also be noted that several fields in the Social Sciences, Economics, Engineering Sciences will benefit from the advances in this area. E-government, Environmental Assessment, E-commerce, Public Policy Evaluation, Risk Management and Security are all areas where the findings of this project apply (as for instance in the case of implementing on-line recommender systems or conflict detection devices for International Organisations). At the same time the findings of this research project will affect the broader scientific community through its impact on global issues such as efficient humanitarian logistics, effective crisis management, reliable governance support, meaningful policy evaluation.

The support of a specific COST Action to such a project, besides providing the synergy for conducting (for the first time) this research at an European level will constitute the nutshell of a future community of researchers committed to this research area. For this purpose, large part of the resources of the COST Action will be dedicated in supporting young researchers and PhD students working in this area besides promoting the subject and disseminating its results.



OBJECTIVES AND BENEFITS


The main objective of the Action is twofold:
- propose new algorithmic solutions for hard decision theoretic problems arising from the use of large amounts of information, the presence of uncertainty as well as of complex structures of data;
- use results and concepts from decision theory in order to improve and advance in computer science and artificial intelligence.

More precisely the following results will be pursued:
  1. Establish a methodology for robust decision support including both a conceptual framework for robustness in decision making and the design of algorithms performing robustly (providing robust results using a reasonable amount of computing resources).
  2. Develop a common framework for the use of graphical representations in decision making, exploring the limits for algorithms implementing such an approach.
  3. Fix a theoretical framework integrating preferences and reasoning in the design and implementation of recommender systems, automatic decision devices, planning systems, information retrieval systems and other broadly defined decision support tools.
  4. Enhance the theory around preference elicitation, modelling and aggregation with particular emphasis on the size of the information to elaborate and the compactness of the representation. Moreover, the problem of integrating the representation of uncertainty with the one of preferences remains a key issue within this project.
  5. Define a methodology for the use of knowledge extraction algorithms combined with decision theoretic principles for the management of critical decision situations, supported by adequate algorithms.
  6. Develop methods and tools to be used in group decision making, collective and social choice problems with particular emphasis in e-democracy and automatic negotiation.


Given the exploratory nature of the research project the deliverables would include:
  • closed theoretical problems such as computational complexity results, representation theorems, (im)possibility results and axiomatic characterisations of procedures and methods;
  • new methodological frameworks (conjoint measurement, robustness, compact representation of preferences, preferences under uncertainty, decision under risk and uncertainty, knowledge extraction, argumentation in decision support, negotiation analysis);
  • design of new algorithms with guaranteed performance (multi-objective optimisation, graphical representations, sequential decision making, learning from examples, unsupervised classification);
  • layout of decision support tools (preferential queries, negotiation protocols, logical tools for uncertain and bipolar preferences, group decision support procedures, graphical interfaces).

The above results can be of interest for three types of users:
  • developers of decision support algorithms, tools, methods and systems in the services industry and the consulting companies;
  • the software industry developing algorithmic libraries for recommender systems, optimisation, information retrieval and knowledge extraction;
  • end-users in e-democracy, decision makers involved in crisis management and homeland security, e-commerce, logistics, production scheduling, clinical decision making, bio-informatics.

Indeed all such potential "clients" of this research are working on large and urgent problems including security management, e-government, collective decision making, information fusion, on-line decision making, auctions implementation, where new theory is lacking. Typical examples of the results expected within this research project include:
  1. Combinatorial auctions A growing number of systems supporting on-line negotiations have been commercialised over the recent years. These systems usually implement different variants of auction mechanisms. Auctions are centralised procedures whereby an auctioneer collects the preferences of different bidders and computes an optimal allocation of items (winner determination problem) to be delivered to agents. When bidders can submit bids on bundles of items, the term of combinatorial auctions is used. Combinatorial auctions exhibit a tremendous potential impact for such tools, but remain largely unexploited. This is largely due to the complexity of the winning determination problem (the later being an issue typically studied in social choice and game theory).
  2. Retrieving and ranking information on the web. The web provides access to multiple information sources, but many of them are only accessible with charges. A combinatorial decision problem which arises naturally in applications is then to determine which subset of sites to choose for launching a multiple query, given a budget constraint and a preference order between sites, or a vectorial evaluation of each site on multiple criteria. A subsequent problem arises for combining ranking results from the different information sources. Moreover, given the possibly high number of results and the need for quick answers, it is necessary to study the computational complexity of the underlying combinatorial problems, and to design efficient aggregation procedures.
  3. Sharing spatial resources. Due to their cost, space projects such as Earth Observing Satellites (EOS) are often co-funded and then exploited by several agents (countries, military agencies ...). An EOS acquires images of specified areas on the Earth surface, in response to complex observation demands from users, collected each day. Demands are given weights, reflecting the degree of preference the requesting agents give to the satisfaction of the demand. Each day the satellite imaging activity must be planned, and allocation of images to agents must be (1) efficient: the satellite should not be under-exploited, and (2) equitable (fair): each agent wants to get a return on investments proportional to its financial contribution. This type of problems applies to several other kinds of resources which have to be allocated through an automatic procedure (see for example the problem of designing a supply chain management for humanitarian logistics).
  4. Recommender systems. The important development of e-commerce has open new spaces for preference modelling and decision support activities. Nowadays, the internet is not only seen as a new media for advertising and sales enhancement, but also as a powerful tool for improving knowledge about consumer's preferences. For this reason, Web-advisor systems are used both to provide users with relevant recommendations for an item and collect individual preference information, to model the collective opinion so as to better anticipate the market trend. In this respect, the basic research problems to be studied are linked to preference representation, individual and collective decision making, as well as collaborative filtering procedures.
  5. Electronic democracy. A possible application of preference aggregation on combinatorial structures is electronic vote concerning decisions about several preferentially dependent variables, that have to be taken in small organisations (small companies, laboratories, recruiting committees etc.). Unlike political elections, such decisions often bear on combinatorial domains (e.g. fulfilling several positions given some preferential correlations between candidates, task or resource allocation etc.) Developing software for such collective decisions needs an interactive preference elicitation tool on combinatorial domains, which calls for choosing a suitable language for preference representation as well as optimisation procedures associated with collective decision rules.



SCIENTIFIC PROGRAMME AND INNOVATION


The scientific programme of the proposed COST Action is expected to be structured around four Working Groups. In the following the major scientific challenges for each of them are presented.



While the above topics have been presented separately, there are obvious connections among them. For example, graphical models are relevant in sequential decision making. Another example involves the preference elicitation problem and the design of auctions. The overall conduction of the Action will take care to offer substantial opportunities to interactions between different groups.

The above methodological developments will undoubtedly have an impact on technological developments focused mainly on the provision of advanced decision support tools in the contexts previously mentioned, characterised by the presence of one or more factors such as sequentiality, large amounts of data, multiple participants. The project will provide both generic tools for general purposes such as preference modelling, graphical model building, negotiations and ad hoc tools for specific application areas including participatory budgeting, recommender systems, semantic Web etc.. It is aimed to providing a reference repository for web-based decision support software. Moreover it will provide a repository of typical instances of hard decision theoretic problems in order to help algorithmic comparison. Because of the multi-participant nature of many of the problems tackled, some attention to security aspects will be devoted.

Succeeding in the above objectives will introduce major theoretical breakthroughs for both Computer Science and Decision Theory in important application areas such as semantic web, intelligent information retrieval, critical decision making, security management and e-government. It is believed that many of the more important technological targets for the next generation private and public services depend on such achievements.


HISTORY OF THE PROPOSAL

The initiative about this proposal was generated through the meeting of two major communities: the first mainly making reference to Decision Theory and particularly to Multiple Criteria Decision Analysis, mainly organised around the EURO (European Association of Operational Research Societies) Working Group on MCDA (see http://www.inescc.pt/$\sim$ewgmcda); the second one mainly structured around Computer Science and most often Artificial Intelligence conferences, not yet organised in a precise group. Such a meeting results from a mutual interest of researchers in the Decision Theory area for concerns and findings in Artificial Intelligence and viceversa. The list of meetings, workshops and conferences listed in section B of Part I shows the evolution of this joint efforts.

At the same time there are several national funded research projects on the subjects of the proposal. In the following some examples are quoted:
- Graduiertenkolleg Wissensrepräsentation (doctoral programme in knowledge representation), funded by DFG, (1998-2007, led by G. Brewka).
- Constraints and preferences as a unifying formalism for the analysis of computer systems and the solution of real-life problems. Funding institution: Italian Ministry for Research MIUR PRIN (2005-2007, let by F. Rossi).
- Individual and collective decision making: analysis of consistency and representativeness. FUNDING SOURCE: Local Government of Castilla-Leon Region (2005-2008, led by J. Gonzalez Pachon).
- Mathematical and Logical Models for Preference Modelling, Data Mining and Decision Aiding, supported by the CNRS, the French Ministry of Education and the ANR (2003 - 2009, led by D. Bouyssou).
- ''===Concepts and systems for supporting electronic
democracy===''. Funded by the Madrid Government (2006-2009, led by David Rios Insua).
- Modeling and elicitation of decision parameters in personal information agents. Funded by the Swiss National Foundation (2004-2008, led by Pearl Pu.
- Characterisation of aggregation operators of multi-criteria references and economic-financial applications, funded by the Italian Ministry of Research, (2006-2009,led by S. Greco).
- EVAL project: Methodology and generic software for decision aiding in a securised multi-users context, funded by the Ministry of Wallony, Belgium, (2004-2008, led by Marc Pirlot).
- MIRÓ: advanced Methods of sImulation for RObustness analysis in Decision Support Systems, funded by the National Foundation for Science and Technology, Portugal (2005-2008, led by José Figueira).
- Decision Desk: advanced tools for Decision Support Systems, funded by the Luxembourg State, (2006-2009, led by Raymond Bisdorff).
- PHAC: Preference Handling and Aggregation in Combinatorial Domains, funded by the ANR, (2005 - 2008, led by Jérôme Lang).
- Modelling Human Reliability in Decision and Risk Analysis, funded by the EPSRC, UK, (2006-2008, led by Simon French).

To the above it should be added a large variety of "private" research contracts conducted for "clients" such as banks, telecommunication companies, railways, mass transit authorities, aerospace industry, software companies, consulting firms, road construction agencies and logistic societies. Last, but not least it should be mentioned a large number of bi-lateral agreements between research laboratories, potentially involved in this proposal funded by specific bi-national funds.

Within the two communities previously mentioned became mature the idea of coordinating such research efforts on an European level, a process confirmed by the increasing attendance to the numerous workshops already organised or scheduled in the immediate future (see section B in Part I). The idea of submitting a proposal for a COST Action has been discussed as one of the possible fund raising action at European level and given priority one since it has been considered that these type of actions were fitting better the necessity of networking the presently un-coordinated national research efforts.

Historique