Heehong Yang

Daesan Kim

Jeongsu Kim

Dongseok Moon

Hyun Seok Song

Seunghun Minju Lee

Tai Hyun Hong

Park

Seunghun Hong
email: seunghun@snu.ac.kr

Tai Hyun Park
email: thpark@snu.ac.kr

Nanodisc-Based Bioelectronic Nose Using Olfactory Receptor Produced in Escherichia coli for the Assessment of Death-Associated Odor Cadaverine

Keywords: nanodiscs, bioelectronic nose, field-effect transistor, trace amine-associated receptor, cadaverine

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

G protein-coupled receptors (GPCRs) play important roles in the cellular responses of the human body. Thus, they are significantly involved in many human diseases and are the target of approximately 40% of all modern medicinal drugs. [START_REF] Siehler | Cell-Based Assays in GPCR Drug Discovery[END_REF][START_REF] Drews | Drug Discovery: A Historical Perspective[END_REF] Trace amine-associated receptors (TAARs), a class of GPCR, are conventional amine receptors binding to endogenous compounds structurally related to classical biogenic amines. It has been reported that trace amine-associated receptor 13c (TAAR13c) in the zebrafish (Danio rerio) functions as an olfactory receptor (OR) and has an efficient specificity to the death-associated odor cadaverine (CV). [START_REF] Hussain | High-Affinity Olfactory Receptor for the Death-Associated Odor Cadaverine[END_REF][START_REF] Liberles | Trace Amine-Associated Receptors Are Olfactory Receptors in Vertebrates[END_REF][START_REF] Sharma | Elimination of a Ligand Gating Site Generates a Supersensitive Olfactory Receptor[END_REF][START_REF] Liberles | A Second Class of Chemosensory Receptors in the Olfactory Epithelium[END_REF] CV, generated by bacterial decarboxylation of lysine, is an extremely repulsive odor to humans, among various biogenic amines. In addition, CV is one of the important markers for decayed foods because various kinds of food products contain lysine.

Therefore, it has been suggested that the detection of CV can be applied to various fields of industrial applications and scientific investigations. [START_REF] Hussain | High-Affinity Olfactory Receptor for the Death-Associated Odor Cadaverine[END_REF][START_REF] Liberles | Trace Amine-Associated Receptors: Ligands, Neural Circuits, and Behaviors[END_REF] For the production of recombinant proteins, the Escherichia coli (E. coli) has been widely used as a host cell because of its great advantage in productivity and convenience. However, the production of GPCR in E. coli remains a challenge because of their strong hydrophobicity, a complicated charge distribution and membrane inserting mechanism of bacterial cells. [START_REF] Grisshammer | Overexpression of Integral Membrane Proteins for Structural Studies[END_REF][START_REF] Gafvelin | Topological "Frustration" in Multispanning E. Coli Inner Membrane Proteins[END_REF][START_REF] Yang | Purification and Functional Reconstitution of Human Olfactory Receptor Expressed in Escherichia Coli[END_REF] Among many reconstitution techniques of receptors, nanodiscs (NDs) have been considered the most appropriate tool for GPCR reconstitution. [START_REF] Denisov | Nanodiscs for Structural and Functional Studies of Membrane Proteins[END_REF][START_REF] Serebryany | Artificial Membrane-Like Environments for in Vitro Studies of Purified G-Protein Coupled Receptors[END_REF] NDs are composed of a receptor, a lipid bilayer and membrane scaffold proteins (MSPs), which tightly wrap the edge of the a lipid bilayer, thus NDs can be stable in an aqueous environment [START_REF] Yang | Purification and Functional Reconstitution of Human Olfactory Receptor Expressed in Escherichia Coli[END_REF][START_REF] Serebryany | Artificial Membrane-Like Environments for in Vitro Studies of Purified G-Protein Coupled Receptors[END_REF][START_REF] Goldsmith | Biomimetic Chemical Sensors Using Nanoelectronic Readout of Olfactory Receptor Proteins[END_REF][START_REF] Glück | Nanodiscs Allow the Use of Integral Membrane Proteins as Analytes in Surface Plasmon Resonance Studies[END_REF] and mimic the native structure of the receptor in a cell. [START_REF] Goldsmith | Biomimetic Chemical Sensors Using Nanoelectronic Readout of Olfactory Receptor Proteins[END_REF][START_REF] Glück | Nanodiscs Allow the Use of Integral Membrane Proteins as Analytes in Surface Plasmon Resonance Studies[END_REF] An ND-based biosensor using Sf9 insect cells has also been reported. [START_REF] Goldsmith | Biomimetic Chemical Sensors Using Nanoelectronic Readout of Olfactory Receptor Proteins[END_REF] However, an ND-based biosensor using an E. coli system, which has great advantages in productivity over other systems, has not been previously reported. A carbon nanotube field-effect transistor (CNT-FET) with floating electrodes can exhibit improved performance compared with a conventional CNT-FET. [START_REF] Lee | Floating Electrode Transistor Based on Purified Semiconducting Carbon Nanotubes for High Source-Drain Voltage Operation[END_REF][START_REF] Lee | Discrimination of Umami Tastants Using Floating Electrode-Based Bioelectronic Tongue Mimicking Insect Taste Systems[END_REF] The floating electrode structure on a CNT-FET can enhance the sensitivity of the device via the increased effect of Schottky barrier modulation. The Au floating electrodes also have advantages in the functionalization of specific biomolecules on their surfaces. The surfaces of floating electrodes have larger areas than conventional devices as well as more suitable conditions for the functionalization of biomolecules.

Here, we report the development of an oriented nanodisc-functionalized bioelectronic nose (ONBN) using TAAR13c-embedded nanodiscs (T13NDs) with high selectivity and sensitivity for the detection of CV. The T13NDs using receptors produced in E. coli enable the immobilized receptor to have stability and a natural binding pocket. Moreover, the T13NDs were immobilized on floating electrodes of a CNT-FET in a desired orientation, which increased the total binding sites of T13NDs. As a result, the ONBN exhibited improved performance in terms of sensitivity and selectivity, as well as reliability and reproducibility. Furthermore, the ONBN could distinguish the target molecules in food samples with differing degrees of spoilage. Our approach can offer a useful sensing system toward a practical bioelectronic sensor to enable the detection of death-associated compounds.

RESULTS AND DISCUSSION

Figure 1 depicts the schematic diagram and the predicted electrical response of an ONBN.

A CNT-FET with floating electrodes was fabricated following previously-reported processes.

A detailed method is described in Supporting Information (Figure S1). In brief, CNTs were patterned on a SiO 2 substrate as transistor channels, and then, Pd/Au electrodes were fabricated via thermal evaporation method. Finally, the source and drain electrodes were passivated using a photoresist to avoid a current leakage in an aqueous environment. After the fabrication of the device, T13NDs were immobilized on the Au surfaces of the floating electrodes. In this research, we used the half V5 antibody (Ab) as linker molecules for oriented immobilization of T13NDs on gold floating electrode. It has been reported that halffragment antibodies can be immobilized onto the gold surfaces with an orientation via their native thiol groups. [START_REF] Karyakin | Oriented Immobilization of Antibodies onto the Gold Surfaces Via Their Native Thiol Groups[END_REF] The receptor TAAR13c has a V5 epitope at C-terminal. Therefore, the T13NDs can be immobilized with the desired orientation using half-fragment V5 Ab as a linker. Here, the V5 epitope of T13NDs binds to the half-fragment V5 Ab on the Au surface.

The immobilized T13NDs on the Au surfaces were oriented such that the binding pockets of TAAR13c on the device were on the exposed side. In previous work, devices with randomly immobilized biomolecules also have been reported. [START_REF] Oh | A Carbon Nanotube Metal Semiconductor Field Effect Transistor-Based Biosensor for Detection of Amyloid-Beta in Human Serum[END_REF][START_REF] Lo | Oriented Immobilization of Antibody Fragments on Ni-Decorated Single-Walled Carbon Nanotube Devices[END_REF] However, randomly oriented sensors have a limited capability to bind target molecules. Therefore, ONBNs could provide an ideal method for the detection of specific target molecules.

We used a dual-glo luciferase assay system, which was suitable for the characterization of the TAAR13c in terms of its selectivity, to measure the dose-dependent response of TAA13c expressed in HEK-293 cells (Figure 2a). [START_REF] Zhuang | Evaluating Cell-Surface Expression and Measuring Activation of Mammalian Odorant Receptors in Heterologous Cells[END_REF] TAAR13c-expressed cells exhibited a significant response to CV, but mock vector-transfected cells had no meaningful responses. This supports the conclusion that TAAR13c was successfully expressed in HEK-293 cells (Figure 2a, S2a). Figure 2b shows the selective responses of TAAR13c to 1 μM stimulus of various amines. TAAR13c was co-expressed with RTP1S and G αolf , increasing the level of expression and efficiency of signal transduction. The selective binding properties of TAAR13 were investigated using various amines, which had different amine moieties and structures (Figure S2b). Our results show TAAR13c responded selectively to CV among various amines.

