By Ehrgott, Matthias
AI Magazine , Vol. 29, No. 4
An investor composes a portfolio of stocks in order to obtain a high return on his or her investment with a small risk of incurring a loss; an oncologist prescribes radiotherapy to a cancer patient so as to destroy the tumor without causing damage to healthy organs; an airline manager constructs schedules that incur small salary costs and that ensure smooth operation even in the case of disruptions. All three decision makers (DMs) are in a similar situation--they need to make a decision trying to achieve several conflicting goals at the same time: The highest return investments are in general the riskiest ones, tumors can always be destroyed at the expense of irreversible damage to healthy organs, and the cheapest schedules to operate are ones that leave as little as possible time between flights, wreaking havoc to operations in the case of unexpected delays.
Moreover, the investor, the oncologist, and the airline manager are all in a situation where the number of available options or alternatives is very large or even infinite. There are infinitely many ways to invest money and infinitely many possible radiotherapy treatments, but the number of feasible crew schedules is finite, albeit astronomical in practice. The alternatives are therefore described by constraints, rather than explicitly known: the sums invested in every stock must equal the total invested; the radiotherapy treatment must meet physical and clinical constraints; crew schedules must ensure that each flight has exactly one crew assigned to operate it.
Mathematically, the alternatives are described by vectors in variable or decision space; the set of all vectors satisfying the constraints is called the feasible set in decision space. The consequences or attributes of the alternatives are described as vectors in objective or outcome space, where outcome (objective) vectors are a function of the decision (variable) vectors. The set of outcomes corresponding to feasible alternatives is called the feasible set in objective space. The decision problem consists in finding that alternative with the most preferred outcome. But what exactly does "most preferred outcome" mean? Although in each of the attributes (or objectives or goals or criteria) the answer is clear (high return is preferred to low, cheap schedules are preferred to expensive ones), the situation is more difficult when all criteria are considered together: It is not possible to compare investments if the first has higher return but also higher risk than the second unless further information on trade-offs between the objectives or other preference information is available. One can distinguish three situations.
If the decision maker is able to completely specify his or her preferences explicitly, it is possible to construct a utility function that combines the criteria in a single function using multiattribute utility theory (see chapter seven in Figueira, Greco, and Ehrgott ). The decision problem then turns into a single-objective optimization problem that can then be solved by traditional mathematical programming methods. This scenario is very unrealistic.
If preference information is not complete or not explicitly available but one assumes that the DM is implicitly aware of those preferences, one can involve the DM in the solution process and assess preferences by asking for pairwise comparisons, aspiration and reservation levels, and so on. Such a scenario leads to interactive methods for finding a preferred alternative, where preference elicitation from the DM alternates with some calculation, often the optimization of a function using the information given by the DM as parameters (see chapter 16 in Figueira, Greco, and Ehrgott ).
If, however, no preference information is available, DMs face a multiobjective optimization problem (chapter 17 in Figueira, Greco, and Ehrgott ). This is what I am interested in this article. …