# Identifying two piecewise linear additive value functions from anonymous preference information

Vincent Auriau, Khaled Belahcene, Emmanuel Malherbe, Vincent Mousseau, Marc Pirlot

► To cite this version:

Vincent Auriau, Khaled Belahcene, Emmanuel Malherbe, Vincent Mousseau, Marc Pirlot. Identifying two piecewise linear additive value functions from anonymous preference information. 2026. hal-05521169

HAL Id: hal-05521169

https://hal.science/hal-05521169v1

Preprint submitted on 23 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Identifying two piecewise linear additive value functions from anonymous preference information

Vincent Auriau<sup>a, b,*</sup>, Khaled Belahcène<sup>a</sup>, Emmanuel Malherbe<sup>b</sup>, Vincent Mousseau<sup>a</sup> and Marc Pirlot<sup>c</sup>

<sup>a</sup>MICS, CentraleSupélec, Université Paris Saclay, France

<sup>b</sup>Artefact Research Center, France

<sup>c</sup>MATHRO, Université de Mons, Belgique

ORCID (Vincent Auriau): https://orcid.org/0009-0002-9640-2639, ORCID (Khaled Belahcène): https://orcid.org/0000-0003-4502-9539, ORCID (Emmanuel Malherbe): https://orcid.org/0009-0006-0898-6873,

ORCID (Vincent Mousseau): https://orcid.org/0000-0001-8574-3337, ORCID (Marc Pirlot):

https://orcid.org/0000-0002-3689-0944

**Abstract.**

Eliciting a preference model involves asking a person, named decision-maker, a series of questions. We assume that these preferences can be represented by an additive value function. In this work, we query simultaneously two decision-makers in the aim to elicit their respective value functions. For each query we receive two answers, without noise, but without knowing which answer corresponds to which decision-maker. We propose an elicitation procedure that identifies the two preference models when the marginal value functions are piecewise linear with known breaking points.

# 1 Introduction

The additive value model is standard to specify preferences over a set of alternatives evaluated on several criteria, see [11]. More precisely, given an alternative $x$ defined by its evaluation on $n$ criteria $x = (x_1, \dots, x_n)$, where $x_i$ is the evaluation of $x$ on criterion $i$, the value of $x$ is defined by $u(x) = \sum_i u_i(x_i)$, where $u_i$ is the marginal value function on criterion $i$. In this paper, we consider that these marginals $u_i$ are strictly increasing and piecewise linear, with an a priori defined linear decomposition. In the following, we will call such preference model a UTA model. To elicit such a UTA model, it is usual to define standard queries corresponding to matching questions [16] involving two alternatives $x$ and $y$ whose evaluations differ on two criteria $i$ and $j$ only. Three evaluations out of $x_i, x_j, y_i$, and $y_j$ are given, and the respondent provides the unfixed value in such a way that indifference holds between $x$ and $y$ (which is noted $x \sim y$). It implies that $u_i(x_i) + u_j(x_j) = u_i(y_i) + u_j(y_j)$. The set of points $(x_i, x_j)$ in the $(i, j)$ plane for which $u_i(x_i) + u_j(x_j)$ is a constant forms an indifference curve in the $(i, j)$ plane. Using matching questions, one can identify points belonging to each indifference curve [3], which will prove useful in the sequel.

We consider a framework in which we have to elicit simultaneously two UTA models. In this context, the answer to a matching query consists of two evaluations $a$ and $a'$ for the unfixed component. These responses are provided anonymously, without the ability to know to which model each answer corresponds. In this paper, our

purpose is to study this problem from an identifiability perspective. In other words, we investigate whether it is always possible to define a finite sequence of queries whose answers enable the identification of the two piecewise linear additive value functions models. The identifiability problem can also be formulated as a game in which a first player specifies the queries, and a second player provides (thruthfull) answers. The question becomes: is there a finite winning strategy for the first player? In another variant of the game (not considered in this paper), the second player can answer with an (adversarial) noise.

Although the problem is purely formulated as a formal one, it is worth noticing that it corresponds to real-world problems. For instance, a supermarket is willing to adapt the list of products to its customer base. The products selected should align with the client's preferences. Yet, not all customers necessarily have the same preferences, and one can consider a market segmentation in which each segment represents a group of clients with homogeneous preferences.

**Example 1.** In this paper, we will use, as a running example, the choice among electric cars that differ on two criteria: autonomy (from 100km to 600km) and price (from 10k€ to 50k€). Answers to preference queries are obtained through an online system that guarantees anonymity. Two decision-makers express their preferences: Commuter will use the car in a urban context for relatively short distances, while Traveler will drive long distances. Commuter and Traveler can use respectively 30k€ and 40k€ liquid savings; they need to get a loan for car that are more expensive than their savings.

Such type of problem has already been tackled from a preference learning perspective [2], and the identifiability result proposed here is of high importance to justify the search for efficient learning algorithms that infer multiple UTA models from preference statements.

Our aim is to provide a systematic elicitation procedure to identify two additive piecewise linear value functions from a finite sequence of matching queries. In this introduction, we provide an overall presentation of this procedure; the following sections aim at providing a detailed and justified description of this elicitation procedure. Hence, the main result of the paper can be formulated as follows.

**Theorem 1.** It is possible to elicit two piecewise linear additive preference models based on anonymized preference information using a finite number of indifference queries.

<footnote>* Corresponding Author. Email: vincent.auriau@artefact.com</footnote>
In our setting, each matching query involves alternatives that vary on two criteria *i* and *j* only, with three values fixed by the Eliciter and the responses are provided by the different Decision-Makers (DMs) in order to obtain an indifference statement. The value space of criteria (*i*, *j*) defines a plane where the queries can be fully represented since everything else is equal. In particular, given that marginal value functions are piecewise linear, the indifference curves are also represented by (different) piecewise linear functions. In this criteria plane, it is convenient to define two types of queries with a specific geometry that we will use as “building blocks” of our elicitation procedure:

*   **Single Rectangle constraint:** The query values as well as the answers are within a single rectangle, defined by the a priori defined linear segments on both criterion scales.

*   **Neighboring Rectangles constraint:** The query values are selected such that it implies two neighboring rectangles defined by the linear segments on the criterion scales.

Single rectangle queries make it possible to elicit the anonymized pair of slopes of marginal value functions on a specific interval, while neighboring rectangles queries provide coupling constraints allowing to assign the slopes to the two value functions. Using these building blocks, the procedure can be summarized as follows:

*   Initialization: the procedure starts with the two first criteria and postulates w.l.o.g. that the slope on criterion 1 are equal to one on the first segment. An Single-Rectangle query identifies the slope of each model for the first segment on criterion 2.

*   Iteration: given an elicited segment $\ell$ on criterion 1, a succession of queries allows to identify the slopes of both models on segment $\ell + 1$; the same applies to criterion 2.

*   Finally, in order to obtain all marginal value functions, one can apply the same principle for all pairs of criteria $(1, i)$, $i \neq 1$.

The paper is organized as follows. After a review of related works in Section 2, Section 3 provides general notation. Section 4 presents the two query types which constitute “building blocks” for the identification procedure. Section 5 presents results justifying the iterative nature of the general procedure presented in Section 6.

## 2 Background and Related Work

The additive value (or utility) function (AVF) model is the most widely used and studied preference model. It may represent preference relations on sets of objects $x = (x_1, \dots, x_n)$ described by $n$ attributes or criteria. If attribute $i$ takes values in a set $\mathcal{X}_i$ (criterion scale), let us consider a preference relation $\succ$ on the Cartesian product $\mathcal{X} = \prod_{i=1}^n \mathcal{X}_i$. Under well understood conditions on the preference $\succ$ [11, 10, 16], there exist real valued functions $u_i : \mathcal{X}_i \to \mathbb{R}$ such that, for all $x, y \in \mathcal{X}$, we have

$$x \succ y \quad \text{iff} \quad \sum_{i=1}^{n} u_i(x_i) \geq \sum_{i=1}^{n} u_i(y_i). \quad (1)$$