Although putrescine (PT) appeared to stimulate the TAAR13c partially, there were no significant responses. The results are consistent with previous reports that TAAR13c is the most sensitive and selective receptor to CV. [START_REF] Hussain | High-Affinity Olfactory Receptor for the Death-Associated Odor Cadaverine[END_REF][START_REF] Sharma | Elimination of a Ligand Gating Site Generates a Supersensitive Olfactory Receptor[END_REF] Toward a receptor-based research, the TAAR13c expressed in E. coli (Figure 2c) was purified with a high purity and applied to the formation of receptor NDs. The purification and functional reconstitution of GPCRs for the development of receptor-based biosensors were reported previously. [START_REF] Yang | Purification and Functional Reconstitution of Human Olfactory Receptor Expressed in Escherichia Coli[END_REF][START_REF] Song | Solubilization and Purification of a Human Olfactory Receptor from Escherichia Coli[END_REF] For the production of T13NDs, TAAR13c and lipids were mixed as detergent micelles, and then the membrane scaffold protein apolipoprotein A-I (ApoA-I) was added to enclose the lipid/receptor complex. The T13NDs were finally obtained after the removal of detergent using Bio-bead. The bands of TAAR13c in gel staining indicate that TAAR13c was purified with a high purity. Moreover, the observed bands were successfully confirmed as TAAR13c by a western blot analysis using V5 epitope Ab, confirming that TAAR13c was prepared with a high quality.

Dynamic light scattering (DLS) measurement of T13NDs (Figure 2d) indicated that size distribution of optimized T13NDs. For the assembly of the T13NDs, ApoA-I, the representative membrane scaffold protein, was successfully expressed in E. coli and purified with a high purity (Figure S3). After the assembly of the NDs, the ND-complex solutions were subjected to size exclusion chromatography (SEC) for the removal of residual unbound proteins (Figure S4). The fraction of T13NDs from the SEC separation was collected and analyzed by DLS. [START_REF] Imura | Surfactant-Like Properties of an Amphiphilic Α-Helical Peptide Leading to Lipid Nanodisc Formation[END_REF] We have tested various conditions, such as lipid sonication time and protein concentration for the formation of receptor-NDs and found the best choice for the formation of optimized T13NDs (Figure S5). This results in a quite narrow size distribution of T13NDs with ca. 20 nm in diameter (Figure 2d), which is close to the diameter values estimated by FE-SEM images (Figure 2e). These results clearly demonstrate that the T13NDs were successfully self-assembled in homogeneous discoidal shapes.

In order to analyze the affinity of T13NDs with CV, the real-time tryptophan fluorescence of T13NDs was measured (Figure 2f). With the sequential addition of increasing CV amounts up to 7 mM, a significant fluorescence change of T13NDs was displayed. On the other hand, there was no response to the control buffer solution. The T13NDs responded selectively to CV in real-time tryptophan fluorescence (Figure 2g) in comparison with various amines which have different structures and amine moieties. The intrinsic tryptophan fluorescence of T13NDs was significantly quenched only by a stimulus of CV. Many researches have reported that the intrinsic fluorescence of functional receptor is quenched by selective binding of a ligand to the receptor. [START_REF] Yang | Purification and Functional Reconstitution of Human Olfactory Receptor Expressed in Escherichia Coli[END_REF][START_REF] Michalke | Mammalian G Protein-Coupled Receptor Expression in Escherichia Coli: II. Refolding and Biophysical Characterization of Mouse Cannabinoid Receptor 1 and Human Parathyroid Hormone Receptor 1[END_REF][START_REF] Son | A Portable and Multiplexed Bioelectronic Sensor Using Human Olfactory and Taste Receptors[END_REF] Therefore, these results show that the TAAR13c was effectively reconstituted in NDs. Note that the intensity profile of the Au surface was higher than that of the SiO 2 surface as shown in the intensity profile (bottom of Figure 3a). This result indicates that V5 Ab was successfully immobilized on the floating electrodes.

Atomic force microscopy (AFM) images of the T13ND-functionalized floating electrode in liquid environments and corresponding height profile (Figure 3b) shows functionalization of T13NDs on the floating electrode. The left and right images were measured in a tapping mode AFM with scan rates of 0.4 and 0.1 Hz, respectively. The bright or dark regions correspond to T13ND-functionalized floating electrode or CNT channels on SiO 2 substrates.

We can find white spots with their heights of ~10nm correspond to the previously reported height of NDs. [START_REF] Denisov | Nanodiscs for Structural and Functional Studies of Membrane Proteins[END_REF][START_REF] Whorton | Efficient Coupling of Transducin to Monomeric Rhodopsin in a Phospholipid Bilayer[END_REF] Here, because of tip convolution effects, the image of x-y dimension is broader than the original one. [START_REF] Allen | Tip-Radius-Induced Artifacts in AFM Images of Protamine-Complexed DNA Fibers[END_REF][START_REF] Schwarz | Tip Artifacts in Scanning Force Microscopy[END_REF] This result implies the functionalization of T13NDs on the floating electrode. The immobilization of half-V5 Ab using disulfide bonding between the thiol groups of a functionalized Au surface and half-V5 Ab was confirmed via fluorescent microscopy (Figure 3a). Also, the height of T13NDs was similar with previously reported result (Figure 3b). These results clearly indicate that the T13NDs were assembled on the floating electrodes via antibody-antigen interaction which is the highly specific binding reaction. Therefore, we can conclude that T13NDs have the specific orientation on the Au surfaces.

The gate profiles of an ONBN before and after the immobilization of T13NDs (Figure 3c) exhibited typical p-type semiconductor characteristics in both cases, indicating that the transistor characteristics of the ONBN was maintained even after the immobilization of T13NDs on floating electrodes. Note that the electrical currents were reduced by the immobilization of T13NDs. This is presumably because negatively-charged parts of receptors immobilized on floating electrodes caused the gating effect and affected the drain-source currents. [START_REF] Venkatakrishnan | Molecular Signatures of G-Protein-Coupled Receptors[END_REF] The electrical noise characteristics of an ONBN (Figure 3d) could be fitted by a straight line, indicating a typical 1/f noise behavior. The y-axis (S/I 2 ) of graph means the noise power according to the change of current level versus the frequency. The noise amplitude was found to be ~ 10 -6 which was similar to the previously-reported values of clean network-based CNT-FETs without T13NDs. [START_REF] Kim | Large Scale Assembly of Pristine Semiconducting Carbon Nanotube Network-Based Devices Exhibiting Intrinsic Characteristics[END_REF][START_REF] Soliveres | 1∕ F Noise and Percolation in Carbon Nanotube Random Networks[END_REF] These results indicate that the functionalization of T13NDs on our CNT devices did not increase its noise levels, which can be critical in achieving a high sensitivity in our devices.

Figure 4a shows the real-time response of an ONBN to various concentrations of CV. Here, while adding various concentrations of target solutions, we measured drain-source currents of the ONBN using a semiconductor analyzer. The drain-source bias voltage was maintained as 0.1 V during the measurement. To monitor the response of our ONBNs to CV, we develop the buffer zone of 9 μL HEPES solution. After 100 s, we consecutively added 10 pM CV solution of 1 μL onto the buffer zone. In a similar manner, CV solutions were introduced from a low concentration to a high concentration by the factor of 10 at each time. The concentrations of added solutions were calculated by considering the increased solution volume. Then, the measured data of current changes during the additions of CV were normalized by the original current values to estimate the normalized conductance change G/G 0 . Note that the conductance of the ONBN was sharply increased after adding various concentrations of CV solutions. The ONBN exhibited increased conductance by CV solutions with concentration as low as 10 pM, indicating the high sensitivity of our device. The control experiment using TAAR5 which does not respond to CV was also performed. We assembled the TAAR5-embedded nanodiscs (T5NDs), immobilized the T5NDs on floating electrode of CNT-FET and tested it with increasing concentration of CV (Figure S6). The CV was added up to 100 μM; however there is no meaningful response. Thus we can conclude the ONBN selectively binding to CV was effectively constructed. Moreover, for CV, in sauerkraut, fish, cheese, fermented sausages and seasonings, maximum tolerable levels are about 4.2, 5.0, 5.3, 10.6 and 15.07 μM, respectively. [START_REF] Rauscher-Gabernig | Dietary Exposure Assessment of Putrescine and Cadaverine and Derivation of Tolerable Levels in Selected Foods Consumed in Austria[END_REF] The limit of detection of ONBN is about 10 pM which is much lower than that of tolerance of CV in various foods. Therefore, our platform could be practically used to assessment of food quality. The plausible mechanism for this response is that the binding of protonated positively-charged CV molecules to TAAR13c increased the work function of the floating electrode. [START_REF] Sharma | Elimination of a Ligand Gating Site Generates a Supersensitive Olfactory Receptor[END_REF] Thus, the binding of CV decreased the Schottky barrier for hole carriers in the device and increased the conductance of the ONBN device. [START_REF] Kim | DNA Sensors Based on CNT-FET with Floating Electrodes[END_REF] Figure 4b shows the graph for the normalized sensitivity N of ONBNs at different concentrations of CV. The normalized sensitivity was estimated by normalizing the sensor sensitivity (|ΔG/G 0 |) with respect to its maximum sensitivity value. [START_REF] Kim | Bioelectronic Super-Taster" Device Based on Taste Receptor-Carbon Nanotube Hybrid Structures[END_REF][START_REF] Takagi | Quantification of Suppression of Bitterness Using an Electronic Tongue[END_REF][START_REF] Jin | Nanovesicle-Based Bioelectronic Nose Platform Mimicking Human Olfactory Signal Transduction[END_REF][START_REF] Kim | Single Carbon Atomic Resolution Detection of Odorant Molecules Using a Human Olfactory Receptor-Based Bioelectronic Bose[END_REF] The measured response curves can be analyzed using the model based on the Langmuir isotherm theory as previous studies. [START_REF] Patnaik | s Analytical Chemistry Handbook[END_REF] In this model, the density C s of CV molecules bound to the T13NDs on an ONBN can be written as

⑶

By fitting the measured data with this model, we could estimate the equilibrium constant K between T13NDs and CV as 3.63ⅹ10 11 M -1 , which is a rather large compared with previously-reported values measured using cells or biological systems. This result implies that our ONBN device can detect target CV molecules with a much higher sensitivity than cells or biological systems. Moreover, these results demonstrate that our ONBN show the reproducible signals in repeated experiments.

