Elicitation of the parameters of a multi-criteria sorting model

Eda Ersek UyanikarXiv 2026 · arXiv

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:

  1. 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.
  2. 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

Abstract

Multiple-criteria decision aiding (MCDA) proposes models and methods for different types of decision problems such as choice, ranking or sorting. Such models involve various parameters that must be elicited. In the elicitation process, all necessary information has to be taken from the decision-maker. For this, several direct and indirect elicitation methods are suggested in the literature. In this work, we concentrate on direct elicitation: we aim at providing a rigorous elicitation procedure for the parameters of the Non-Compensatory Sorting model (NCS), which has been characterized by an axiomatic analysis. A basic version of the NCS model is considered, i.e., a model with two categories and no vetoes. The parameters are the set of sufficient coalitions of criteria and the profile separating the two categories. Regarding the sufficient coalitions, we propose several questioning algorithms that engraft questions on classical graph exploration algorithms such as depth-first search. Such algorithms are implemented and evaluated by simulation. For eliciting the limit profile, we design a questioning algorithm using dichotomy. Questioning algorithms can be optimal in the worst case or on average. An optimal algorithm in the worst case has been proposed by Hansel in the framework of monotone Boolean functions. We implement and evaluate this algorithm as a variant of the depth-first search approaches. Regarding optimal questioning strategies on average, we evaluate decision trees for up to four criteria. On the other hand, we assess how more general is NCS as compared to MR-Sort, a particular case of the NCS model in which sufficient coalitions can be represented by additive weights.
BibTeX
@misc{uyanik2026elicitation,
  author = {Eda Ersek Uyanik},
  title = {{Elicitation of the parameters of a multi-criteria sorting model}},
  year = {2026},
  eprint = {2611.13062},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13062},
}
Figure