The marginal value (or utility) functions $u_i$ are unique up to positive affine transformations. The main property required of $\succ$ for admitting such a representation is an independence condition allowing for ceteris paribus reasoning. Specifically, one may compare objects without specifying the values of the attributes on which they agree. Such characterization results allow one to devise query strategies for eliciting the marginal value functions, hence describing the preferences on the whole Cartesian product by a numerical representation. Among the query strategies, the method of indifference judgments builds a

“standard sequence” of points on a criterion scale, which are equally spaced (in terms of value). This is done by using a fixed interval on the scale of another criterion as a unit measure. Queries are designed as follows. Let $q_i, p_i$ be two distinct values on the scale $\mathcal{X}_i$ of criterion $i$, and $q_j$ a value on the scale $\mathcal{X}_j$ of criterion $j$. The query is: “What is the value $a_j \in \mathcal{X}_j$ such that the value difference between $q_i$ and $p_i$ on $\mathcal{X}_i$ is exactly compensated by the value difference between $q_j$ and $a_j$ on $\mathcal{X}_j$ (all other things being equal, i.e., ceteris paribus)?” The answer $a_j$ is a first point in a standard sequence. The next point is the answer to the modified query obtained by substituting $q_j$ by $a_j$ in the initial query, and so on. The pairs $(q_i, q_j)$, $(p_i, a_j)$ belong to an indifference curve in the domain $\mathcal{X}_i \times \mathcal{X}_j$ (hence the name “indifference judgments”).

Jacquet-Lagrèze and Siskos [8] developed a method, called UTA, to learn marginal value functions of an AVF that is compatible with known preferences expressed on a set of pairs of objects. In order to exploit linear programming they assume that the marginal value functions are piecewise linear. Let the points $x_{i,\ell}, \ell = 0, 1, \dots, L$ partition the scale $\mathcal{X}_i$ of criterion $i$ into $L$ subintervals $[x_{i,\ell}, x_{i,\ell+1}]$, and the marginal value function be piecewise linear with respect to this decomposition. The latter is known as soon as the values $u_i(x_{i,\ell})$ at the intervals endpoints are determined. Alternatively, it suffices to determine the slopes of the linear segments of the marginal value function $\gamma_{i,\ell} = [u_i(x_{i,\ell}) - u_i(x_{i,\ell-1})]/(x_{i,\ell} - x_{i,\ell-1})$. This method has been subsequently widely developed and applied [9]. In general, there are several models (actually, an infinite number of models) compatible with the set of preference examples. Some papers [e.g., 7] deal with formulating robust conclusions by considering the set of all models compatible with the examples.

In this work, we consider the case in which two DMs reply to elicitation queries each using her own AVF model, with piecewise linear marginals. The answers to the queries are not tagged by the name of the DM. The question we tackle is whether it is possible to identify each DM’s model without ambiguity, by asking queries of the type “indifference judgments”.

Similar work about model identifiability problems have been addressed in multicriteria decision analysis in the case of the Choquet integral [12], the hierarchical Choquet integral [5] and more [4, 14]. This question of model identifiability can be approached from different angles. At its core is a parametric family of functions $(f_\omega)_{\omega \in \Omega}$ where $\Omega$ is the latent parameter set, and each $f_\omega$ is a function mapping queries in $\mathcal{Q}$ to answers in $\mathcal{A}$. Abstract identifiability can be cast as the existence of a query $q \in \mathcal{Q}$ such that two distinct parameters $\omega \neq \omega' \in \Omega$ yield distinct outcomes, i.e. $f_\omega(q) \neq f_{\omega'}(q)$. More operational definitions exist. For instance, various notions of combinatorial dimension have been put forward so as to upper bound the number of queries needed to distinguish concepts [1]. In turn, these bounds can be used to obtain statistical guarantees w.r.t. the estimation of those parameters from data, playing a key role in probably approximately correct machine learning (see e.g. [15, 13]). The problem we address here is not standard w.r.t. those approaches, because neither the queries nor the latent parameters are. Indifference queries do not have a binary outcome, as expected from concept learning theory. More importantly, our latent parameter space encompasses both the preference models of the DMs but also the identity of the DM associated to each answer (and thus grows with the number of queries). A more fruitful analogy comes from adversarial game-playing: consider two players, the Eliciter and the Adversary, and a fixed parameter space, such that $\omega$ completely specifies two UTA models. The Eliciter can either query the Adversary, or reveal two UTA models. The Adversary answers queries as he wishes. He immediately loses
if there are no parameter $\omega$ compatible with all answers, and wins if the Eliciter reveals a parameter $\omega_E$ and he can provide an alternate $\omega' \neq \omega$ which is compatible with all answers. A procedure based on mixed-integer linear programming is described in [2] and allows to decide whether a set of preference statements can be partitioned into two DMs represented by a UTA model, and can serve as a judge in this game. In effect, this allows the Adversary to cheat and modify the model behind the scene, as long as this behavior cannot be detected, and forces the Eliciter to reduce the set of all possible models to a singleton. Such approach can be found in [6]. Here, we show that the Eliciter has indeed a winning strategy.

### 3 Problem setting

We consider a set $\mathcal{N} = \{1, ..., n\}$ of criteria. A criterion $i \in \mathcal{N}$ is defined on its scale, noted $\mathcal{X}_i \subset \mathbb{R}$. For each criterion $i$, we are given a positive integer $L_i$ and $L_i + 1$ values $x_{i,0} < x_{i,1} < \dots < x_{i,L_i} \in \mathcal{X}_i$.

The value function of a DM $\kappa$ in the form of a UTA model can be defined by its values at the edges of the intervals, $(u_i^\kappa(x_{i,\ell}))_{\ell \le L_i, i \in \mathcal{N}}$. An equivalent formulation uses the slopes of this value function $\gamma_{i,\ell}^\kappa = \frac{u_i^\kappa(x_{i,\ell})-u_i^\kappa(x_{i,\ell-1})}{x_{i,\ell}-x_{i,\ell-1}}$ for $1 \le \ell \le L_i$. We consider the functions to be strictly increasing, meaning that $\gamma_{i,\ell}^\kappa > 0$.

**Example 2.** (Ex. 1 cont.) The marginal value functions for both DMs (Traveler & Commuter) are provided in Figure 1(a) for the price criterion, and in Figure 1(b) for the autonomy criterion. These value functions induce interpretable preferences: for instance, an increase in autonomy from 100km to 200km is valued 2 (10, resp.) for Traveler (for Commuter, resp.). Indeed, 200km autonomy is a poor value for Traveler who drives long distances, while it is already reasonably good for Commuter who drives shorter distances.

Given the value function $u^\kappa$ of DM $\kappa$, one can define *Indifference curves* which are the sets of points $x \in \prod_{i \in \mathcal{N}} \mathcal{X}$ in the Cartesian product of criteria having the same value, i.e., such that $u^\kappa(x) = z$ ($z \in \mathbb{R}$). All pairs of objects on an *Indifference Curve* are said to be indifferent, meaning they belong to the symmetric part $\sim$ of the $z$ relation defined in (1).

**Example 3.** (Ex. 2 cont.) *Indifference curves induced by the value functions of Traveler and Commuter are depicted in Figure 1(c). Obviously, for a given DM, indifference curves do not cross. On the contrary the indifference curves of the different DMs do cross, meaning their preferences are different.*

One can note that the criteria space $\mathcal{X}_i \times \mathcal{X}_j$ can be seen as a grid where each rectangle element is defined by the breaking points on each criterion: $(x_{i,\ell_i-1}, x_{j,\ell_j-1})$; $(x_{i,\ell_i}, x_{j,\ell_j})$. In this specific rectangle denoted $\mathcal{R}_{\ell_i, \ell_j}$ (corresponding to the $\ell_i^{th}$ interval of criterion $i$ and the $\ell_j^{th}$ interval of criterion $j$), the indifference represented by the value functions is a straight line, neither horizontal nor vertical, whose slope is $\gamma_{i,\ell_i}^\kappa / \gamma_{j,\ell_j}^\kappa > 0$.