Figure 4c shows the real-time response of an ONBN to various molecules containing amine functional groups. Here, we injected diaminodecane (DD), trimethylamine (TMA), ethanolamine (EA), glutamine (Glu) and CV molecules to the ONBN in series while measuring the sensor responses. DD and EA have the similar structures with CV, TMA has a fishy odor, and Glu is an amino acid. The structures of these molecules are presented in Supporting Information (Figure S2). Note that the ONBN device exhibited negligible sensor responses to non-target molecules even at a relatively high concentration of 1 μM. However, the conductance of the ONBN increased sharply by adding CV at a concentration of 1 nM, which is 1000 times lower concentration than that of non-target molecular species. This result clearly shows that our ONBN can selectively detect CV at a very low concentration even in the presence of high concentrations of similar molecular species. The amplitude of response was compatible with that in figure 4a. However, the noise level of this experiment was higher than previous one in figure 4a. They are the same response in figure 4a and4c, but the shape of response could seem different because of the difference between their noise levels (signalto-noise ratio in figure 4c: ~4.3).

Figure 4d shows the responses of ONBNs to various real-sample solutions obtained from spoiled foods. Each tested food sample was prepared in HEPES buffer solution and filtered by ultrafiltration membranes (see METHODS section). The ONBN exhibited a higher response to samples from salmon and beef with a longer spoilage period. On the other hand, the samples from salmon with sorbic acid, one of the preservatives, exhibited decreased sensor responses, presumably due to the reduced spoilage of the salmon by sorbic acid. It indicates that our ONBN devices can be used to evaluate the quality of real-food samples quantitatively. Interestingly, the pork fat sample showed negligible sensor responses even after a long spoilage period. This is presumably because CV, the target of our ONBN device, is the product of a decarboxylation of lysine which existed in salmon and beef at a large quantity, but not in pork fat. [START_REF] Pipek | The Composition of Pork Lard as a Raw Material in Meat Production[END_REF] These results indicate our ONBN devices can be utilized to evaluate the quality of various real-food samples quantitatively under complex environmental conditions.

CONCLUSIONS

In conclusion, we developed a highly-stable ND-based bioelectronic nose for the detection of CV. The NDs were successfully constructed with TAAR13c produced in E. coli.

TAAR13c receptors in ND keep the native receptors properties and permit highly sensitive and selective detections of CV. Especially, the immobilization of T13NDs in a desired orientation on floating electrodes via linker molecules enabled a high density of recognition elements and active binding pockets in our ONBN devices, which results in its high sensitivity and selectivity. Furthermore, an ONBN measured CV quantitatively in real-food samples with different spoilage periods. These results show that our ONBN device based on high-quality GPCR-conjugated FETs is attractive technique for the detection of food spoilage and has a great potential for other practical applications such as detection of corpses. Western blot analysis and total protein assays. All protein samples (20 μL) were analyzed by SDS-PAGE and western blot analysis. Western blot analysis was performed using anti-FLAG rabbit Ab (Cell Signaling Technology, USA), anti-His-probe mouse Ab (Santa Cruz Biotechnology, USA) and anti-V5 epitope mouse Ab (Santa Cruz Biotechnology, USA) as primary Ab. HRP-conjugated anti-rabbit Ab (Millipore, USA) and HRP-conjugated anti-mouse Ab (Milipore, USA) were used as a secondary Ab. Luminata Forte western HRP substrate (Millipore, USA) was also used. The protein concentration was measured using BCA assay kit (Pierce, IL, USA).

METHODS

Materials

Assembly of T13NDs. POPC and POPG were used in combination at a 1:1 molar ratio to mimic the native membrane-like environment. Lipids were dried using nitrogen gas from a chloroform solution and vacuumed for 1 h to remove residual chloroform. The lipids were solubilized in HEPES buffer II, added to purified TAAR13c protein, and then incubated for Measurement of gate profiles and noise characteristics. The gate profiles were measured by a semiconductor analyzer (4200-SCS, Keithley, USA). A drain-source bias voltage of 0.1

V was maintained during measuring the characteristics. When a DI water droplet of 10 μL was placed on the channel of an ONBN, the gate bias voltage was applied through the DI water droplet and swept from -0.5 V to 0.5 V. We utilized a fast Fourier-transform network analyzer (SR 770) for the measurement of the noise characteristics. The bias voltage of 0.1 V was applied to the ONBN sensor.

Figure 3

 3 Figure3shows the characteristics of an ONBN. Figure3ashows the fluorescence image of

⑴

  where C and K represent the concentration of odorant in a solution and an equilibrium constant between odorant and T13NDs, respectively. C s max is the density of T13NDs on the electrodes of an ONBN. The binding events between CV and T13NDs induced increased conductance. If we assume that a conductance change ΔG is linearly proportional to the number of bound CV molecules on T13NDs, a sensor sensitivity can be approximated as |ΔG/G 0 | ~ kC s , where k is a constant representing the response characteristics of an ONBN. Therefore, the sensor sensitivity could be written as ⑵ As C becomes very large, the sensor sensitivity |ΔG/G 0 | could converge to k•C s max . Thus the normalized sensitivity N can be written as

.

  Zebrafish (Danio rerio) cDNA was donated by Prof. Hyunsook Lee () were purchased from Avanti Polar Lipids (USA). Sodium cholate and HEPES were purchased from Sigma-Aldrich (USA).Gene cloning of ApoA-I and TAAR13c. The ApoA-I gene was designed so that it contained 6xHis and stop codon gene, and it was amplified by PCR with primers (5' CAC CAG GAG ATA TAC ATA TGA AAG CTG CGG TGC TGA CC 3', 5' CTA GTG GTG GTG GTG GTG GTG CTG GGT GTT GAG CTT CTT AGT GTA 3') using human genomic DNA. The TAAR13c gene was amplified by PCR with primers (5' CAC CAG GAG ATA TAC ATA TGA TGC CCT TTT GCC ACA AT 3', 5' TGA ACT CAA TTC CAA AAA TAA TTT ACA C 3') using the zebrafish cDNA. Amplified PCR products were inserted into the pET-DEST42 bacterial expression vector (Invitrogen, USA) using a gateway cloning system (Invitrogen, USA). The TAAR13c gene was also cloned into pcDNA3 mammalian expression vector using an amplified PCR product (primer; 5' ATG AAT TCA TGG ATT TAT CAT CAC AAG AAT 3', 5' ATC TCG AGT CAA ACC GTA AAT AAA TTG ATA 3').Expression ofTAAR13c in HEK-293 cell. Human embryonic kidney (HEK)-293 cells were cultured in Dulbecco's Modified Eagles Medium (DMEM) (HyClone, USA) supplemented with 1% penicillin, 1% streptomycin (Gibco, USA) and 10% Fetal Bovine Serum (FBS) (Gibco, USA) at 37 °C under 5% CO 2 . The transfection was performed with Lipofectamine3000 (Invitrogen, USA) following the manufacturer's protocol. The cells were transfected with Liopofectamine3000 DNA mixture containing TAAR13c, pCRE-Luc, pSV40-RL, G αolf and RTP1S. The cells were harvested with phosphate-buffed saline, (PBS, pH 7.4) and then disrupted by sonication (2 s on/off, 2 min) (Sonics Vibracell, USA). Dual luciferase reporter assay. The Dual-Glo Luciferase Assay System (Promega, USA) was introduced to analyze biological activity of TAAR13c. The transfected cells were stimulated with 50 μL of serum-free DMEM for 30 min and then incubated with various amine species for 4 h. The luminescence activity was measured with a Spark 10M multimode microplate reader (TECAN, USA). The normalized luciferase activity was calculated with the formula [CRE/Renilla(N) -CRE/Renilla(0)]/[CRE/Renilla(FSK) -CRE/Renilla(0)]. A no amine solution was used as a negative control, and the 10μM forskolin (FSK) was used as a positive control. Purification of ApoA-I. BL21(DE3) E. coli cells bearing the pET-DEST42/ApoA-I construct were cultured in 1 L Luria-Bertani (LB) medium (+50 μg/mL ampicillin) at 37 °C.When the cells were grown until the OD 600 value reached 0.5, the overexpression of ApoA-I was induced by the addition of isopropyl thiogalactoside (IPTG) to a final concentration of 1 mM. After 3 h, the cells were centrifuged (7000 g, 20 min, 4 °C), resuspended in a lysis buffer (20 mM Tris-HCl, 0.5 M NaCl, 20 mM imidazole, pH 8.0) and disrupted by sonication (5 s on/off, 5 min). The cell lysate was centrifuged at 12,000 g for 30 min at 4 °C. The ApoA-I in the supernatant was collected and loaded to HisTrap HP column (GE Healthcare, Sweden) through FPLC (GE Healthcare). The column was washed with washing buffer (20 mM Tris-HCl, 50 mM imidazole, 0.5 M NaCl, pH 8.0), and the ApoA-I was eluted with the elution buffer (20 mM Tris-HCl, 400 mM imidazole, 0.5 M NaCl, pH 8.0) and dialyzed against HEPES buffer I (20 mM HEPES-NaOH, 100 mM NaCl, 20 mM cholate, 1mM EDTA, pH 8.0) using HiTrap HP desalting column (GE Healthcare, Sweden). The proteins were stored at 4 °C until used.Purification of TAAR13c. The BL21 (DE3) cells were transformed with the pET-DEST42/TAAR13c vector and cultured in LB medium (+50 μg/mL ampicillin) at 37 °C until the OD 600 value reached 0.5. The expression of TAAR13c was induced by the addition of 1 mM IPTG, and the cells were incubated for 4 h. The cells were centrifuged (7000 g, 20 min, 4 °C), and pellets were resuspended in PBS containing 2 mM EDTA. The cells were disrupted by sonication (5 s on/off, 5 min) and centrifuged (12000 g, 4 °C, 20 min). The sonication and centrifugation were repeated, and the pellet of the sample was solubilized in solubilization buffer (0.1 M Tris-HCl, 20 mM sodium dodecyl sulfate (SDS), 100 mM dithiothreitol (DTT), 1 mM EDTA, pH 8.0) at 25 °C. The solubilized proteins were dialyzed against 0.1 M sodium phosphate (pH 8.0) containing 10 mM SDS using a 10K MWCO dialysis cassette (Thermo Scientific, USA), filtered with a 0.2 μm bottle top filter (Thermo Scientific, USA), and then applied to HisTrap HP column equilibrated in 0.1 M sodium phosphate (pH 8.0) containing 10 mM SDS. The column was successively washed with gradient (pH 8.0 to 7.0) using washing buffer (0.1 M sodium phosphate, 10 mM SDS), and the TAAR13c was eluted with the same buffer at pH 6.0. The eluted protein was dialyzed against the HEPES buffer II (20 mM HEPES-NaOH, 100 mM NaCl, 25 mM cholate, 1mM EDTA, pH 8.0). The purified TAAR13c was analyzed by SDS-PAGE and western blot analysis.

  10 min in ice. After that the ApoA-I was added, and the mixtures were incubated for 2 h at 4 °C with stirring. The final concentrations of the mixture were 1 μM TAAR13c, 100 μM ApoA-I, 8 mM lipids and 25mM detergent. Next, Bio-Beads (Bio-Rad, USA) were added to this mixture to remove the detergents with overnight agitation. Finally, the mixture was applied to a size exclusion chromatography (SEC) (Superdex 200 Increase 10/300 GL, GE Healthcare, USA) to remove unbound proteins. The column was equilibrated with HEPES buffer III (20 mM HEPES-NaOH, 100 mM NaCl, 1mM EDTA, pH 8.0) and the 500 μL of sample was loaded in injecting loops at a flow rate of 0.5 mL/min using FPLC. The peak fractions were collected and the purified T13NDs was stored at 4 °C before characterization steps.Analyses of T13NDs.The sizes of NDs were analyzed using a dynamic light scattering spectrophotometer (DLS) (DLS-7000, Japan). The T13NDs was also confirmed by using a SUPRA 55VP field-emission scanning electron microscope (FE-SEM) (Carl Zeiss, Germany). The intrinsic fluorescence of T13NDs was measured in real-time using a LS 55 luminescence spectrometer (Perkin Elmer, USA) (excitation 290 nm; emission 340 nm). The real-time intrinsic fluorescence of TAAR13c was measured using 1-10 mM of various amines.Immobilization of T13NDs on floating electrode of CNT-FET using V5 Ab. Halffragment Ab was generated by 2-MEA reagent. Channels were incubated in 0.5 M N-acetyl cysteine for 10 min. Subsequently, channels were gently rinsed in deionized (DI) water. The thiol-functionalized channels were dipped in half-fragment V5 Ab solution at 37 °C for 1 h. Finally, the V5-functionalized floating electrodes were incubated in T13ND solution for 30 min at room temperature. For fluorescence microscopy, V5 Ab with Dylight 488 solution (Thermo Scientific, USA) was diluted with PBS (0.02 mg Ab/ml) and applied to the channel for 1 h. The droplet was then washed with PBS solution, instead of the final T13NDs incubation step. In the case of AFM measurement, we exchanged the buffer solution for DI water.Preparation of tested samples. All the tested amines were prepared at 1 mM in 100% DMSO, and serially diluted 1:10 with HEPES buffer. Fresh foods (salmon (Norway), beef (Korea), pork fat (Korea)) were purchased from a local grocery store. Each food sample (100 mg) was soaked in HEPES buffer solution (1mL) and incubated at 37 °C for 4 weeks to prepare the real samples. The spoiled foods samples were collected weekly (0 -4 weeks) and kept in microtubes at -80 °C. The frozen samples were thawed at once just before the electrical measurements. The sample solutions were diluted to 1/1000 and filtered by 100,000 nominal molecular weight cut-off (NMWCO) ultrafiltration membranes (Ultracel YM-100, Millipore, USA) with centrifugation at 1000g for 10 min to remove floating matter in the sample solutions.

