How do we help people make complex decisions when they have multiple, often conflicting, objectives? This is the core question of Multiple-Criteria Decision Aiding (MCDA). Whether you are a student choosing a university or a committee sorting job applicants, you are likely using some internal model to weigh different factors.
In her dissertation, "Elicitation of the parameters of a multi-criteria sorting model," Eda Ersek Uyanık tackles a major bottleneck in this field: how to accurately capture a decision-maker's (DM) preferences without overwhelming them with technical jargon or an endless barrage of questions.
TL;DR
The paper provides a rigorous framework for "direct elicitation"—asking a decision-maker simple classification questions to automatically determine the parameters of a Non-Compensatory Sorting (NCS) model. By treating the problem as a search through a graph of criteria combinations, the author develops algorithms that minimize the number of questions needed to build a precise mathematical model of a person’s decision logic.
What Problem Does This Paper Address?
In MCDA, "sorting" refers to assigning alternatives (like cars or candidates) into predefined, ordered categories (e.g., "Good" vs. "Bad"). To do this, models use parameters like weights (how important is price vs. safety?) and profiles (what is the minimum score needed to be "Good"?).
There are two traditional ways to get these parameters:
- Directly asking for values: "What weight do you give to fuel economy?" This is notoriously unreliable because humans struggle to translate their intuition into precise numbers.
- Indirect elicitation (Learning): Inferring parameters from past decisions. This is mathematically complex and often requires a large "training set" of examples that a DM might not have the patience to provide.
Uyanık focuses on direct elicitation of assignments. Instead of asking for weights, the analyst asks: "If a car is cheap but has poor safety, is it still 'Good'?" The challenge is that for $n$ criteria, there are $2^n$ possible combinations (coalitions) of criteria. Asking about every single one is impossible as $n$ grows. The paper aims to find the most efficient sequence of questions to map out the DM's "sufficient coalitions"—the specific sets of criteria that, if satisfied, are enough to push an alternative into a better category.
Methods
The research centers on the Non-Compensatory Sorting (NCS) model. Unlike "compensatory" models where a high score in one area can make up for a failure in another, NCS is stricter: you must meet requirements on a "sufficient" set of criteria.
The author proposes several graph-based questioning algorithms:
- DFS3 (Depth-First Search with Dichotomy): This is the "star" heuristic. It explores the graph of criteria combinations and asks questions in the "middle" of unexplored branches. This "dichotomy" approach effectively halves the search space with each answer.
- DFSHansel: Based on Hansel’s theory of monotone Boolean functions, this algorithm is mathematically proven to be optimal in the worst-case scenario. It guarantees that the number of questions will never exceed a specific lower bound.
- Decision Trees: For small numbers of criteria ($n \le 4$), the author computed the absolute optimal questioning strategy on average by evaluating every possible path a DM could take.
Datasets
While this is a theoretical and algorithmic paper, the methods were evaluated using:
- Exhaustive Simulations: The algorithms were tested against every possible valid NCS model for up to 6 criteria. This involved navigating the "Dedekind numbers"—a sequence that grows at a staggering rate (for 6 criteria, there are over 7.8 million possible models).
- Didactic Example: A "Car Selection Problem" was used to demonstrate how these rigorous tools could be adapted for real-world use, showing how a few general questions can drastically simplify the subsequent algorithmic search.
Key Insights and Ideas
- The Expressivity Gap: A major finding is that the NCS model is far more powerful than the simpler MR-Sort model (which uses basic additive weights). For 6 criteria, only about 3% of possible NCS models can be represented by simple weights. This proves that "non-compensatory" logic is often too complex for basic weighted-sum math.
- Symmetry and Dimensional Reduction: The author discovered that optimal questioning patterns for 2 or 3 criteria often reappear as sub-structures within the 4-criteria problem. This "dimensional reduction" allows for faster computation of optimal strategies.
- Information vs. Patience: There is a fundamental limit to how much we can learn. The paper compares the algorithms against the informational bound ($\log_2 D_n$), showing that while we can't reach the theoretical minimum due to the discrete nature of the questions, DFS3 and DFSHansel come remarkably close.
Key Results
- Efficiency: For 4 criteria, the theoretical optimal average is 7.65 questions. The proposed DFS3 algorithm averaged 8.09, and DFSHansel averaged 7.90. Both are highly efficient given the complexity of the underlying model.
- Worst-Case Guarantee: DFSHansel ensures that for 4 criteria, you never need more than 10 questions, regardless of how "weird" the DM's preferences are.
- Representability: The paper quantifies how many models require "k-additive" capacities. It shows that while simple weights fail often, move to "2-additive" models (considering pairs of criteria) covers over 90% of cases for $n=6$.
Limitations and Future Work
The primary limitation is the combinatorial explosion. While the methods work perfectly for up to 6 or 7 criteria, they become computationally "hopeless" for very large sets of criteria without further simplification.
The author suggests several paths forward:
- Handling "Noisy" DMs: Real people are inconsistent. Future versions of these algorithms need to handle contradictory answers or "I don't know" responses.
- Hierarchies: Grouping criteria into hierarchies (e.g., "Safety," "Performance," "Cost") could allow the algorithms to run on smaller subsets, making them applicable to much larger problems.
- Vetoes: The current study focused on a basic NCS model. Adding "veto" effects (where a single terrible score disqualifies an alternative) adds another layer of parameters to elicit.
Summary updated