We consider two DMs, noted $\alpha$ and $\beta$, that can be queried at will. We define a query $\mathcal{Q}$ as questioning the DMs concerning alternatives whose evaluations vary on two criteria only. More specifically, we formulate $\mathcal{Q}$ as the specification of an ordered pair of criteria, $(i, j) \in \mathcal{N}^2$ and a triplet of values on these criteria: $(q_i, q_j, p_i)$, with $(q_i, p_i) \in \mathcal{X}_i^2$ and $q_j \in \mathcal{X}_j$. This query triggers the collection of answers $\mathcal{A} = \{a_j^\kappa, a_j^{\kappa'}\} \subset \mathcal{X}_j$ from the two DMs. We arbitrarily decide to note $\kappa$ and $\kappa'$ such that $a_j^\kappa \le a_j^{\kappa'}$. We also sometimes omit to specify the selected criteria, when it is already clear enough. The elements

of $\mathcal{A}$ are such that either $[(q_i, q_j) \sim \alpha (p_i, a_j^\kappa), (q_i, q_j) \sim \beta (p_i, a_j^{\kappa'})]$ or $[(q_i, q_j) \sim \beta (p_i, a_j^\kappa), (q_i, q_j) \sim \alpha (p_i, a_j^{\kappa'})]$, with $\sim \alpha$ (resp. $\sim \beta$) denoting indifference for DM $\alpha$ (resp. $\beta$). In other words, the answers are non-identifiable, meaning that we don't know which DM they come from. Some queries cannot be answered by one, or both DMs, when the difference of value on the first criterion is too large to be compensated on the second one. In this case, we are provided with the answer “None”.

**Example 4.** (Ex. 3 cont.) a query $\mathcal{Q}=(200km, 30k \in) \sim (400km, ?)$ can be interpreted as: given a car with a $30k \in$ price having 200km autonomy, how much more would you be willing to pay to obtain 400km autonomy? the two answers are $(34k \in, 43k \in)$ without knowing which DM gave each answer.

Eliciting the value function of both DMs involves a sequence of queries, and for each of these queries, there is a hidden bit of information. Hence, the problem of attributing each answer to the correct DM compounds at each step—giving a combinatorial aspect, potentially explosive, to this problem. A summary of the notation can be found in Table 1.

<table><caption>**Table 1:** Notations summary</caption><thead><tr><th>Description</th><th>Notation</th><th></th></tr></thead><tbody><tr><td>Criteria set</td><td>$\mathcal{N} = \{1, ..., n\}$</td><td>$i, j \in \mathcal{N}$</td></tr><tr><td>Criterion scale</td><td>$\mathcal{X}_i = [x_{i,0}, x_{i,L}]$</td><td>$\ell \in \{0, ..., L\}$</td></tr><tr><td>Criterion interval</td><td>$[x_{i,\ell}, x_{i,\ell+1}]$</td><td></td></tr><tr><td>Decision makers</td><td>$\alpha, \beta$</td><td></td></tr><tr><td>Value functions</td><td>$u_i^\kappa(\cdot)$</td><td>$\kappa \in \{\alpha, \beta\}$</td></tr><tr><td>Marginal value functions</td><td>$u_i^\kappa(\cdot)$</td><td>$\kappa \in \{\alpha, \beta\}, i \in \mathcal{N}$</td></tr><tr><td>Value function</td><td>$\gamma_{i,\ell}^\kappa$</td><td>$\kappa \in \{\alpha, \beta\}, i \in \mathcal{N}$, $1 \le \ell \le L$</td></tr><tr><td>slopes</td><td>$\mathcal{Q} = (q_i, q_j) \sim (p_i, ?)$</td><td>$q_i \in \mathcal{X}_i, p_j \in \mathcal{X}_j$</td></tr><tr><td>Queries</td><td>$a_i^\kappa, a_i^{\kappa'}$</td><td>$i \in \mathcal{N}, a_i^\kappa \in \mathcal{X}_i$</td></tr><tr><td>Answers</td><td>$a_i^\kappa, a_i^{\kappa'}$</td><td>$i \in \mathcal{N}, a_i^\kappa \in \mathcal{X}_i$</td></tr></tbody></table>

### 4 Play Patterns

Our perfect Eliciter relies on two basic play patterns or sequences of moves (i.e. indifference queries) yielding preference information that allows it to reach specific short-term goals. Given two criteria $i \neq j \in \mathcal{N}$, these goals can be specified geometrically in the plane $\mathcal{X}_i \times \mathcal{X}_j$: obtaining indifference statements between points located either in the same rectangle (Section 4.1) or adjacent rectangles (Section 4.2).

#### 4.1 Obtaining Single-Rectangle Preference Information

We are first interested in collecting preference information in the form of anonymized indifference statements between points lying in the same rectangle $\mathcal{R}_{\ell_i+1, \ell_j+1}$. Play Pattern 1 ensures this information can be obtained in at most two queries.

The play pattern opens with the following query from the bottom right corner to the left side: $(i: x_{i,\ell_i+1}, j: x_{j,\ell_j}) \sim (i: x_{i,\ell_i}, j: ?)$, yielding two answers $a^1 < a^2 \in \mathcal{X}_i \cup \{\text{None}\}$. There are three cases:

* If $x_{j,\ell_j} \le a^1 \le a^2 \le x_{j,\ell_j+1}$ (Case 1, illustrated by Fig. 2). Both indifference curves lie below the diagonal and hit the left side of the rectangle. The specified goal is reached in a single query.

* Else, if $a^1 \le x_{j,\ell_j}$ (Case 2, illustrated by Fig. 3). Exactly one DM has an indifference curve (in blue) steeper than the diagonal and that hits the top side of the rectangle. Querying on the bottom side
<figure><img src="image_2.png" /><figcaption>**Figure 1:** Preferences of the DMs from the example, serving as ground truth for the elicitation. Marginal values for Price (left), Autonomy (middle), and resulting indifference curves (right).</figcaption></figure>

from the point given by the other DM (in yellow), makes sure to obtain two values $b^1 < b^2 \in \mathcal{X}_j$ such that $b^2 = x_{j,\ell_{j+1}}$, yielding two points on the bottom side of the rectangle.

* Finally, Case 3 covers all situations where both indifference curves are steeper than the diagonal and hit the top side of the rectangle, as illustrated by Fig. 4. Querying from the top left corner ensures getting both answers on the bottom side of the rectangle.

<figure><img src="image_3.png" /><figcaption>**Figure 2:** A successful Single Rectangle query in the space $\mathcal{X}_i \times \mathcal{X}_j$, corresponding to case 1. Colored lines represent DMs' indifference curves.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Figure 4:** Outcome and second query for case 3 of the Single Rectangle Constraint.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 3:** Outcome and second query for case 2 of the Single Rectangle Constraint.</figcaption></figure>

**Exploiting Single-Rectangle Preference Information** Suppose that we have three points in $[x_{i,\ell_i}, x_{i,\ell_i+1}] \times [x_{j,\ell_j}, x_{j,\ell_j+1}]$ $A(A_i, A_j), B(B_i, B_j) \neq A, C(C_i, C_j) \neq A$ such that one DM – say $\kappa \in \{\alpha, \beta\}$– is indifferent between A and B and the other –say $\kappa' \neq \kappa \in \{\alpha, \beta\}$– is indifferent between A and C.

**Play Pattern 1:** to get a Single Rectangle Constraint

**Input:** two criteria $i \neq j$, two interval labels $\ell_i \in [0, L_i - 1]$, $\ell_j \in [0, L_j - 1]$

**Output:** three points A, B, C, $A \neq A$ in $[x_{i,\ell_i}, x_{i,\ell_i+1}] \times [x_{j,\ell_j}, x_{j,\ell_j+1}]$ s.t. one DM is indifferent between A and B and the other is indifferent between A and C

$a^1, a^2 \leftarrow \text{Query } (i: x_{i,\ell_i+1}, j: x_{j,\ell_j}) \sim (i: x_{i,\ell_i}, j: ?)$

if $a^2 \le x_{j,\ell_j+1}$ **then** /* Case 1

return $(x_{i,\ell_i+1}, x_{j,\ell_j}), (x_{i,\ell_i}, a^1), (x_{i,\ell_i}, a^2)$;

if $a^1 \le x_{j,\ell_j+1}$ **then** /* Case 2

$b^1, b^2 \leftarrow \text{Query } (i: x_{i,\ell_i}, j: a^1) \sim (j: x_{j,\ell_j}, i: ?)$

return $(x_{i,\ell_i}, a^1), (b^1, x_{j,\ell_j}), (b^2, x_{j,\ell_j})$;

else /* Case 3

$b^1, b^2 \leftarrow \text{Query } (i: x_{i,\ell_i}, j: x_{j,\ell_j+1}) \sim (j: x_{j,\ell_j}, i: ?)$

return $(x_{i,\ell_i}, x_{j,\ell_j+1}), (b^1, x_{j,\ell_j}), (b^2, x_{j,\ell_j})$;
$$ \left\{ \begin{array}{l} (A_i, A_j) \sim_{\kappa} (B_i, B_j) \\ (A_i, A_j) \sim_{\kappa'} (C_i, C_j) \end{array} \right. \Leftrightarrow \left\{ \begin{array}{l} u_{\kappa}((A_i, A_j)) = u_{\kappa}((B_i, B_j)) \\ u_{\kappa'}((A_i, A_j)) = u_{\kappa'}((C_i, C_j)) \end{array} \right. $$

The additive value function is such that $u_{\kappa}((A_i, A_j)) = u_{\kappa}^k(x_{i,\ell_i}) + \gamma_{i,\ell_i+1}^k \cdot (A_i - x_{i,\ell_i}) + u_{\kappa'}^k(x_{j,\ell_j}) + \gamma_{j,\ell_j+1}^k \cdot (A_j - x_{j,\ell_j})$, with a similar form for $u_{\kappa'}$. More details are shared in Appendix A. It leads to:

$$ \left\{ \begin{array}{l} \gamma_{j, \ell_j}^{\kappa} = \Lambda_{\kappa} \cdot \gamma_{i, \ell_i}^{\kappa} \\ \gamma_{j, \ell_j}^{\kappa'} = \Lambda_{\kappa'} \cdot \gamma_{i, \ell_i}^{\kappa'} \end{array} \right. \quad \text{with:} \quad \left\{ \begin{array}{l} \Lambda_{\kappa} = \frac{B_i - A_i}{A_j - B_j} \\ \Lambda_{\kappa'} = \frac{C_i - A_i}{A_j - C_j} \end{array} \right. $$

If $B = C$ then $\gamma_i^\alpha / \gamma_j^\alpha = \gamma_i^\beta / \gamma_j^\beta$. Otherwise, let $k \in \{0, 1\}$ such that $k = 0$ iff $\alpha$ answers $B$ and $\beta$ answers $C$. We have:

$$ \left\{ \begin{array}{l} \gamma_{j, \ell_j}^{\alpha} = (k \cdot \Lambda_{\kappa} + (1-k) \cdot \Lambda_{\kappa'}) \cdot \gamma_{i, \ell_i}^{\alpha} \\ \gamma_{j, \ell_j}^{\beta} = ((1-k) \cdot \Lambda_{\kappa} + k \cdot \Lambda_{\kappa'}) \cdot \gamma_{i, \ell_i}^{\beta} \end{array} \right. \quad (2) $$

## 4.2 Obtaining Neighboring-Rectangles Preference Information

We are also interested in collecting preference information in the form of anonymized indifference statements $A \sim_{\kappa} B$, $A \sim_{\kappa'} C$ between points lying in adjacent rectangles, i.e. $A \in \mathcal{R}_{\ell_i, \ell_j-1}$ and $B, C \in \mathcal{R}_{\ell_i, \ell_j+1}$. Play Pattern 2 ensures this information can be obtained with a finite number of queries.

The play pattern is based on the iterated uses of queries of the form $(i: x_{i,\ell_i} + \delta_i, j: \frac{1}{2}(x_{j,\ell_j-1} + x_{j,\ell_j}) + \frac{\lambda}{2}\delta_i) \sim (i: x_{i,\ell_i}, j: ?)$). The values $\lambda$ and $\delta_i$ are initialized so that the first query point lies at the center of rectangle $\mathcal{R}_{\ell_i, \ell_j}$. These values are then adjusted according to the answers until both answers are in the sought rectangle and the pattern terminates, as illustrated by Figure 5. Case 1 corresponds to the situation where both answers are above $x_{j,\ell_j}$ but at least one is not below $x_{j,\ell_j+1}$. In such a case, $\delta_i$ is divided by two and the query point moves left (see Figure 6)- along a line passing through the point $(x_{i,\ell_i}, x_{j,\ell_j})$ whose slope is controlled by $\lambda$. The variable $\lambda$ is initialized so that this line coincides with the diagonal of the lower rectangle. If, at the first query, the lowest answer is below $x_{j,\ell_j}$ we obtain single-rectangle preference information for one of the DMs and can compute the actual value of the slope of its indifference curve, which is stored in $\lambda$ (Case 2, illustrated by Figure 7). In effect, the querying point moves towards the upper-left vertex of the lower rectangle along a more gentle slope, ensuring Case 2 never occurs again.

**Exploiting Neighboring-Rectangles Preference Information.** Suppose that we have $A(A_i, A_j)$ in $[x_{i,\ell_i}, x_{i,\ell_i+1}] \times [x_{j,\ell_j-1}, x_{j,\ell_j}]$ and $B(B_i, B_j) \neq A$, $C(C_i, C_j) \neq A$ in $[x_{i,\ell_i}, x_{i,\ell_i+1}] \times [x_{j,\ell_j}, x_{j,\ell_j+1}]$ such that one DM is indifferent between $A$ and $B$ and the other, is indifferent between $A$ and $C$. At this point, we attribute $B$ to the DM $\kappa$ and $C$ to $\kappa'$, but we do not know whether $(\kappa, \kappa')$ is $(\alpha, \beta)$ or $(\beta, \alpha)$.

$$ \left\{ \begin{array}{l} (A_i, A_j) \sim_{\kappa} (B_i, B_j) \\ (A_i, A_j) \sim_{\kappa'} (C_i, C_j) \end{array} \right. $$

Contrary to the Single Rectangle, we have: $u_j^\kappa(B_j) - u_j^\kappa(A_j) = \gamma_{j, \ell_j+1}^\kappa \cdot (B_j - x_{j, \ell_j}) + \gamma_{j, \ell_j}^\kappa \cdot (x_{j, \ell_j} - A_j)$, leading to:

$$ \left\{ \begin{array}{l} \gamma_{j, \ell_j+1}^{\kappa} = \gamma_{i, \ell_i}^{\kappa} \cdot \Theta_{\kappa} + \gamma_{k, \ell_j}^{\kappa} \cdot \Phi_{\kappa} \\ \gamma_{j, \ell_j+1}^{\kappa'} = \gamma_{i, \ell_i}^{\kappa'} \cdot \Theta_{\kappa'} + \gamma_{j, \ell_j}^{\kappa'} \cdot \Phi_{\kappa'} \end{array} \right. $$

### Play Pattern 2: to get a Neighboring Rectangles Constraint

**Input:** two criteria $i \neq j$, two interval labels $\ell_i \in [1, L_i]$, $\ell_j \in [1, L_j - 1]$

**Output:** three points $A, B, C$ with $A \in [x_{i, \ell_i}, x_{i, \ell_i+1}] \times [x_{j, \ell_j-1}, x_{j, \ell_j}]$ and $B, C \in [x_{i, \ell_i}, x_{i, \ell_i+1}] \times [x_{j, \ell_j}, x_{j, \ell_j+1}]$ such that one DM is indifferent between $A$ and $B$ and the other is indifferent between $A$ and $C$

$\delta_i \leftarrow \frac{1}{2} \cdot (x_{i, \ell_i+1} - x_{i, \ell_i});$

$\lambda \leftarrow (x_{j, \ell_j} - x_{j, \ell_j-1})/(2\delta_i);$

$a^1, a^2 \leftarrow \text{Query } (x_{i, \ell_i} + \delta_i, x_{j, \ell_j-1} - \lambda \cdot \delta_i) \sim (x_{i, \ell_i}, ?);$

while not $(a^1 > x_{j, \ell_j} \text{ and } a^2 \le x_{j, \ell_j+1}) \text{ do}$

if $a^1 > x_{j, \ell_j}$ then $\delta_i \leftarrow \delta_i/2$; /* Case 1

else $\lambda \leftarrow (x_{j, \ell_j} - a^1)/(2\delta_i);$ /* Case 2

$a^1, a^2 \leftarrow \text{Query } (x_{i, \ell_i} + \delta_i, x_{j, \ell_j} - \lambda \cdot \delta_i) \sim (x_{i, \ell_i}, ?);$

end

return $(x_{i, \ell_i} + \delta_i, x_{j, \ell_j} - \lambda \cdot \delta_i), (x_{i, \ell_i}, a^1), (x_{i, \ell_i}, a^2);$

$$ \text{with:} \quad \left\{ \begin{array}{l} \Theta_{\kappa} = \frac{A_i - B_i}{B_j - x_{j, \ell_j}}; \quad \Theta_{\kappa'} = \frac{A_i - C_i}{C_j - x_{j, \ell_j}} \\ \Phi_{\kappa} = \frac{A_j - x_{j, \ell_j}}{B_j - x_{j, \ell_j}}; \quad \Phi_{\kappa'} = \frac{A_j - x_{j, \ell_j}}{C_j - x_{j, \ell_j}} \end{array} \right. $$

Let $k \in \{0, 1\}$ such that $k = 0$ iff $\alpha$ answers $B$ and $\beta$ answers $C$:

$$ \left\{ \begin{array}{l} \gamma_{j, \ell_j+1}^{\alpha} = \gamma_{i, \ell_i}^{\alpha} (k\Theta_{\kappa} + (1-k)\Theta_{\kappa'}) + \gamma_{j, \ell_j}^{\alpha} (k\Phi_{\kappa} + (1-k)\Phi_{\kappa'}) \\ \gamma_{j, \ell_j+1}^{\beta} = \gamma_{i, \ell_i}^{\beta} ((1-k)\Theta_{\kappa} + k\Theta_{\kappa'}) + \gamma_{j, \ell_j}^{\beta} ((1-k)\Phi_{\kappa} + k\Phi_{\kappa'}) \end{array} \right. \quad (3) $$

<figure><img src="image_6.png" /><figcaption>**Figure 5:** Example of a Query with a neighboring rectangles constraint. Colored lines represent the indifference curve of each DM.</figcaption></figure>

## 5 Propagation Patterns

At this point, each low-level pattern introduced in Section 4 yields preference information about the slopes of the indifference curves. They are exploited by introducing a binary variable $k$ representing two possible worlds per query, according to which DM provide each answer. Thus, carelessly chaining $n$ of those patterns opens $2^n$ possible worlds, as illustrated by Figure 8. To avoid this combinatorial explosion, we devise two higher-level sequences of moves that aim
<figure><img src="image_7.png" /><figcaption>Figure 6: Outcome and second query for case 1 of Play Pattern 2.</figcaption></figure>

<figure><img src="image_8.png" /></figure>

Figure 7: Outcome and second query for case 2 of Play Pattern 2, effectively pruning the worlds corresponding to an incorrect assignment. These sequences differ in their requirements: in Section 5.1 we assume we know the slopes of the marginal value functions of each DM on two intervals of $\mathcal{X}_i$ and we obtain the slopes and their assignment to each DM on an interval of the other criterion; in Section 5.2 we assume we know the slopes of the marginal value functions of each DM on an interval of $\mathcal{X}_i$ and an interval of $\mathcal{X}_j$, and we obtain the slopes and their assignment to each DM on a neighboring interval.

## 5.1 Identification with two single rectangle constraints

**Play Pattern 3: Identification with two Single-Rectangle Constraints**

**Input:** A criterion $j$ and an interval labels $\ell_j \in [1, L_j]$; a second criterion $i \neq j$, and two interval labels $\ell_i \neq \ell'_i \in [1, L_i]$ such that $\gamma_{i, \ell_i}^{\alpha}, \gamma_{i, \ell_i}^{\beta}, \gamma_{i, \ell'_i}^{\alpha}$ and $\gamma_{i, \ell'_i}^{\beta}$ are known.

**Output:** the identified values of $\gamma_{j, \ell_j}^{\alpha}, \gamma_{j, \ell_j}^{\beta}$

$A, B, C \leftarrow \text{Play Pattern 1}((i, j), (\ell_i, \ell_j));$

$A', B', C' \leftarrow \text{Play Pattern 1}((i, j), (\ell'_i, \ell_j));$

System 1a $\leftarrow$ Equation 2 and $A, B, C$;

System 1b $\leftarrow$ Equation 2 and $A', B', C'$;

$\gamma_{j, \ell_j}^{\alpha}, \gamma_{j, \ell_j}^{\beta} \leftarrow \text{Solve } (1a) = (1b), \text{see Appendix B;}$

return $\gamma_{j, \ell_j}^{\alpha}, \gamma_{j, \ell_j}^{\beta}$;

Our play patterns have been defined to be able to identify the slopes of the value functions of both DMs on a specific interval $\ell_j$ of a criterion $j$. The idea is to use two intervals $\ell_i \neq \ell'_i$ on a criterion $i$ for which the value functions are known and with $\gamma_{i, \ell_i}^{\alpha}/\gamma_{i, \ell'_i}^{\alpha} \neq \gamma_{i, \ell_i}^{\beta}/\gamma_{i, \ell'_i}^{\beta}$. Using Play Pattern 1, on $[x_i, \ell_i, x_i, \ell_i+1] \times [x_j, \ell_j, x_j, \ell_j+1]$, we obtain a system, from Equation 2 for $\gamma_{\alpha, j, \ell_j}$ and $\gamma_{\beta, j, \ell_j}$. Doing

the same for $[x_i, \ell'_i, x_i, \ell'_i+1] \times [x_j, \ell_j, x_j, \ell_j]$ we get a second system with different expression for these two slopes. Equating these expressions, we obtain two equations with two variables $k, k'$:

$$ \left\{ \begin{aligned} & (k\Lambda_{\kappa} + (1-k)\Lambda_{\kappa'})\gamma_{i, \ell_i}^{\alpha} = (k'\Lambda'_{\kappa} + (1-k')\Lambda'_{\kappa'})\gamma_{i, \ell'_i}^{\alpha} \\ & ((1-k)\Lambda_{\kappa} + k\Lambda_{\kappa'})\gamma_{i, \ell_i}^{\beta} = ((1-k')\Lambda'_{\kappa} + k'\Lambda'_{\kappa'})\gamma_{i, \ell'_i}^{\beta} \end{aligned} \right. \quad (4) $$

This system is non-singular. Its resolution yields the values of variables $k$ and $k'$ and the respective slopes of the marginal value functions of each DM. Details can be found in Appendix B and the described procedure is summarized in Algorithm 3. This result means that once one marginal value function has been identified on at least two distinct intervals, it is possible to generalize the identifiability of any interval on another criterion.

## 5.2 Identification with Single Rectangle and a Neighboring Rectangles queries

**Play Pattern 4: Identification with a Single-Rectangle and a Neighboring-Rectangles Constraints**

**Input:** A criterion $j$ and an interval labels $\ell_j \in [2, L_j]$ for which $\gamma_{j, \ell_j-1}^{\alpha}$ and $\gamma_{j, \ell_j-1}^{\beta}$ are known; a second criterion $i \neq j$ and an interval label $\ell_i \in [1, L_i]$ s.t. $\gamma_{i, \ell_i}^{\alpha}$ and $\gamma_{i, \ell_i}^{\beta}$ are known.

**Output:** the identified values of $\gamma_{j, \ell_j}^{\alpha}, \gamma_{j, \ell_j}^{\beta}$

$A, B, C \leftarrow \text{Play Pattern 1}((i, j), (\ell_i, \ell_j));$

$A', B', C' \leftarrow \text{Play Pattern 2}((i, j), (\ell_i, \ell_j-1));$

System 1a $\leftarrow$ Equation 2 and $A, B, C$;

System 1b $\leftarrow$ Equation 3 and $A', B', C'$;

$\gamma_{j, \ell_j}^{\alpha}, \gamma_{j, \ell_j}^{\beta} \leftarrow \text{Solve } (1a) = (1b), \text{see Appendix C;}$

return $\gamma_{j, \ell_j}^{\alpha}, \gamma_{j, \ell_j}^{\beta}$;

Our second identification pattern, described in Play Pattern 4, is relatively similar to the first one. The difference lies in the use of a neighboring interval of the criterion interval to be elicited instead of a second interval on the other criterion. Therefore, we will make use of one - instead of two - Single Rectangle query and one Neighboring Rectangles query. Considering an interval labeled $\ell_j - 1$ on a criterion $j$ that has been elicited, we choose an additional interval $\ell_i$ on a different criterion $i$ that has also been elicited and for which $\gamma_{i, \ell_i}^{\alpha}/\gamma_{j, \ell_j-1}^{\alpha} \neq \gamma_{i, \ell_i}^{\beta}/\gamma_{j, \ell_j-1}^{\beta}$. We use the Play Pattern 1 on $[x_j, \ell_j, x_j, \ell_j+1] \times [x_i, \ell_i, x_i, \ell_i+1]$ to obtain the triplet $(A, B, C)$ and Play Pattern 2 on $[x_j, \ell_j-1, x_j, \ell_j+1] \times [x_i, \ell_i, x_i, \ell_i+1]$ to obtain the triplet $(A', B', C')$. It leads to two systems from Equations 2, 3. These systems express different equations for $\gamma_{j, \ell_j}^{\alpha}$ and $\gamma_{j, \ell_j}^{\beta}$ and therefore can be reduced to:

$$ \left\{ \begin{aligned} & (k\Lambda_{\kappa} + (1-k)\Lambda_{\kappa'})\gamma_{i, \ell_i}^{\alpha} = \gamma_{i, \ell_i}^{\alpha} (k'\Theta'_{\kappa} + (1-k')\Theta'_{\kappa'}) \\ & + \gamma_{j, \ell_j-1}^{\alpha} (k'\Phi'_{\kappa} + (1-k')\Phi'_{\kappa'}) \\ & ((1-k)\Lambda_{\kappa} + k\Lambda_{\kappa'})\gamma_{i, \ell_i}^{\beta} = \gamma_{i, \ell_i}^{\beta} (k'\Theta'_{\kappa} + (1-k')\Theta'_{\kappa'}) \\ & + \gamma_{j, \ell_j-1}^{\beta} (k'\Phi'_{\kappa} + (1-k')\Phi'_{\kappa'}) \end{aligned} \right. \quad (5) $$

This system with two equations and two unknown variables $k, k'$ can be solved. With these values, we can finally obtain the values of $\gamma_{j, \ell_j}^{\alpha}$ and $\gamma_{j, \ell_j}^{\beta}$ using Equation 2 for example.
<figure><img src="image_9.png" /><figcaption>Figure 8: Possible value functions after Play Pattern 1. The colored lines represent the marginal value functions of each DM.</figcaption></figure>

# 6 General Elicitation Procedure

We propose a general elicitation procedure that can be used in order to identify a set of two DMs in our described setup. The procedure can be found in the Algorithm 5 and is described in the following sections. A Python implementation and a few examples will be shared in a GitHub repository shared upon acceptance.

<caption>**Algorithm 5: General Strategy for the Elicitation**</caption>

**Initialize criterion i:**
Set $\gamma_{i,\ell_i}^{\alpha} = \gamma_{i,\ell_i}^{\beta} = 1$ for all DMs on $[x_i, \ell_i-1, x_i, \ell_i]$
**Initialize criterion j:**
Play Pattern 1 on $[x_i, \ell_i-1, x_i, \ell_i] \times [x_j, \ell_j, x_j, \ell_j+1]$;
Attribute slopes $\gamma_{j,\ell_j}^{\alpha}, \gamma_{j,\ell_j}^{\beta}$ on $[x_j, \ell_j-1, x_j, \ell_j]$;
**Fully Elicit Criterion i, j:**
for $\ell'_j \in [\ell_j, L_j]$
Play Pattern 4 on $[x_{j,\ell'_j}, x_{j,\ell'_j+1}] \times [x_{i,\ell_i-1}, x_{i,\ell_i}]$;
Solve Eq. 5 and deduct slopes $\gamma_{j,\ell'_j}^{\alpha}, \gamma_{j,\ell'_j}^{\beta}$;
for $\ell'_i \in [\ell_i, L_i]$
Play Pattern 4 on $[x_{i,\ell'_i}, x_{i,\ell'_i+1}] \times [x_{j,\ell_j-1}, x_{j,\ell_j}]$;
Solve Eq. 5 and deduct slopes $\gamma_{i,\ell'_i}^{\alpha}, \gamma_{i,\ell'_i}^{\beta}$;
**for criterion j' $\in \mathcal{N}, j' \neq i, j$**
**Initialize criterion j':**
Play Pattern 3 on $[x_{j',0}, x_{j',1}] \times [x_{i,\ell_i}, x_{i,\ell_i+1}]$;
Solve Eq. 4 and deduct slopes $\gamma_{j',1}^{\alpha}, \gamma_{j',1}^{\beta}$;
**Fully Elicit Criterion j':**
for $\ell'_{j'} \in [1, L_{j'}]$
Play Pattern 4 on $[x_{j',\ell'_{j'}}, x_{j',\ell'_{j'}+1}] \times [x_{i,\ell_i}, x_{i,\ell_i+1}]$;
Solve Eq. 5 and deduct slopes $\gamma_{j',\ell'_{j'}}^{\alpha}, \gamma_{j',\ell'_{j'}}^{\beta}$;

## 6.1 Initialization

We begin by choosing two criteria $i \neq j$ and a rectangle $\mathcal{R}_{\ell_i, \ell_j} \subset \mathcal{X}_i \times \mathcal{X}_j$ and following Play Pattern 1 so as to obtain Single Rectangle preference information describing two intersecting indifference curves (i.e. distinct points B and C). If this is not possible, the DMs have the exact same preferences and the identification task is over. Otherwise, we set:

$$ \gamma_{i, \ell_i}^{\alpha} = 1; \quad \gamma_{j, \ell_j}^{\alpha} = \frac{B_i - A_i}{A_j - B_j}; \quad \gamma_{i, \ell_i}^{\beta} = 1; \quad \gamma_{j, \ell_j}^{\beta} = \frac{C_i - A_i}{A_j - C_j} $$

Indeed, without loss of generality, we can arbitrarily assign the answer B to the DM $\alpha$ (resp. C to $\beta$) and normalize the UTA model of

$\alpha$ (resp. $\beta$) so that it has unit slope on $[x_i, \ell_i-1, x_i, \ell_i]^{1}$.

In order to find a suitable rectangle, we traverse the intervals in $\mathcal{X}_i$ and $\mathcal{X}_j$ in increasing order. Thus, when one is found, all rectangles with lower indices have unanimous DMs and can be identified at this point.

## 6.2 Full elicitation of criteria i and j

It is now possible to use the Play Pattern 4 to elicit interval by interval the criteria $i$ and $j$, in increasing order. Let us consider that the criterion $i$ has been elicited up to the $\ell$-th interval, we formulate:

* a Single Rectangle Query on $[x_{j,\ell_j-1}, x_{j,\ell_j}] \times [x_{i,\ell+1}, x_{i,\ell+2}]$

* a Neighboring Rectangles Query on $[x_{j,\ell_j-1}, x_{j,\ell_j}] \times [x_{i,\ell}, x_{i,\ell+2}]$

Following Equation 5, we are able to obtain the slopes values $\gamma_{i,\ell+1}^{\alpha}$ and $\gamma_{i,\ell+1}^{\beta}$. Using this procedure iteratively for $2 \le \ell \le L_i$, it is possible to fully elicit the criterion $i$.

The same procedure can be applied for criterion $j$. The only change needed is the use of the interval $[x_{j,\ell_j-1}, x_{j,\ell_j}]$ instead of $[x_{i,\ell_i-1}, x_{i,\ell_i}]$ for the different queries. The iterative steps for two criteria are illustrated in Figure 9, assuming initialization occurs in the rectangle $[x_{i,0}, x_{i,1}] \times [x_{j,0}, x_{j,1}]$. Observe it is necessary and sufficient to exploit preference information concerning exactly one rectangle per column and per row (i.e. $L_i + L_j - 1$ rectangles) to fully identify $u_i^{\alpha}, u_j^{\alpha}, u_i^{\beta}, u_j^{\beta}$.

## 6.3 Elicitation of the remaining criteria

The remaining criteria can finally be elicited independently. For a criterion $j' \notin \{i, j\}$, an initialization is done in order to get the slopes on the first interval, following the Play Pattern 3:

* a Single Rectangle Query on $[x_{i,\ell_i-1}, x_{i,\ell_i}] \times [x_{j',0}, x_{j',1}]$

* a Single Rectangle Query on $[x_{i,\ell_i-1}, x_{i,\ell_i}] \times [x_{j',0}, x_{j',1}]$

Following Equation 4, we obtain the slopes values $\gamma_{i,1}^{\alpha}$ and $\gamma_{i,1}^{\beta}$.

At this point, it is possible to use the procedure for criterion $i$ or $j$ described in Section 6.2 to fully elicit the criterion $j'$.

<figure><img src="image_10.png" /><figcaption>Figure 9: General Procedure sequencing for the elicitation of two different DMs on two criteria.</figcaption></figure>

<footnote n="1">¹ This normalization is licit but not standard in MAVT. The usual convention of having values ranging from 0 to 1 can be easily restored after the complete identification of the two AVF.</footnote>
## Conclusion

In this paper, we study the identifiability of two additive piecewise linear value functions using matching queries. Such queries provide two answers (those of the two additive models), but without specifying to which model each answer corresponds. We provide a systematic elicitation procedure that makes it possible to obtain the two additive piecewise linear models from a finite sequence of matching queries, hence proving identifiability.

This work leaves open questions that should be studied in further research. First, our work is limited to additive value functions for which the marginals are piecewise linear; it would be interesting to study this identifiability problem when marginals can be any monotonically increasing function. A second extension relates to the fact that our work accounts for two DMs only; extending Single- and Neighboring-Rectangle queries to more than two DMs seems straightforward, but defining an elicitation procedure to identify *n* additive models (*n* > 2) would be of great interest. Finally, the positive results concerning the identifiability of such model could help to analyze the behavior of statistical learning algorithms.

## References

[1] D. Angluin. Queries revisited. *Theoretical Computer Science*, 313(2): 175–194, 2004. ISSN 0304-3975. Algorithmic Learning Theory.

[2] V. Auriau, K. Belahcène, E. Malherbe, and V. Mousseau. Learning multiple multicriteria additive models from heterogeneous preferences. In R. Freeman and N. Mattei, editors, *Algorithmic Decision Theory*, pages 207–224. Springer, 2025. ISBN 978-3-031-73903-3.

[3] D. Bouyssou and M. Pirlot. Conjoint measurement tools for mcdm. In S. Greco, M. Ehrgott, and J. R. Figueira, editors, *Multiple Criteria Decision Analysis: State of the Art Surveys*, pages 97–151. Springer New York, 2016.

[4] D. Braziunas and C. Boutilier. Preference elicitation and generalized additive utility. In *AAAI*, volume 21. Boston, MA, 2006.

[5] R. Bresson, J. Cohen, E. Hüllermeier, C. Labreuche, and M. Sebag. On the Identifiability of Hierarchical Decision Models. In *Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning*, pages 151–162, 11 2021.

[6] N. Chetcuti-Sperandio, F. Delorme, and S. Lagrue. On aggregate and comparison functions for Motus/Lingo playing. *International Computer Games Association Journal*, 40(3):258–268, 2018.

[7] S. Greco, V. Mousseau, and R. Słowiński. Ordinal regression revisited: multiple criteria ranking using a set of additive value functions. *European Journal of Operational Research*, 191(2):416–436, 2008.

[8] E. Jacquet-Lagrèze and Y. Siskos. Assessing a set of additive utility functions for multicriteria decision making: the UTA method. *European Journal of Operational Research*, 10:151–164, 1982.

[9] E. Jacquet-Lagrèze and Y. Siskos. Preference disaggregation: 20 years of MCDA experience. *European Journal of Operational Research*, 130 (2):233–245, 2001.

[10] R. L. Keeney and H. Raiffa. *Decisions with multiple objectives: Preferences and value tradeoffs*. John Wiley & Sons, 1976.

[11] D. Krantz, R. Luce, P. Suppes, and A. Tversky. *Foundations of Measurement - Volume 1: Additive and Polynomial Representations*. Academic Press, Incorporated, 1971.

[12] C. Labreuche, E. Hüllermeier, P. Vojtas, and A. Fallah Tehrani. On the identifiability of models in multi-criteria preference learning. In R. Busa-Fekete, E. Hüllermeier, V. Mousseau, and K. E. Pfannschmidt, editors, *Proceedings DA2PL 2016, Euro Mini Conference from Multiple Criteria Decision Aid to Preference Learning*, 2016.

[13] Z.-Y. Ran and B.-G. Hu. Parameter identifiability in statistical machine learning: A review. *Neural Computation*, 29(5):1151–1203, 05 2017. ISSN 0899-7667.

[14] K. Regan and C. Boutilier. Eliciting additive reward functions for markov decision processes. In *IJCAI Proceedings-International Joint Conference on Artificial Intelligence*, volume 22, page 2159, 2011.

[15] S. Shalev-Shwartz and S. Ben-David. *Understanding Machine Learning - From Theory to Algorithms*. Cambridge University Press, 2014. ISBN 978-1-10-705713-5.

[16] D. von Winterfeldt and W. Edwards. *Decision analysis and behavioral research*. Cambridge University Press, Cambridge, 1986.
A Details for Equation 2

$$
\left\{
\begin{array}{l}
(A_i, A_j) \sim_{\kappa} (B_i, B_j) \\
(A_i, A_j) \sim_{\kappa'} (C_i, C_j)
\end{array}
\right.
\Leftrightarrow
\left\{
\begin{array}{l}
u_{\kappa}((A_i, A_j)) = u_{\kappa}((B_i, B_j)) \\
u_{\kappa'}((A_i, A_j)) = u_{\kappa'}((C_i, C_j))
\end{array}
\right.
$$

Since $A_i, B_i, C_i \in [x_i, \ell_i, x_i, \ell_i+1]$ and $A_j, B_j, C_j \in [x_i, \ell_j, x_j, \ell_j+1]$:

$$
\begin{align*}
& \left\{
  \begin{array}{@{}l@{}}
    u_i^{\kappa}(x_i, \ell_i) + \gamma_{i, \ell_i+1}^{\kappa} \cdot (A_i - x_i, \ell_i) + u_j^{\kappa}(x_j, \ell_j) + \gamma_{j, \ell_j+1}^{\kappa} \cdot (A_j - x_j, \ell_j) = u_i^{\kappa}(x_i, \ell_i) + \gamma_{i, \ell_i+1}^{\kappa} \cdot (B_i - x_i, \ell_i) + u_j^{\kappa}(x_j, \ell_j) + \gamma_{j, \ell_j+1}^{\kappa} \cdot (B_j - x_j, \ell_j) \\
    u_i^{\kappa'}(x_i, \ell_i) + \gamma_{i, \ell_i+1}^{\kappa'} \cdot (A_i - x_i, \ell_i) + u_j^{\kappa'}(x_j, \ell_j) + \gamma_{j, \ell_j+1}^{\kappa'} \cdot (A_j - x_j, \ell_j) = u_i^{\kappa'}(x_i, \ell_i) + \gamma_{i, \ell_i+1}^{\kappa'} \cdot (C_i - x_i, \ell_i) + u_j^{\kappa'}(x_j, \ell_j) + \gamma_{j, \ell_j+1}^{\kappa'} \cdot (C_j - x_j, \ell_j)
  \end{array}
\right\} \\
\Leftrightarrow & \left\{
  \begin{array}{@{}l@{}}
    \gamma_{i, \ell_i+1}^{\kappa} \cdot (A_i - B_i) + \gamma_{j, \ell_i+1}^{\kappa} \cdot (A_j - B_j) = 0 \\
    \gamma_{i, \ell_i+1}^{\kappa'} \cdot (A_i - C_i) + \gamma_{j, \ell_i+1}^{\kappa'} \cdot (A_j - C_j) = 0
  \end{array}
\right.
\end{align*}
$$
Equation 2
$$
\Leftrightarrow
$$

B Condition of unicity of the system resulting from Play Pattern 3

Using Play Pattern 1, on $[x_i, \ell_i, x_i, \ell_i+1] \times [x_j, \ell_j, x_j, \ell_j+1]$, we obtain a system, from Equation 2:

$$
\left\{
\begin{aligned}
\gamma_{j, \ell_j}^{\alpha} &= (k \cdot \Lambda_{\kappa} + (1-k) \cdot \Lambda_{\kappa'}) \cdot \gamma_{i, \ell_i}^{\alpha} \\
\gamma_{j, \ell_j}^{\beta} &= ((1-k) \cdot \Lambda_{\kappa} + k \cdot \Lambda_{\kappa'}) \cdot \gamma_{i, \ell_i}^{\beta}
\end{aligned}
\right.
\qquad (6)
$$

Following the same procedure with $[x_i, \ell_i', x_i, \ell_i'+1] \times [x_j, \ell_j, x_j, \ell_j]$ we get a second system with different expression for our two slopes:

$$
\left\{
\begin{aligned}
\gamma_{i, \ell_i}^{\alpha} &= (k' \cdot \Lambda'_{\kappa'} + (1-k') \cdot \Lambda'_{\kappa'}) \cdot \gamma_{j, \ell_j}^{\alpha} \\
\gamma_{i, \ell_i}^{\beta} &= ((1-k') \cdot \Lambda'_{\kappa} + k' \cdot \Lambda'_{\kappa'}) \cdot \gamma_{j, \ell_j}^{\beta}
\end{aligned}
\right.
\qquad (7)
$$

Equating the two systems, we obtain two equations with two variables k, k', which we can solve:

$$
\left\{
\begin{array}{l}
(k\Lambda_{\kappa} + (1-k)\Lambda_{\kappa'}) \gamma_{i, \ell_i}^{\alpha} = (k'\Lambda'_{\kappa} + (1-k')\Lambda'_{\kappa'}) \gamma_{i, \ell_i'}^{\alpha} \\
((1-k)\Lambda_{\kappa} + k\Lambda_{\kappa'}) \gamma_{i, \ell_i}^{\beta} = ((1-k')\Lambda'_{\kappa} + k'\Lambda'_{\kappa'}) \gamma_{i, \ell_i'}^{\beta}
\end{array}
\right.
\qquad (8)
$$
$$
\Leftrightarrow \left\{
\begin{array}{l}
[k(\Lambda_{\kappa} - \Lambda_{\kappa'}) + \Lambda_{\kappa'}] \gamma_{i, \ell_i}^{\alpha} = [k(\Lambda'_{\kappa} - \Lambda'_{\kappa'}) + \Lambda'_{\kappa'}] \gamma_{i, \ell_i'}^{\alpha} \\
[k(\Lambda_{\kappa'} - \Lambda_{\kappa}) + \Lambda_{\kappa}] \gamma^{\beta} i, \ell_j = [k(\Lambda'_{\kappa'} - \Lambda'_{\kappa}) + \Lambda'_{\kappa}] \gamma^{\beta}
\end{array}
\right.
\qquad (9)
$$

If the equations are linearly correlated, it means that the coefficients in k, k' are correlated between the equations. Differently said, it would mean that $\exists z \in \mathbb{R}$ such that:

$$
\left\{
\begin{array}{l}
(\Lambda_{\kappa} - \Lambda_{\kappa'}) \gamma_{i, \ell_i}^{\alpha} = z \cdot (\Lambda_{\kappa'} - \Lambda_{\kappa}) \gamma_{i, \ell_i}^{\beta} \\
(\Lambda'_{\kappa} - \Lambda'_{\kappa}) \gamma^{\beta} i, \ell_i' = z \cdot (\Lambda'_{\kappa} - \Lambda'_{\kappa'}) \gamma_{i, \ell_i'}^{\alpha} \\
\hfill \Leftrightarrow \\
\gamma_{i, \ell_i}^{\alpha} = -z \cdot \gamma_{i, \ell_i}^{\beta} \\
\gamma_{i, \ell_i'}^{\beta} = -z \cdot \gamma_{i, \ell_i'}^{\alpha}
\end{array}
\right.
$$

The second system holds if the $\Lambda$ values are different at $t$ and $t+1$. Which is the case if the answers of the two DMs are different. It results that the solution of the system can be found and is unique unless:

• the answers from the query $t$ or $t'$ are the same for both DMs

* the slopes ratios of each DM are the same on the two intervals on criterion $i$, $\frac{\gamma_{i, \ell_i}^{\alpha}}{\gamma_{i, \ell_i}^{\alpha} + \gamma_{i, \ell_i}^{\beta}} = \frac{\gamma_{i, \ell_i}^{\beta}}{\gamma_{i, \ell_i}^{\beta} + \gamma_{i, \ell_i}^{\alpha}}$
### C Condition of unicity of the system resulting from Play Pattern 4

Using Play Pattern 1, on $[x_i, \ell_i, x_i, \ell_i+1] \times [x_j, \ell_j, x_j, \ell_j+1]$, we obtain a system, from Equation 2:

$$ 
\left\{ 
\begin{aligned}
\gamma_{j, \ell_j+1}^{\alpha} &= (k \cdot \Lambda_{\kappa} + (1-k) \cdot \Lambda_{\kappa'}) \cdot \gamma_{i, \ell_i}^{\alpha} \\
\gamma_{j, \ell_j+1}^{\beta} &= ((1-k) \cdot \Lambda_{\kappa} + k \cdot \Lambda_{\kappa'}) \cdot \gamma_{i, \ell_i}^{\beta}
\end{aligned}
\right. 
\qquad (10) 
$$

Following Play Pattern 2 with $[x_i, \ell_i, x_i, \ell_i+1] \times [x_j, \ell_j-1, x_j, \ell_j+1]$ we get a second system from Equation 3

$$ 
\left\{ 
\begin{aligned}
\gamma_{j, \ell_j+1}^{\alpha} &= \gamma_{i, \ell_i}^{\alpha} (k' \Theta_{\kappa} + (1-k') \Theta_{\kappa'}) + \gamma_{j, \ell_j}^{\alpha} (k' \Phi_{\kappa} + (1-k') \Phi_{\kappa'}) \\
\gamma_{j, \ell_j+1}^{\beta} &= \gamma_{i, \ell_i}^{\beta} ((1-k') \Theta_{\kappa} + k' \Theta_{\kappa'}) + \gamma_{j, \ell_j}^{\beta} ((1-k') \Phi_{\kappa} + k' \Phi_{\kappa'})
\end{aligned}
\right. 
\qquad (11) 
$$

Equating the two systems, and following Appendix B, we find that if the equations are linearly correlated, it means that the coefficients in $k, k'$ are correlated between the equations. Differently said, it would mean that $\exists z \in \mathbb{R}$ such that:

$$ 
\left\{ 
\begin{aligned}
& (\Lambda_{\kappa} - \Lambda_{\kappa'}) \gamma_{i, \ell_i}^{\alpha} = z \cdot (\Lambda_{\kappa'} - \Lambda_{\kappa}) \gamma_{i, \ell_i}^{\beta} \\
& (\Theta_{\kappa} - \Theta_{\kappa'}) \gamma_{i, \ell_i}^{\alpha} + (\Phi_{\kappa} - \Phi_{\kappa'}) \gamma_{j, \ell_j}^{\alpha} = z \cdot [(\Theta_{\kappa'} - \Theta_{\kappa'}) \gamma_{i, \ell_i}^{\beta} + (\Phi_{\kappa'} - \Phi_{\kappa'}) \gamma_{j, \ell_j}^{\beta}] \\
\Leftrightarrow & \gamma_{i, \ell_i}^{\alpha} = -z \cdot \gamma_{i, \ell_i}^{\beta} \\
& \gamma_{j, \ell_j}^{\alpha} = z \cdot \gamma_{j, \ell_j}^{\beta}
\end{aligned}
\right. 
$$

Similarly to B, we find that the solution of the system is unique unless:

* the answers from the query $t$ or $t'$ are the same for both DMs

* the slopes ratios of each DM are the same on the two intervals on criterion $j$, $\frac{\gamma_{i, \ell_i}^{\alpha}}{\gamma_{i, \ell_i}^{\beta}} = \frac{\gamma_{j, \ell_j}^{\alpha}}{\gamma_{j, \ell_j}^{\beta}}$