Figure 1 .

 1 Figure 1. Schematic diagram of an ONBN. This figure illustrates the ONBN and possible

Figure 2 .

 2 Figure 2. Characterization of TAAR13c expressed in HEK-293 cells and high-quality

Figure 3 .

 3 Figure 3. Characteristics of an oriented NDs-functionalized CNT-FET with floating

Figure 4 .

 4 Figure 4. Responses of ONBN devices to various samples. (a) Real-time response of an

ACKNOWLEDGMENTS

We thank Prof. Hyunsook Lee (Seoul National University) for donating the zebrafish (Danio rerio) cDNA. This research was supported by the National Research Foundation funded by the Korean government (MSIP) (2016945295). This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 682286). S.H. acknowledges the support the BioNano Health-Guard Research Center and NRF grant funded by MSIP (H-GUARD 2013M3A6B2078961, 2014M3A7B4051591). This work was also supported by the Korea Basic Science Institute (D37410).

Table of Contents (TOC)

ASSOCIATED CONTENT

Supporting Information: Additional information about experimental details, NDs purification, MSP preparation, CNT fabrication and real sample data. The Supporting Information is available free of charge via the Internet at http://pubs.acs.org.

AUTHOR INFORMATION

Corresponding Authors

Prof. T. H. Park: Tel: +82-2-880-1874; Fax: +82-2-857-9348; E-mail: thpark@snu.ac.kr Prof. S. Hong: Tel: +82-2-880-1343; Fax: +82-2-884-5572; E-mail: seunghun@snu.ac.kr Author Contributions ‡ These authors contributed equally to this work.


Miriam Luque Chipana

Himanshu Verma
email: himanshu.verma@acm.org

Florian Evéquoz
email: florian.evequoz@hevs.ch

Pierre Vanhulst
email: pierre.vanhulst@unifr.ch

Denis Lalanne
email: denis.lalanne@unifr.ch

Miriam Luque-Chipana

Vasco: Interactive Tool for Early-Exploration of Data Vasco : un outil interactif pour l'exploration précoce des données

Keywords: Human-centered computing → Visualization tools, Early exploration Visualization tools, data visualization, early exploration Outils de visualisation, visualisation de données, exploration précoce

à 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.

INTRODUCTION

Data visualizations are direct representations of the data. They allow the comprehension of the data, the generation of hypotheses and the representation of an idea to communicate [START_REF] Fisher | Making data visual : a practical guide to using visualization for insight[END_REF]. Most tools that offer assistance with data visualization usually require users to have training and prior knowledge of the data. To choose relevant visual representations, inexperienced users also need to understand their data and their attributes, a task that requires early exploration of the data. We believe these users would benefit from an automatic visualization presentation that is generated based on data selections grouped by attributes.

IHM'19 Adjunct, December 10-13, 2019, Grenoble, France Vasco: Interactive Tool for Early-Exploration of Data

4:2

Vasco attempts to help these inexperienced users during the data comprehension process, through exploration based on visualization. Vasco uses univariate analysis to describe the data and help the user to find patterns that exist within the variable. To this end, Information Cards display sparklines and the data characteristics (mean, mode, average) to help the user understand the data; to continue with the exploration process, Vasco allows the user to select the variables (get from the data) and generates a list of visualizations from the combination of the selected variable and the remaining variables. For the user to be able to focus on specific questions, Vasco allows the creation of specific visualizations using the selection of variables grouped in a card without the specification of the visualization channels. The interface of Vasco relies on dedicated color schemes and icons to facilitate the identification of the type of each variable in a dataset. By improving their understanding of the data, users of Vasco are also better informed about the relevance of the associations between each dimension of their data. At the moment, Vasco is not focused on the customization of visualizations and provides no mean to change the specifications.

STATE OF THE ART

The tools for generating visualizations differ in the approach and process that the user must follow to create visualizations. Data Illustrator [START_REF] Liu | Data Illustrator: Augmenting Vector Design Tools with Lazy Data Binding for Expressive Visualization Authoring[END_REF] focuses on the design of the visualization, the user composes the visualization and configures its parameters to be able to add data. RawGraphs [START_REF] Mauri | RAWGraphs: A Visualisation Platform to Create Open Outputs[END_REF] has a predefined list of visualizations, the users choose the visualization and then add the data, the data is restricted by the chosen visualization. In both cases, creating and choosing the most suitable visualization requires to know about the visualization design and the data. Tools such as Datawrapper [START_REF] Datawrapper | Enrich your stories with charts, maps and tables[END_REF], Data Voyager [START_REF] Wongsuphasawat | Voyager: Exploratory Analysis via Faceted Browsing of Visualization Recommendations[END_REF], Voyager 2 [START_REF] Wongsuphasawat | Voyager 2: Augmenting Visual Analysis with Partial View Specifications[END_REF] and Tableau [START_REF] Mackinlay | Show Me: Automatic Presentation for Visual Analysis[END_REF][START_REF] Tableau | Changing the way you think about data[END_REF] require the specification of dimensions and display marks. Data Wrapper generates a visualization and then allows you to change the visualization type, dimensions and marks. Data Voyager, Voyager 2 and Tableau use a ranking system to decide which is the best visualization based on the selected data dimensions. Once the visualization is generated it is possible to change the visualization type. Data Voyager and Voyager 2 have a mixed-initiative, that use a recommendation system to generate visualizations related to the visualization created by the user.

VASCO PLATFORM

