Efficient and binary consensus functions on transitively valued relations (Q1059534): Difference between revisions

Given a set S, the consensus problem on S is that of the construction, for any integer v, of a mapping \(\Phi:S^ v\to S\) such that, for any v- tuple \(\eta =(s_ 1,...,s_ v)\in S^ v\), \(s=\Phi (\eta)\) is a good representative of \(\eta\). In order to have that, \(\Phi\) must satisfy some conditions, some of them based on structural properties of S and the others derived from considerations related to a domain of application. Since Arrow's theorem, preference aggregation is a classical consensus problem; many recent works concern consensus of classifications. This paper presents Arrow-like results on sets of transitively valued relations, or fuzzy quasi-orders, on a finite set X. Here, \[ S=\{q\in L^{X\times X}| (\forall x,y,z\in X)q(xz)\leq \max (q(xy),q(yz))\}, \] where \(0\in L\subseteq {\mathbb{R}}^+\). This set, with the pointwise order, has a lattice structure. The main result of the paper gives the general form of consensus functions \(\Phi\) satisfying two axioms adapted from Arrow's ones: \(\Phi =\bigvee^{v}_{i=1}\phi_ i\circ q_ i\), for some reductive and isotone mappings \(\phi_ 1,...,\phi_ v:\) \(L\to L.\) Various consequences of this result are derived by adding further conditions on \(\Phi\), by setting \(L=\{0,1\}\), or by considering restrictions of the domain or the codomain of \(\Phi\). In preference aggregation, results of Arrow (1951), Mas-Collel and Sonnenschein (1972), Brown (1975) and Mirkin (1981) are found again. In classification, one obtains a new result on the consensus of ultrametrics (or dendrograms, an important class of hierarchical classification models), with a result on partitions due to Mirkin (1975), as a special case.