Vasco is built on NodeJs and uses CompassQl [START_REF] Wongsuphasawat | Voyager: Exploratory Analysis via Faceted Browsing of Visualization Recommendations[END_REF], Vega, Vega-Lite [START_REF] Satyanarayan | Vega-Lite: A Grammar of Interactive Graphics[END_REF] to generate visualizations. Vasco uses CompassQl to choose the most relevant visualization. Vasco is divided into three components (1) data upload, (2) analyzer and (3) report. The first component, Data Upload allows the user to upload data in CSV format files. The second component, the Analyzer is in charge of generating the visualizations and creating a list of the dimensions together with relevant attributes( average, media, moda, sparklines) for each dimension. The analyzer uses CompassQl to generate a list of Vega-Lite

Vasco Mode of Use

Vasco is focused on exploring data. To this end, the platform has two modes of use: (1) exploratory mode and (2) creation mode. The exploratory mode generates a list of views for each dimension, these views are formed from the combination of the selected variable with the remaining dimensions. The selection of multiple dimensions in exploratory mode avoids the redundancy of the visualizations. The second mode allows you to create specific views by grouping dimensions. It is not necessary to specify the axes and display marks.

Vasco Interface

The Vasco interface is divided into 4 sections: (1) Load the data, (2) Variable Panel(Figure 1 A), (3) Workspace(Figure 2 A), (4) Report. Vasco is composed of cards that allow interaction, display information and visualizations. The first section Load the Data, allows the user to upload the CSV files selected by the users. The second section, the Variables Panel shows the list of dimensions found in the data. Information Cards are used to present the dimension, the cards change according to the type of data of the variable. The types of data(Figure 3) are classified in quantitative, nominal, temporal. Vasco assigns an icon and a different color for each type of data. The information cards(Figure 4) are divided into two parts: (1) the header and (2) the body. The header contains the data type icon and the name of the dimension; the body of the card shows additional information such as the mean, fashion, average and sparkline that is created as a summary of the dimension. The third section Workspace is divided into two subsections: (1) Selection Panel(Figure 2 C) and (2) Graphics Panel(Figure 2 F). The user can create multiple Workspaces, creating also new selection and graphics panels. The user must drag the cards from the variable panel to the selection panel to create visualizations. When Vasco is in exploration mode, the list of graphics generated for the variable will be displayed in the graphics panel.

To create a specific visualization, Vasco uses creation cards that allow to group dimensions. The creation cards(Figure 5 ) are divided into two parts: (1) the header and (2) the body. The first part is intended to give feedback to the user on the visualization to be created. The icons of the data types are shown with their respective colors, when the user adds a dimension inside this card the color of the icons change to lead if it is not possible to continue adding a dimension of the same type; in this way Vasco seeks to help the users to create a visualization without having to worry about the configuration of the axes and marks of the visualization. The graphics panel shows the created visualizations, uses graphics cards to show the visualizations. Graphics cards(Figure 6) are divided into two parts:(1) the header and (2) the display. The header of the card contains the name of the IHM'19 Adjunct, December 10-13, 2019, Grenoble, France Vasco: Interactive Tool for Early-Exploration of Data 4:4 dimensions that have been used when generating the display; additionally it has a button to add the display to the report. The last part of the interface is the Report which allows the grouping of important visualizations. We conducted a user study to compare Vasco with Voyager 2, with a specific focus on early exploration. Through this comparison, we intended to study the generation of fully manual visualizations through semi-automatic process.

EVALUATION AND RESULTS

Study Protocol

We recruited twelve participants without experience in data analysis and visualization design. The users had no prior experience with Voyager 2 and the datasets. We used the same databases that the authors of Voyager 2 used in their study. The study session was designed to compare Vasco and Voyager 2. We used two different databases, but they shared the same data types. The order of use of the tools was alternated among the participants. The study started with 5 minutes of training on the tool, then the users were asked to: "explore the dataset, get an idea of what it was about and what information they think is relevant"; they were free to use the tool during 20 minutes. The process was repeated for each tool. At the end of the session, an interview was performed and the user was asked to complete a post-study survey.

Results

We present the results obtained in the study, which focuses on early exploration by covering dimensions as part of the exploration process, the use of creation cards to generate specific visualizations and the feedback obtained in interviews and surveys. We use linear mixed-models that allow us to estimate the effect of the visualization tool taking into account the variance of data set and individual performance. We made the following assumptions regarding Vasco:

(1) Information cards increase the understanding and coverage of variables. To evaluate the coverage of the dimensions we include the visualization tool as a fixed effect and the interaction with variables as the dependent variable, under the relation of the interaction with the variables as a function of the Vasco or Voyager2 tool. It was found that this model was significant t(9)=2.61, p=.03. Vasco affected the interaction with the variables by increasing the coverage of the variables in 1.7 variables more than Voyager 2 with a standard error of 0.9. The information sheets in Vasco try to summarize the information of the dimensions, in the same way, Voyager presents the summarized visualizations. While Voyager 2 starts with a list of summarized views, Vasco starts with an empty workspace. Some of the users stated that the initial visualization IHM'19 Adjunct, December 10-13, 2019, Grenoble, France Vasco: Interactive Tool for Early-Exploration of Data 4:5 of Voyager 2 made them feel overwhelmed and confused because they didn't understand the relationship with dimensions. This limited the user's interaction with the variables (2) We expected that Voyager 2 would be preferred to answer specific questions, but that the margin of preference to Voyager 2 would not be prejudicial to Vasco. Voyager 2 offers control over the visual encodings, unlike Vasco which automatically generates the visualization and indicates what type of variables can be added. To measure this, we include the visualization tool as a fixed effect and the creation of visualizations as the dependent variable, under the relation of the creation of visualizations in function of the Vasco or Voyager2 tool. It was found that this model resulted in t(9)=-1.7, p=.01. This result argues that there is a slight preference for Voyager 2 when it comes to specification control, but the difference with Vasco is thin. The users said they would like Vasco to offer more control over the channels and customization of the tools. Voyager 2 was preferred by users, but they also said they would use Vasco to create simple visualizations. They require a mid-point that allows them to customize the visualizations after they are automatically created as Vasco does. (3) The use of workspaces facilitates and improves the work of the user. Regarding the third hypothesis, we asked the users about their experience with workspaces. 9 of the 10 participants agreed that it helped them with the organization, and made their work more efficient. The average number of workspaces created during the sessions was 3, the highest number of workspaces used was 5 and the lowest was 2.

We finally submitted a survey to the users, that consisted of 15 questions and statements related to both platforms and rated from 0 (strongly disagree) to 5 (strongly agree). We found that 8 of the 10 users considered Vasco easy to use, while 3 of the 10 users considered Voyager 2 the same. We found a relationship between the difficulty of use and the complexity of the tools. For data exploration, 8 of the 10 prefer Vasco, while 5 of the 10 users said they would also work on Voyager 2. For the specific creation of graphics, 6 of the 10 would use Vasco, while 7 of the 10 would also use Voyager 2.

CONCLUSION AND FUTURE WORK

We introduced Vasco, a system to support early exploration of data through visualization for inexperienced users. We found that the visual presentation of information related to the attributes of the data improves their comprehension. The use of multiple workspaces helps the users organize their work and consult their previous explorations without having to recreate the visualizations. A common issue raised by our participants was the lack of control of the specifications. Further work should extend Vasco with this feature, with the aim of serving both inexperienced and expert users. Another trail to follow is the addition of annotations [START_REF] Vanhulst | A Descriptive Attribute-Based Framework for Annotations in Data Visualization[END_REF], leveraging Vasco to allow the sharing of discoveries made by analysts during their exploration of the data.

Figure 1 :

 1 Figure 1: Vasco Interface, Variable Panel(A), Visualization dimension information button(B)

IHM' 19

 19 Adjunct, December 10-13, 2019, Grenoble, France Vasco: Interactive Tool for Early-Exploration of Data 4:3 IHM '19 Adjunct, December 10-13, 2019, Grenoble, France specifications, and then render them using Vega. The last component is the Report, it allows the grouping and export of the visualizations.

Figure 2 :

 2 Figure 2: Vasco Interface, Workspace(A), Add workspace button(B), Selection Panel(C), Creation Card Button(D), Clear the selection panel button(E), Graphic panel(F), Comments button(G), Comments box(H) .

Figure 3 :

 3 Figure 3: Data types icons and colors

Figure 4 :Figure 5 :Figure 6 :

 456 Figure 4: Information card with additional information displayed(A), Information card without additional information(B), Information card when is in the selection panel(C)

IHM' 19

 19 Adjunct, December 10-13, 2019, Grenoble, France Vasco: Interactive Tool for Early-Exploration of Data 4:6


Arthur Boixel

Pierre Bisquert

Madalina Croitoru

Deliberation towards Transitivity with Unshared Features

We place ourselves in a decision making setting where a set of agents needs to collectively decide upon a set of alternatives characterised by their features. We introduce the notion of unshared features and show that if such features do not exist then we can reach a Condorcet consensus. We provide a deliberation protocol that ensures that, after its completion, the number of unshared features of the decision problem can only be reduced.

Introduction and Motivation

Social choice theory allows to study the way in which the aggregation of individual preferences can lead to the expression of a collective preference. Unfortunately, well-known impossibility results prevent the construction of simple and satisfactory preference aggregation methods [START_REF] Brandt | Handbook of Computational Social Choice[END_REF]. In this paper we focus on a well-known topic in social choice : single-peakedness preferences and their link to the Condorcet paradox. The Condorcet paradox is a situation noted by the Marquis de Condorcet in the late 18th century [START_REF] De Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF], in which the aggregation of individual preferences via pairwise majority can result in cyclic collective preferences, even if the individual preferences are not cyclic. For example, if we consider three agents 1, 2 and 3 and three alternatives bike, car and train, one can encounter the situation where agent 1 prefers bike to car to train, agents 2 prefers car to train to bike and agent 3 prefers train to bike to car. In this case no alternative beats the other in pairwise majority. The car is strictly preferred to the train by a majority (agents 1 and 2) but the train is strictly preferred to the bike by an other majority (agents 2 and 3) and the bike is strictly preferred to the car by a majority (agents 1 and 3). Thus we have no Condorcet winner here (i.e. an alternative that is preferred, pairwise, to all other alternatives by a majority) and we obtain a non transitive result. Although satisfying properties which are desirable in democracy1 [START_REF] Arrow | Social choice and individual values[END_REF], in such cases, pairwise majority cannot be used to aggregate individual preferences.

One way of going around this situation is to look for necessary or sufficient conditions on the individual preferences that will ensure a well-defined result [START_REF] Sen | A possibility theorem on majority decisions[END_REF]. But restricting the expression of individual preferences is a non democratic way for their aggregation. Indeed, it forces our preference aggregation method to violate the universality property [START_REF] Arrow | Social choice and individual values[END_REF]. To take advantage of the latter conditions without violating this property, we have to better understand them. In the forties, Duncan Black studied cyclic preferences and introduced the notion of single-peakedness [START_REF] Black | The median voter theorem[END_REF]. A group of agents is said to have single-peaked preferences if each agent has an ideal choice in the set of alternatives, and for each agent, alternatives that are-according to a fix order on the alternativesfurther from her ideal choice are less preferred. Single-peaked preferences have the desired property of allowing for a Condorcet winner [START_REF] Black | The median voter theorem[END_REF]. For example if we alter the preferences from the previous example and we consider that agent 3 prefers train to car and car to bike then the set of individual preferences is single-peaked according to the order > : bike > car > train. Therefore we can conclude that there exists a Condorcet winner, in that case, the car alternative. In this paper we place ourselves in a decision making setting where a set of agents needs to collectively decide upon a set of alternatives characterised by their features [START_REF] Dietrich | Where do preferences come from ?[END_REF]. The agents have desired features and the satisfaction of these features by the alternatives induces agents' individual preferences. The more an alternative satisfies the desired features of an agent, the higher its rank will be in the agent's individual preferences. In this setting, as explained above, using voting rules satisfying desirable properties as a collective decision making procedure can lead to situations (such as the Condorcet Paradox) where no decision can be made. In this paper we address this problem by studying conditions on the alternatives' features that ensure the avoidance of the Condorcet Paradox. We introduce the notion of unshared features and show that if such features do not exist then we can reach a Condorcet consensus. Moreover, we conjecture and empirically prove that the less unshared features there are, the closer we get (with respect to well-known distance measures in the literature) to reaching a Condorcet consensus. Last, we provide a deliberation protocol that ensures that, after its completion, the number of unshared features can only be reduced.

Individual Desires and Preference Formation

In this section, we will explore how agents can form their individual preferences based on the amount of satisfaction alternatives can provide them and how the consequences of dissatisfaction affect preferences.

Let us consider a set N of n agents that will express preferences over a set X of possible alternatives. Each alternative x is objectively described by a set P x of features that represents the satisfaction, or dissatisfaction, of several criteria. More precisely, given a set of criteria C, for each criterion c ∈ C, P x will either contain p c (criterion c is satisfied) or np c (criterion c is not satisfied). We say that x satisfies p c if p c ∈ P x , otherwise np c ∈ P x .

Inspired by the work of Dietrich et al. [START_REF] Dietrich | Where do preferences come from ?[END_REF] we suppose in this work that agents' preferences are based on desired features. In particular, we assume that each agent i ∈ N has a set W i of desired features which will induce a preference relation over X, i.e. i will prefer an alternative x ∈ X over an alternative y ∈ X if the number of features in W i satisfied by x is greater than or equal to the number of features in W i satisfied by y.

Definition 1 (Features-induced preference formation). Given a set W of desired features, two alternatives x, y ∈ X and their respective set of satisfied properties P x and P y , x is preferred to y according to W (x W y) if and only if

|{p ∈ P x s.t. p ∈ W }| ≥ |{p ∈ P y s.t. p ∈ W }|
If x is preferred to y and y is not preferred to x according to W , then x is strictly preferred to y according to W (x W y). Otherwise, we suppose that x and y are equivalent according to W (x ∼ W y). 2 Given an agent i ∈ N and her desired features W i , we will denote by Wi or i her preferences.

Among these desired features, some are desired by all agents in the group, while others are more personal. Some of these personal features can lead to modifications in the agents preferences which bring the collection of individual preferences (so-called preference profile) farther from consensus. Intuitively, the more the agents want personal features, the more heterogeneous their preferences will be and the lower the probability of obtaining a transitive result via pairwise majority. Following this idea we will qualify as unshared every feature which is not desired by the entire set of agents, the others are considered as consensual.

Definition 2 (Consensual and unshared features). Given a set N of agents and, for each agent i ∈ N its set of desired features W i , we denote by

• W ∀ = i∈N W i the set of consensual features, • W ∃ = {p ∈ i∈N W i s.t. p / ∈ W ∀ } the set of unshared features.
Hence, it is possible to consider the preferences induced by the consensual features, W ∀ , which correspond to a ranking that can be seen as an approximation of the group's collective preferences. The aim of our work is to provide agents with a means to reach a situation where the Condorcet paradox can be circumvented thanks to a deliberative dialogue. But accounting for every particular case of induced preferences following a deliberation is nearly impossible Table 1: The six possible rankings for three alternatives.

#

Ranking

1 A B C 2 B A C 3 A C B # Ranking 4 C A B 5 B C A 6 C B A
as it depends on what the agents want and their justifications, which can be considered as infinitely diverse. Hence, we need to introduce a notion that will help to represent disagreement within the group. Disagreement between agents is caused by diverging goals and contradicting means to satisfy them. In particular, due to unshared features, agents might distance themselves from the preference relation induced by the consensual features ( W ∀ ) by swapping alternatives in this approximate ranking. We will see in Section 4.2 how to formally link these swaps-called alternative escalations-to the number of unshared features.

In other words, this notion aims to represent the quality of the deliberation: the smaller the number of alternative escalations, the higher the level of consensus, and the more "decisive" the deliberation has been.

Empirical Results

In this section, we will first define the metrics allowing to assess the distance between a given profile of preferences and some kind of idealised preference structure. We next present the experimental setup as well as the results we obtained.

Profile Distance

Single-peakedness and single-cavedness In 2004, Gehrlein [START_REF] Gehrlein | Consistency in measures of social homogeneity: A connection with proximity to single peaked preferences[END_REF] considers a variation of the measure proposed by Niemi et al. [START_REF] Niemi | Majority decision-making with partial unidimensionality[END_REF]. Consider the case of an election with three alternatives X = {A, B, C}. The individual preferences of the agents on these alternatives are limited to the six rankings in Table 1.

Let n l be the number of agents whose individual preferences correspond to ranking #l. We therefore have n 1 + n 2 equal to the number of agents who ranked the alternative C in last position. Similarly, n 3 + n 4 agents ranked B last and n 5 +n 6 agents ranked A last. In our case, if one of the three alternatives is never ranked last, then the preference profile will be-according to an order in which this alternative is ranked second-single-peaked [START_REF] Sen | A possibility theorem on majority decisions[END_REF]. We thus define our measure of proximity: if there exists a candidate rarely ranked last by the agents, then it is probably a unifying candidate in the sense that very few agents would regard her election as the worst possible result. If there are such candidates, it will be easier to find a Condorcet winner [START_REF] Gehrlein | Probabilities of election outcomes with two parameters: the relative impact of unifying and polarizing candidates[END_REF]. Definition 3 (Proximity to single-peakedness). Given n agents, 3 alternatives, a preference profile P and the rankings in Table 1, let n l be the number of agents whose individual preferences i ∈ P correspond to ranking #l. The single-peakedness proximity measure m sp is defined as

min(n 1 + n 2 , n 3 + n 4 , n 5 + n 6 ) |P|
When the value of the metric is 0, a candidate is never ranked last, so the preference profile is single-peaked and there is a Condorcet winner3 . A trivial upper bound for this measure is n 3 . A similar metric m sc can be set up in order to compute the proximity to single-cavedness, a mirror property of single-peakedness which is also a sufficient condition ensuring the existence of a Condorcet winner [START_REF] Inada | A note on the simple majority decision rule[END_REF]. A triplet of alternatives is single-caved when there is an alternative that is never ranked first by the agents.

Separability into two groups

In 2005, based on the work of Inada [START_REF] Inada | A note on the simple majority decision rule[END_REF], Gehrlein [START_REF] Gehrlein | Probabilities of election outcomes with two parameters: the relative impact of unifying and polarizing candidates[END_REF] proposes another measure, variant of the previous ones. Still in the case of three alternatives, if there is a candidate rarely ranked second by the agents, then it is a polarizing candidate. Indeed, it is either very appreciated by some agents (ranked first), or very little appreciated by others (ranked last). In such a situation, it will be easier to extract a structuring dimension from the individual preferences [START_REF] Gehrlein | Probabilities of election outcomes with two parameters: the relative impact of unifying and polarizing candidates[END_REF]. We can then, in the same way as before, define m sg as a measure of the proximity to separability into two groups of a preference profile. In the case m sg = 0, there is a candidate who is never ranked second, the preference profile satisfies the condition of separability into two groups and a Condorcet winner exists. The same upper bound of n 3 applies to this measure.

Triple wise value restriction

The previous measures can be combined to compute a proximity to triple wise value restriction which is a generalisation of the three previous conditions introduced by Sen [15].

Definition 4 (Distance to triple wise value restriction). Given n agents, 3 alternatives, a preference profile P and the rankings in Table 1, let n l be the number of agents whose individual preferences i ∈ P correspond to ranking #l.

The triple wise value restriction proximity measure m tw is defined as

min(m sp , m sc , m sg )
In Section 3.2, we will use variants of these measures-normalised over all triplets of alternatives-in order to study the consequences that the number of unshared features may have on the proximity of preference profiles to these structural properties.

Simulation Results

The notion of alternative escalations introduced in the previous section lets us control the quality of the deliberation that takes place between the agents. A small amount of alternative escalations after deliberation indicates that the agents managed to reduce the quantity of unshared features. On the contrary, a high amount of alternative escalations indicates that they did not manage to agree on a large amount of desirable features and each agent potentially has a significant amount of residual unshared features. More precisely, we will answer in this section the following question: does proximity to interesting structural properties increase when the number of unshared features decreases?

Experimental Settings . The experiment, which aims at simulating a deliberation outcome, is fixed by the following parameters: the number n of agents, the number k of alternatives and the maximum number e of alternatives escalations an agent can do. The experimental protocol is the following. One takes a linear order W ∀ of k alternatives in order to simulate the preference relation induced by the set W ∀ of features considered as desirable by all the agents after deliberation. Then, each agent can do at most e random alternatives escalations in W ∀ (by using her residual unshared features). Once the new preferences generated, one computes the proximity of the preference profile to a given preference structure (single-peakedness, separability into two groups, triple wise value restriction): the proximity measure is the ratio between the number of triplets of alternatives satisfying the preference structure and the total number of triplets. A measure of m s = 1 indicates that all the triplets are satisfying the structure s ∈ {sp, sg, tw}. On the contrary, a measure m s = 0 indicates that all the triplets are problematic and thus the preference profile is not satisfying the preference structure, which will give rise to a non-transitive result in most cases. In order to treat and harmonise the different cases that we can encounter, each point on the graphs corresponds to an average performed on 10, 000 repetitions.

Single-peakedness . The first proximity measure we want to observe is the one to single-peakedness. Figure 1 shows the results of the experiment for n = 200 agents. For k = 3 to k = 10 alternatives, the proximity to single-peakedness has been computed according to e.

Proximity to single-peakedness increases when e (and thus the number of unshared features) decreases. This result supports the hypothesis that agreeing on features allows agents to restructure their individual preferences in an interesting way. However, this increase in proximity is at different speeds depending on the number of alternatives. Indeed, with three alternatives, it is easy to obtain a non single-peaked preference profile by modifying very little the same ranking 4 . On the other hand, with more alternatives, and thus more triplets to consider, more personal modifications from the agents in their new preferences are necessary to move away from single-peakedness. Thus, for a fixed number of modifications, the probability of obtaining a good proportion of single-peaked triplets increases with the number of alternatives.

Please note that good proximity to single-peakedness does not guarantee a transitive result via pairwise majority. We can still hope, in these cases, to obtain a Condorcet winner even if the overall ranking of alternatives is not totally transitive. Indeed, even if there is a cycle in the ranking, a Condorcet winning alternative may exist and may dominate this cycle. This is why the search for a unifying candidate is interesting.

Figure 2 shows the results of the same experiment with a set of 20 agents. The proximity to single-peakedness decreases less rapidly here. This can be explained by the fact that, for a triplet of alternatives, the probability that it is not single-peaked increases with the number of times it has to be considered. The more agents there are, the more unlikely their individual preferences will be single-peaked. Deliberation seems therefore to be more efficient with a reduced number of agents. Although intuitive, this result is interesting because the implementation of a deliberation protocol in real life situations seems difficult if it is necessary to consider a large number of agents.

Separability into Two Groups . The second experiment aims to study the proximity to separability into two groups as introduced in Section 3.1. The results obtained are given in Figure 3. The general shape of the curves is the same as before, so we can conclude that the proximity to separability into two groups increases when e (and therefore the number of unshared features) decreases. However, the proximity value to this property decreases faster than the proximity to single-peakedness, this can be explained by the way in which the new individual preferences are generated. The alternatives ranked first and last in W ∀ are half as likely as the others to change their position when performing alternatives escalations (the first one cannot go up and the last one cannot go down). In case the alternative ranked first moves, then it has to go down to the second place, increasing the probability that a triplet of alternatives containing this alternative will not satisfy the separability into two groups condition. The same holds for the alternative ranked last in W ∀ . The final preference profile will therefore be more likely to be single-peaked or single-caved than to satisfy the separability into two groups condition.

Triple Wise Value Restriction . In the same way as before, we look at the proportion of triplets of alternatives satisfying this condition: checked if the triple is single-peaked, single-caved or satisfies the separability into two groups condition. As expected, the shape of the curves remains the same. Proximity to triple wise value restriction increases as the number of residual unshared features decreases. There is also again a rapid drop in the value of proximity when few alternatives are considered. The same experiment was performed for n = 20 agents, the results are given in Figure 6. As for the proximity measure to singlepeakedness (but to a lesser extent since the measure of proximity to separability into two groups comes into play), with less agents the proximity decreases less drastically and this regardless of the number of alternatives considered. Another positive observation is the fact that for a large number of alternatives, a significant proportion (around 25%) of triplets of alternatives always satisfy one of the three conditions that make up the triple wise value restriction even with a very large and seemingly unrealistic number of residual unshared features. Now that we observed the critical impact that alternative escalations can have on the deliberation outcome, it is necessary to study means to reduce their amount. In the next section, we will assess how a simple deliberation protocol can be used to achieve this goal.

Deliberation Around Unshared Features

In this section, we will first define a simple yet effective deliberation protocol, we will then assess its ability to impact the number of possible alternative escalations an agent will be able to do once the deliberation is over.

Protocol Definition

The deliberation protocol will take place in two phases. Before the first phase, each agent i ∈ N has a preference relation i over the alternatives based on (i) her desirable features in W i and (ii) the a priori knowledge she has on the alternatives.

The goal of the protocol is to provide the agents with a way to revise these preferences by refining their set of desired features and the knowledge they have about the alternatives. Intuitively, agents will share knowledge and opinions through arguments. During this process, agents might discover new features that they were not aware of before as well as new arguments leading them to change their opinion on a particular question. Hopefully, this discussion will give agents more insights on the situation and will allow them to refine their preferences, namely their set of desired features and their knowledge about the alternatives. At the end of the second phase, each agent will have modified preferences i over the alternatives which she will use to vote.

During the first phase, agents will deliberate to collectively agree upon a-final-set W ∀ of features, considered as relevant by the group, that they will use in order to choose among the alternatives. Throughout the deliberation, the goal for an agent i is to make her desired features from W i accepted as relevant by the group. To achieve this goal, agents will assert arguments to justify their preferences. During this first phase, by referring to accepted arguments stored in her commitment store, each agent will change her desired features as she gets eventually convinced by other agents' arguments. In this phase, agents will talk in a round robin manner (one after another) but each agent can, if desired, skip her turn. The first phase ends after n successive turn skips. At the end of the first phase, the set W ∀ of consensual features after deliberation is obtained.

The goal of the second phase is to determine, for each alternative x ∈ X, and at least for each criterion c ∈ C such that p c ∈ W ∀ or np c ∈ W ∀ , whether or not x satisfies the criterion c. Agents will use arguments to justify their position. This process results in an attribution for each alternative x ∈ X of a set P x of satisfied features. Based on this outcome, the agents will then revise their preferences over the alternatives by considering their own desired features and the features considered as relevant by the group. Once again, agents will deliberate in a round robin manner and can skip their turn. The second phase ends after n successive turn skip. 5The way an agent can revise her preferences is to agree that the features chosen by the group are desirable for her too as she is part of the group. Then, each agent i can merge the features contained in W ∀ with her own set of desired features W i constructing thus a new set W i of desired features, being careful not to leave opposite features in W i . In case of a conflict, the feature extracted from W ∀ is more relevant than its opposite one initially in W i . The new preference relation of agent i ( i ) is then induced by W i and the collective knowledge gained on the alternatives. Definition 5 (Desired properties after deliberation). Let N be a set of agents, each agent i in N has a set of wanted properties W i . Let W ∀ be the set of consensual features obtained after deliberation. For all i in N , the new wanted features of i are defined as follows :

W i = (W i ∪ W ∀ )\({p ∈ W i | np ∈ W ∀ } ∪ {np ∈ W i | p ∈ W ∀ })
Let us formally define how the agents can interact with each other. In order to get a desired feature or a piece of knowledge accepted as relevant by the group, agents must justify their claims. To achieve this goal, arguments will be used. Classically, in this paper, we assume that agents possess a logical language allowing the construction of arguments. Here, an argument is a triple containing a set of premises, a set of rules and a conclusion which is derived from the premises using the rules [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF][START_REF] Besnard | A logic-based theory of deductive arguments[END_REF]. Agents can use arguments for different purposes according to possible actions. We define these actions as a set of possible speech acts [START_REF] Searle | Speech acts: An essay in the philosophy of language[END_REF]. This set contains the following locutions:

• assert(.) :

-Meaning : an agent uses this locution to formally prove a claim. -Usage : assert(i, arg) where i is in N and arg is an argument whose conclusion is the statement agent i wants to prove.

• reject(.) :

-Meaning : an agent uses this locution to formally reject a statement another agent made before. To achieve this goal, the agent uses an argument which proves that the statement she wants to reject is false.

-Usage : reject(i, j, F, arg) where i and j are in N and F is a set of premises previously used by j to prove a statement. Note that the conclusion of the argument arg and the rejected premises F are logically incompatible.

• challenge(.) :

-Meaning : an agent uses this locution to ask another agent to justify some premises she used in order to prove a statement.

-Usage : challenge(i, j, F ) where i and j are in N and F are premises used by j in order to prove a statement.

• retract(.) :

-Meaning : an agent uses this locution when she is unable to justify some premises she used to prove a statement.

-Usage : retract(i, arg) where i is in N and arg is an argument using premises i is unable to prove.

• concede(.) :

-Meaning : an agent uses this locution to explicitly accept a statement made by another agent.

-Usage : concede(i, j, arg) where i and j are in N and arg is an argument previously asserted by j whose conclusion is accepted by i.

These locutions allow agents to justify their positions. We will now see how they can use it to deliberate constructively.

Reply Structure In order to maintain a coherent dialogue, agents have to use locutions in a constructive way. Speech acts are subject to a particular reply structure ensuring that each locution is used for a correct purpose. This reply structure is described in Table 2. We can see, for example, that the retract(.) locution might be used by an agent to respond to a challenge(.) locution. This challenge(.) locution, in turn, might be used by someone else to ask for a justification about a claim made earlier using the assert(.) or the reject(.) locution.

Correctness Conditions

In order to avoid misuses of the locutions, they are subject to a set of conditions which comply with the reply structure. The conditions that must be satisfied in order to use a specific locution are listed in Table 3. These conditions ensure that agents deliberate in a focused manner. Commitment Store Effects Due to the previous conditions, each action performed by an agent is done for a particular purpose. In order to track the effects of these actions on the dialogue, the use of some speech acts is subject to post conditions which imply commitment store modifications. For each agent i ∈ N , CS(i) is the set of arguments that i has explicitly accepted, her commitment store. The effects of each locution on agents' commitment stores are shown in Table 4. By applying these modifications, each agent can know, at any time, the status of her preferences. This is necessary as agents have to revise their preferences after the deliberation ends. Now that the deliberation protocol has been formally defined, we can assess its quality for reaching consensus by characterising its impact on the number of possible alternative escalations agents will be able to do.

Impact of the Protocol on the Number of Possible Alternative Escalations

At the end of the deliberation process, each agent has a new set of desired features built according to Definition 5. As a consequence, we can make a first trivial observation: if there is a consensus on which features are desirable and as they all share the same knowledge over the alternatives, then all the agents will have the same preferences and the application of pairwise majority will always give a transitive result.

Lemma 1 (Absence of unshared features). When deliberation ends, if no agent desires an unshared feature then the result of pairwise majority on the induced agents' preferences is transitive.

We have seen that absence of unshared features benefits transitivity, it is thus interesting to track their evolution during the deliberation phase. The Lemma 1 guarantees a transitive result in case of consensus. The following result ensures that the deliberation process allows agents to move closer to such consensus. The proof consists in verifying that (i) an unshared feature can only become a consensual one and (ii) a consensual feature cannot become an unshared one.

Locutions

Using conditions assert(i, arg)

The arg argument was never asserted before.

reject(i, j, F, arg) The rejected premises in F were used by j to prove some statement that i is rejecting. The conclusion of argument arg and the premises in F are logically incompatible with respect to the logical language considered.

challenge(i, j, F ) The challenged premises in F were used by j to prove some statement that i has not yet accepted.

retract(i, arg)

The argument arg was asserted by i.

concede(i, j, arg)

The argument arg was asserted by j.

Lemma 2 (Diminution of unshared features). The number of unshared features can only decrease during the deliberation.

At the end of the deliberation, the agents agree on a set W ∀ of desirable features for the group that induces a preference relation W ∀

. Then, the unshared features of each agent i ∈ N will let her modify W ∀ in order to obtain her new individual preferences i . Let us try to identify the alternative escalations that an agent can perform on W ∀ according to her residual unshared features. Let x, y ∈ X be two alternatives such that x W ∀ y and i ∈ N an agent. In order to obtain y i x by changing W ∀ , i needs a certain number of unshared features. Let us suppose that x satisfies exactly one more feature of W ∀ than y. Then, i will strictly prefer y over x only if there exist two unshared features (not in W ∀ ) p 1 and p 2 in W i desired by i such that y satisfies both and x satisfies none. One can generalise this result for scenarios in which the difference di(x, y) of number of features in W ∀ satisfied by x and y is greater than 1. In such cases, at least di(x, y) + 1 unshared features satisfied by y but not by x must be desired by i to obtain y i x.

Based on this observation, we can now use Lemma 2 to obtain the following theorem which links the alternative escalation parameter used in the experiments of Section 3.2 to the number of unshared features.

Theorem 1 (Maximum number of possible modifications). Given M ax the maximum value of di(x, y) among all pairs of alternatives (x, y) ∈ X 2 , an alternative escalations in W ∀ .

Hence, during the deliberation, the more the agents are able to bring effective arguments, the less they will away from the preference relation W ∀ induced by W ∀ , which will bring them closer to consensus.

Discussion

In this paper, we tried to answer the following question: is it possible to assess formally the possibility of defining a deliberation protocol moving agents' preferences closer to particular structures (single-peakedness, triple wise value restriction, etc.) ensuring a transitive result under pairwise majority? We started by defining agents' preference formation based on the notion of desired features and used the notion of alternative escalations to represent how agents might diverge from the preference relation induced by the group's desired features. Using these notions, we proposed an experimentation showing that less alternative escalations leads to agents' preferences being closer to useful preference structures. Finally, we defined a simple deliberation protocol and characterised it in terms of its impact on the number of possible alternative escalations. While the presented work answer our initial problem, it raises many other questions. We present them in the following paragraphs.

Preferences formation Although the results of the experiment seem to confirm the hypothesis that the deliberation protocol improves the agents' preferences structure 6 , we observed that our simulation choices have some consequences. In particular, the way in which individual preferences are generated through alternative escalations impacts the separability into two groups measure. In our experiment, agents are assumed to be completely independent of each other and to perform alternative escalations in a random way. This way to deal with agents is reminiscent of how one can generate individual preferences under the impartial culture assumption [START_REF] Guilbaud | Les théories de l'intérêt général et le problème logique de l'agrégation[END_REF]. Unfortunately, impartial culture is known to be unrealistic and seems likely to maximise the probability of obtaining majority cycles [START_REF] Tsetlin | The impartial culture maximizes the probability of majority cycles[END_REF]. For these reasons, it would be interesting to study other ways of generating preferences and disagreements between agents.

Deliberation protocol

We deliberately chose to leave aside the argumentation part of the deliberation protocol. However, considering the argument exchange part it is necessary to decide on several points. For instance, what would happen if two agents have rational justifications for opposite features? Or if they desire the same feature but with contradictory justification? Considering argumentation systems [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] during the deliberation could allow the resolution of such conflicts and help agents deciding which justifications should be taken into account.

Measures generalisation In the experiment carried out, we have chosen to generalise the various measures of proximity to the whole set of triplets of alternatives by observing the proportion of triplets satisfying the desired condition. Several reasons motivated this choice, such as the fact that for extreme values the measure remains consistent (a measure of 1 means that the condition is true for the preference profile as a whole, a measure of 0 means that the condition is absolutely unverified).

That being said, it would be interesting to consider other approaches to measure the efficiency of the deliberation, for instance by studying the link between the distribution of unshared features and the probability of obtaining a non-transitive result using pairwise majority.

Real-life situation Finally, setting up a real-life experimentation would allow to focus on other aspects of deliberation. Indeed, in addition to confirming or refuting the experimental results of this work, it would let us assess to which extent people are able to identify desirable features and to defend them using rational arguments.

Figure 1 :

 1 Figure 1: Proximity to single-peakedness : 200 agents.

Figure 2 :

 2 Figure 2: Proximity to single-peakedness : 20 agents.

Figure 3 :

 3 Figure 3: Proximity to sep. into two groups : 200 agents.

Figure 4 :

 4 Figure 4: Proximity to sep. into two groups : 20 agents.

Figure 5 :

 5 Figure 5: Proximity to Triple wise value rest. : 200 agents.

Figure 6 :

 6 Figure 6: Proximity to Triple wise value rest. : 20 agents.

Table 2 :

 2 Locutions and their respective attacks and surrenders.

	Locutions	Attacks	Surrenders
	assert(.)	reject(.)	concede(.)
		challenge(.)	retract(.)
	reject(.)	challenge(.)	retract(.)
		reject(.)
	challenge(.) assert(.)	retract(.)
	retract(.)	∅	∅
	concede(.)	∅	∅

Table 3 :

 3 Locutions and their using conditions.

Table 4 :

 4 Locutions and their effects on Commitment Stores.

	Locutions	Commitment store effects
	assert(i, arg)	Add arg to CS(i).
	reject(i, j, F, arg) Add arg to CS(i).
	challenge(i, j, F ) -
	retract(i, arg)	Remove arg from CS(i)
	concede(i, j, arg)	Add arg to CS(i).
		ui
		M ax+1

agent i ∈ N with u i unshared features will be able to do at most

The pairwise majority aggregation method is known to be unanimous, independent to irrelevant alternatives and non-dictatorial.

Please note that Dietrich et al.[START_REF] Dietrich | Where do preferences come from ?[END_REF] suppose that agents can have a preference relation over features and thus they can discriminate between two alternatives satisfying the same number of desired features. Intuitively, the importance given to a feature depends on the context.

In this case, the Condorcet winner is the most preferred alternative of the median voter[START_REF] Black | The median voter theorem[END_REF].

Case of the Condorcet paradox for example.

Please note that for simplicity purposes, we assume here that both phases always succeed, i.e. all the agents manage to agree on a set of desired features and on the features satisfied by the alternatives.

This observation is in line with the experimental results obtained by List et al.[START_REF] List | Deliberation, singlepeakedness, and the possibility of meaningful democracy: evidence from deliberative polls[END_REF] in 2012.