Olivier Company
email: <company@lirmm.fr

Franc ¸ois Pierrot

Jean Christophe Fauroux

A Method for Modeling Analytical Stiffness of a Lower Mobility Parallel Manipulator

Keywords: Parallel manipulator, Stiffness modeling, Lower mobility, Articulated traveling plate

The H4 robot is a parallel machine with four degrees of freedom. The purpose of this work is to evaluate the H4 stiffness, ie the displacement response of the tool controlled point when it is submitted to a given force using an analytical method. A stiffness analysis based on analytical calculations is performed. It has the advantage to be rather fast and easy to integrate into a design optimization. This method allows to compute stiffness matrix of parallel robots and takes into account particularity of parallel robots with articulated traveling plate. Some numerical results are shown at the end of this paper for the H4 first prototype.

I. INTRODUCTION

Parallel manipulators are still a broad topic of research and the possible mechanical architectures are not all discovered yet. Since the first publications on this topic, the major part of research efforts was devoted to six-degree of freedom (dof) manipulators [START_REF] Merlet | Les robots paralèles[END_REF], mainly hexapods like Gough [START_REF] Gough | Contribution to discussion of papers on research in automotive stability, control and tyre performance[END_REF] or Stewart [START_REF] Stewart | A platform with 6 degrees of freedom[END_REF] platforms.

Clavel contributes to a new phase in research on parallel manipulators by putting the focus on lower mobility parallel mechanisms by publishing his results on the Delta Architecture [START_REF] Clavel | Delta, a fast robot with parallel geometry[END_REF] at the end of the 80's. This four-dof robot has the same motions (Schoenflies motions [START_REF] Hervé | The lie group of rigid body displacements, a fundamental tool for mechanism design[END_REF]) as a serial SCARA arm while being light weight. As a consequence, H4 robot is well suited to high speed pick-and-place tasks.

A lot of authors work on improving lower manipulability parallel manipulators by finding new architectures [START_REF] Brogardh | PKM Research -important issues, as seen from a product development perspective at ABB robotics[END_REF]. The H4 robot created by the authors in 1999 has the same motions ie three translations plus one rotation about a given axis (vertical axis has been chosen for the prototype).

Stiffness is a crucially important performance specification of parallel kinematic machines. In order to get a real industrial machine, the H4 prototype (Fig. 1) must be optimized. Because of its long arms and rods, designers must be particularly careful with the machine stiffness, which has direct consequences on manipulation accuracy [START_REF] Svinin | On the stiffness ans stability of gough stewart platforms[END_REF]. Several studies were performed by inventors to determine the geometric model, the usable workspace and the forces into the machine components [START_REF] Pierrot | H4 parallel robot: modeling, design and preliminary experiments[END_REF]. The work presented in this paper is about stiffness modeling of H4 robot and can be easily extended to lower manipulability parallel manipulators and manipulators with articulated traveling plate. This paper is divided in four parts:

• firstly the robot kinematics and its parameters are described

• the method is introduced • and developed in the fourth section • numerical results and comments are given in the last section The conclusion of this paper mentions the feed-back of this work on the design of future parallel manipulators.

II. ROBOT KINEMATICS DESCRIPTION

Robot kinematics can be described by its joint-andloop graph (Fig. 2) where each box stands for a revolute (R) or spherical (S) joint (see table I). Grey boxes stand for actuated joints. Robot practical design is extremely simple thanks to the use of DD motors. Rods are made of carbon fiber; arms, forearms and traveling plate are made of aluminum alloy. Before going further robot's geometry must be modeled. As depicted on Fig. 3: • P i is a point belonging to i th actuator's revolute axis (i = 1..4)

• u i is the unitary vector defining the rotation axis • A ij is the center of ball joint number j on the actuator side (j = 1..2)

• A i is the middle of A i1 and A i2 • B ij is the center of ball joint number j on the traveling plate side H4 robot prototype was built according to the following simplifying hypothesis:

• B i is the middle of B i1 and B i2 • v k is
• Points P i and A i are supposed to be located in the same plane perpendicular to u i

• All forearms are supposed to have the same length r • All bars are supposed to have the same length l Geometrical constraints (these constraints are required to have robot's end point desired displacements ie three translations and one rotation about z axis [START_REF] Pierrot | H4: a new family of 4-dof parallel robots[END_REF]):

• Vector defined by A i1 and A i2 is collinear to u i • Vector defined by B i1 and B i2 are collinear to u i • v  and v  are collinear to z axis and are replaced by z in following developments As this robot has a particular architecture, some explanations about its behavior are now given. The robot is composed by four "legs" linking the fixed part (with the reference frame visible in Fig. 3) to the traveling plate. Mainly, technology and working principle is identical to Delta robot. The major improvement is based on the use of an articulated traveling plate instead of a rigid one. The shape of the traveling plate looks like letter "H" composed by two lateral bars linked to the central bar by two revolute joints. Each leg is composed by a forearm and a "spatial parallelogram" ie a four bar linkage with spherical joints, each side having the same length as the opposite one.

When the robot is assembled, lateral bars are parallel to each other. In such a configuration, if geometrical design rules are respected during the design stage, "spatial parallelograms" are planar. When the robot moves, excepted for singular configurations, the lateral bars remain parallel and "spatial parallelograms" planar. The end effector is linked to the central bar. Its possible displacements are three translations and one rotation about a given axis. This rotation is obtained by internal deformation of the articulated traveling plate.

When robot components don't have their theoretical geometry due to bad manufacturing process or deformation linked to external forces applied to the robot, following changes occur:

• Traveling plate doesn't remain parallel when moving • Lateral bars don't remain parallel to each other To extend the range of motion of the traveling plate (limited to 45 degrees) and to reach a 180-degree rotation capability in both directions, traveling plate design has been improved and equipped with a mechanical amplification system with a ratio of 4:1 that can be seen on Fig. 4. This device was excluded from the stiffness modeling presented in this paper.

III. STIFFNESS MODELING METHOD

In this section, a method giving a good estimate of robot stiffness is presented. This method is similar to the one presented in [START_REF] Svinin | On the stiffness ans stability of gough stewart platforms[END_REF] for a Gough Stewart Platform, assuming that machine elements are considered as springs. The advantage of this method is to provide results with low computation time that can easily be integrated during the robot design stage in an iterative design process or in a stiffness optimization procedure. This method is based on classical mechanical tools and equations. The application of this method to lower mobility parallel mechanisms is more difficult than the one for hexapods (presented in [START_REF] Svinin | On the stiffness ans stability of gough stewart platforms[END_REF]). Moreover, H4 robot has particularities that must be integrated to the model and complicate this modeling:

• legs stress is not only tension/compression but also includes bending of the arms

• the traveling plate is not "rigid" because of the two passive joint added For this method (see Fig. 5) virtual forces and torques are applied on the end point. The load of all the robot elements is derived. Giving this load, elements deformation is computed. Using small displacement theory (first order approximation), end point displacement is computed. As a final result a relation between an applied force and a resulting displacement is obtained in a linear form. Matrix contained in this relation is then considered as the robot stiffness matrix.

IV. ANALYTICAL DEVELOPMENTS

A. Preliminary statements

The goal of this first subsection is to find linear relations between displacement of characteristic points and end point displacement (step 4 of the method Fig. 5). To do so, finite displacement theory is used. The following relations give machine geometrical models:

w ij 2 = l 2 ij i = 1..4, j = 1..2 (1)
where w ij is the vector linking point A ij to B ij . First order approximation gives:

(δb ij -δa ij ).w ij = l ij .δl ij (2)
where δa ij (resp. δb ij ) is the change in vector linking point O to A ij (resp. B ij ).

In this relation, δl ij and δa ij depend directly on machine elements deformation. δb ij depends on end point displacement and traveling plate displacement. When a load is applied on machine elements, their geometry change and nominal conditions expressed in section II are no longer respected. Under load, additional displacements must be considered: central bar rotation around y and z axes, and rotation of lateral bars around v  or v  axes. In fact, the traveling plate is considered as a mechanism composed by rigid bodies. A set of eight parameters is necessary to express traveling plate possible spatial displacements (including its internal dof). The vector used to model its displacement is:

δtp = δD T δΩ T δω 1 δω 2 T (3)
where:

• δD is vector composed by Cartesian coordinates of point D displacement

• δΩ is vector composed by rotation angles of robot end part

• δω k is the rotation angle of revolute joint number k

(k = 1 for i ∈ 1, 2, k = 2 for i ∈ 3, 4 ) δc k = δd + s k × δΩ (4)
δb ij = δc k + t ij × (δω k z + δΩ) (5)
where δc k (resp. δd ) is the change in vector linking point O to C k (resp. D ) and s k (resp. t ij ) is the vector linking point C k to D (resp. B ij to C k ). All this set of equations can be easily written in a linear form:

M  .δtp = M  .δ (6)
where:

M  = w ij T (w ij × (s k + t ij )) T • • • (w ij × t ij ).z 0 0 (w ij × t ij ).z M  = spar([w ij ] T ) diag([l ij ] T ) δ = δa  • • • δa  δl 11 • • • δl 42
Note that dimension of δ is 34. spar() operator is defined as follows:

spar(X) =      X   • • •   X      . . .   • • •  X n      (7)
where matrix X has n lines and X i is the i th line of matrix X . Now, displacement of all characteristic points of the mechanism are computed for a virtual force applied to the traveling plate (steps 1,2 and 3).

B. Displacement of point A 1) Actuator control stiffness:

The kinematics I/O law of this robot can be written as:

J x . ẋ = J q . q or ẋ = J. q (8)
where:

• ẋ = ẋ ẏ ż θ T is the vector composed by cartesian and angular velocities of end point • J, J x and J q are jacobian matrices • q is the vector composed by actuators angular velocities

Let's consider a force F d and torque T d applied to the end point D about possible displacement directions of the traveling plate. If there is no friction in the robot, then input power equals output power that leads to (as this relation is valid for every set of q and Γ act ):

Γ act = J T .Γ d (9)
where • Γ act is the vector composed by actuators torque

• Γ d = F d T T d .z T If k c
is the angular control stiffness of the actuator -all actuators are supposed to be identical, the angular displacement ∆q of the actuators is :

∆q = J T .Γ d /k c ( 10
)
This can be written:

δ cont = M  ∆q (11)
with:

M  = spar([ (p i × u i ) T (p i × u i ) T ])  T
where p ij is the vector linking point A ij to P i

δ cont = M  .J T .Γ d /k c (12)
2) Forearms bending stiffness: In this subsection, only bending moment around u i is taken into account. Bending in other directions can be negligible for the geometry of the studied robot because the biggest component of forces that produces bending is along z axis. Another reason is that the effects of bending in other directions on traveling plate displacement are lower.

Forearms are considered as constant section beams with a pure force applied to one end. This force can be expressed as:

f f = Γ act /r (13)
Displacement of points A i is then perpendicular to forearms and to vector u i . As all forearms shapes and material are identical, the norm of this displacement can be expressed as:

δA f = r 3 3.E.I f f (14)
where:

• E is Young's modulus of forearm material • I is the quadratic momentum of the beam section This leads to:

δ bend = r 3.E.I .M  .J T .Γ d (15)
3) Forearms torsion stiffness: Considered deformations generate a set of displacements compatible with geometrical conditions mentioned in section II. As a consequence, displacements belong to the set of possible displacements of the robot. Considered forces belong are the controlled forces ( force and torque that the robot end point can apply on an external object). The dimension of this set is four. Now, torsion deformations in forearms and tension in bars can change all the set of parameters describing traveling plate position which dimension is eight.

Let's now consider torsion effects in forearms. Firstly, forces in bars must be computed. The stress in each bar is tension-compression. Forces applied to forearms have the same direction as the considered bars. These computations need a complete set of forces and torque applied to the traveling plate applied to the traveling plate. The considered external actions are F d , torque T d applied to the end point D and two torques about z applied on revolute joints between central and lateral bars t 1 and t 2 .

Traveling plate equilibrium leads to:

Γ ext = J b F b (16)
where:

• Γ ext = F d T T d T t 1 t 2
T is the vector composed by extended external forces corresponding to the dual of traveling plate possible displacements expressed in eq. 8 .

• J b is the jacobian matrix relative to forces in bars

• f b = f b11 f b12 f b21 • • • f b42
T is the vector composed by the force in each bar ( f bij is the tension load in bar number ij)

If J b is not singular: f b = J b -1 Γ ext (17)
Resulting torque t ti applied on the forearm (point A i ) number i is:

t ti = j f ij p ij × w i ( 18
)
w i is an unitary vector collinear to vector linking A i to B i . As for bending effects, only torsion around the forearm axis is taken into account. Torsion torque applied to forearm i around its axis is:

τ i = -t ti .r i ( 19
)
where r i is the unitary vector collinear to vector linking points A i and P i Torsion angle can be expressed as:

δα i = r G.I 0 τ i ( 20
)
where G is Coulomb modulus of the material and I 0 the polar momentum of the section.

Displacement of point A ij is:

δA ij = p ij × δα i r i (21)
δA ij = - r G.I 0 (p ij × r i ) j (f ij p ij × w i ).r i (22)
δ tors = r G.I0 M  J b -1 Γ ext (23)
with:

M  = spar(N )  N = [p i × r i ] T [p i × r i ].w i [p i × r i ] T [p i × r i ].w i [p i × r i ] T [p i × r i ].w i [p i × r i ] T [p i × r i ].w i

C. Changes in bars length

Changes in bars length are linked to bars stiffness. According to derivations made in previous sections, forces in bars are given by the relation:

F b = J b -1 Γ ext (24)
Change in bars length is:

δl = l S b .E b f b (25)
where S b is the area of bars section and E b is Young's modulus of bars material

δl = l S b .E b J b -1 Γ ext (26) δ tens = l S b .E b M  J b -1 Γ ext (27)
with:

M  =  diag(ones(1, 8))

D. Machine end point final displacement

The following relation gives machine end point final displacement obtained when forces and torque are applied to the traveling plate (step 5) by summing all displacements:

δtp = M  -1 M  (δ cont +δ bend +δ tors +δ tens ) (28)
And the following expression is derived:

δtp = KΓ ext ( 29
)
where K is defined here as the stiffness matrix:

K = M  -1 M  1 kc M 3 J T R + • • • M 3 r 3E.I J T R + r G.I0 M 4 J -1 b + l S b .E b M 5 J -1 b (30)
with:

R =    
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0

   
As mentioned in the beginning of subsection IV-B.3, bending and control stiffness need a four dimension force input, torsion and tension need a eight dimension force input. As the final displacement is the sum of all these displacements for a given force, the selection matrix R must be used.

V. STIFFNESS EVALUATION

In this section, results of stiffness analytical modeling are compared to some experimental stiffness measurements on H4 robot prototype.

A. Dimensions and mechanical characteristics

Dimensions of the modeled prototype are (dimensions are expressed in millimeters):

B. Numerical results

Experimental stiffness measurements were done on H4 robot, by applying a force on the traveling plate and measuring the resulting displacements about three directions (x, y and z) using dial indicators (see Fig. 6 and and a detailed description in [START_REF] Corradini | Evaluation of a 4-degree of freedom parallel manipulator stiffness[END_REF]). Results obtained using these two different methods are presented in table II. Only translational response of the mechanism in x, y and z directions is measured for forces applied in x, y and z directions. Measurements have been done for one pose that is workspace center ie all actuators angle q i is equal to 45. Its is obvious that, due to its particular architecture, when a force is applied on the robot, the resulting displacement direction is not the same as the one of the force. Number given in table II are translational stiffnesses for a given pose expressed in m/N . The main result is that stiffness in x direction is bad regarding other directions. This stiffness study shows that the choice of robot actuators location on the machine frame does not provide good results.

The estimated results and the measured ones are "similar" due to approximations in the modeling phase. But estimated results are pessimistic regarding measured ones because some technological considerations have not been taken into account. All forearms length are considered to be stressed in bending and torsion, but in the prototype assembly, only 2/3 of the forearms length are stressed. More over, these parts are the weak point of the prototype regarding stiffness.

VI. CONCLUSION

In this paper a method for stiffness modeling of lower mobility parallel manipulators is presented and applied to a H4 robot whose particularity is to have an articulated traveling plate. This analytical method is very fast and useful for the design stage. For better quality results, a FEM analysis can be conducted once all the dimensions of robot parts are chosen. Analytical results are compared to experimental results and allow to have an interesting feed-back on the design of future parallel H4-like robots:

• actuators placement (that implies legs placement) is bad and cannot be modified into a symmetrical placement because of the architecture: the robot has a null stiffness in one direction for a symmetrical placement

• as a consequence, a new articulated traveling plate (with a different kinematics) has to be designed to allow a symmetrical design of the robot. This will contribute to reduce stiffness anisotropy.

• forearms shape and material need to be modified as they are the weak point of the robot

Fig. 1 .

 1 Fig. 1. H4 robot prototype

4 •Fig. 2 .

 42 Fig. 2. H4 robot -joint-and-loop graph

Fig. 3 .

 3 Fig. 3. H4 robot -CAD model and parameters

v 1 v 2 C 1 DFig. 4 .

 214 Fig. 4. H4 robot: Close view of traveling plate and parameters

  1 -F o r c e a n d t o r q u e a p p l i e d t o e n d p o i n t 2-S t r e s s i n m a c h i n e e l e m e n t s 3 -M a c h i n e e l e m e n t s d i s p l a c e m e n t 4 -E n d p o i n t r e s u l t i n g d i s p l a c e m e n t 5 -T o t a l e n d p o i n t d i s p l a c e m e n t

Fig. 5 .

 5 Fig. 5. Method for analytical stiffness modeling

  7, 4.10 6 N mm/ • E = 70000N mm -2 I = 1, 6.10 4 mm 4 G = 0, 4E I 0 = 2I S b = 28mm 2 E b = 200000N mm -2

Fig. 6 .

 6 Fig. 6. Experimental setting scheme

TABLE I KINEMATIC

 I CHAINS DESCRIPTION

	symbol P R U C	joint name prismatic revolute universal cylindrical	symbol S X X	joint name spherical with sensor actuated

TABLE II COMPARISON

 II BETWEEN EXPERIMENTAL AND COMPUTED RESULTS


Noortje J Venhuizen
email: n.j.venhuizen@rug.nl

Valerio Basile
email: v.basile@rug.nl

Kilian Evang
email: k.evang@rug.nl

Johan Bos
email: johan.bos@rug.nl

Gamification for Word Sense Labeling

Obtaining gold standard data for word sense disambiguation is important but costly. We show how it can be done using a "Game with a Purpose" (GWAP) called Wordrobe. This game consists of a large set of multiple-choice questions on word senses generated from the Groningen Meaning Bank. The players need to answer these questions, scoring points depending on the agreement with fellow players. The working assumption is that the right sense for a word can be determined by the answers given by the players. To evaluate our method, we gold-standard tagged a portion of the data that was also used in the GWAP. A comparison yielded promising results, ranging from a precision of 0.88 and recall of 0.83 for relative majority agreement, to a precision of 0.98 and recall of 0.35 for questions that were answered unanimously.

Introduction

One of the core aspects of semantic annotation is determining the correct sense of each content word from a set of possible senses. In NLP-related research, many models for disambiguating word senses have been proposed. Such models have been evaluated through various public evaluation campaigns, most notably SenseEval (now called SemEval), an international word sense disambiguation competition held already six times since its start in 1998 [START_REF] Kilgarriff | Framework and results for English SENSEVAL[END_REF].

All disambiguation models rely on gold standard data from human annotators, but this data is timeconsuming and expensive to obtain. In the context of constructing the Groningen Meaning Bank (GMB, [START_REF] Basile | Developing a large semantically annotated corpus[END_REF], a large semantically annotated corpus, we address this problem by making use of crowdsourcing. The idea of crowdsourcing is that some tasks that are difficult to solve for computers but easy for humans may be outsourced to a number of people across the globe. One of the prime crowdsourcing platforms is Amazon's Mechanical Turk, where workers get paid small amounts to complete small tasks. Mechanical Turk has already been successfully applied for the purpose of word sense disambiguation and clustering (see, e.g., [START_REF] Akkaya | Amazon mechanical turk for subjectivity word sense disambiguation[END_REF][START_REF] Rumshisky | Word sense inventories by nonexperts[END_REF]. Another crowdsourcing technique, "Game with a Purpose" (GWAP), rewards contributors with entertainment rather than money. GWAPs challenge players to score high on specifically designed tasks, thereby contributing their knowledge. GWAPs were successfully pioneered in NLP by initiatives such as 'Phrase Detectives' for anaphora resolution [START_REF] Chamberlain | Addressing the Resource Bottleneck to Create Large-Scale Annotated Texts[END_REF] and 'JeuxDeMots' for term relations [START_REF] Artignan | Multiscale visual analysis of lexical networks[END_REF]. We have developed an online GWAP platform for semantic annotation, called Wordrobe. In this paper we present the design and the first results of using Wordrobe for the task of word sense disambiguation.

Method

Wordrobe 1 is a collection of games with a purpose, each targeting a specific level of linguistic annotation. Current games include part-of-speech tagging, named entity tagging, co-reference resolution and word sense disambiguation. The game used for word sense disambiguation is called Senses. Below we describe the design of Wordrobe and the data used for Senses.

Design of Wordrobe

Wordrobe is designed to be used by non-experts, who can use their intuitions about language to annotate linguistic phenomena, without being discouraged by technical linguistic terminology. Therefore, the games include as little instructions as possible. All games share the same structure: a multiple-choice question with a small piece of text (generally one or two sentences) in which one or more words are highlighted, depending on the type of game. For each question, players can select an answer or use the skip-button to go to the next question.

In order to encourage players to answer a lot of questions and to give good answers, they are rewarded in two ways: they can collect drawers and points. A drawer is simply a unit of a few questions -the more difficult the game, the fewer questions are in one drawer. By completing many drawers, players unlock achievements that decorate their profile page. While drawers are used to stimulate answering many questions, points are used to motivate players to play with attention. The points are calculated on the basis of two factors: the agreement with other players who answered the same question and the bet that the player put at stake. Players can place a bet reflecting the certainty about their answer. The bet is always between 10% and 100% of the points that a question is worth. The default choice is a bet of 10% and once a player adjusts the bet, this new value is remembered as the new preset value for the next question. Higher bets will result in higher gains when the answer is correct, and lower points when the answer is wrong. Since Wordrobe is designed to create gold standard annotations, the correct choice is not defined (this is exactly what we want to obtain!). Therefore, the points are calculated on the basis of the answers given by other players, as in Phrase Detectives [START_REF] Chamberlain | Addressing the Resource Bottleneck to Create Large-Scale Annotated Texts[END_REF]. The idea is that the majority rules, meaning that the choice that gets selected most by human players is probably the correct one. So, the more players agree with each other, the more points they gain. As a consequence, the score of a player is continually updated -even when the player is not playing -in order to take into account the answers provided by other players answering the same questions.

Generation of questions for the Senses game

All Wordrobe games consist of automatically generated multiple-choice questions. In the case of Senses, the word sense labeling game, each question consists of one or two sentences extracted from the Groningen Meaning Bank with one highlighted word for which the correct word sense in the given context must be determined. Currently, the game only focuses on nouns and verbs, but it can be easily extended to include, e.g., adjectives and adverbs. The choices for the questions are automatically generated from the word senses in WordNet [START_REF] Fellbaum | WordNet. An Electronic Lexical Database[END_REF].

Of all the occurrences (tokens) of nouns and verbs in the GMB, 92.3% occurs in WordNet. This results in a total of 452,576 candidate questions for the Senses game. For the first version of Wordrobe, we selected a subset of the tokens that have at most five different senses in WordNet, such that the number of choices for each question is restricted. Figure 1 shows a screenshot of a question of Senses.

Results

The number of automatically generated questions for the first version of Senses was 3,121. After the first few weeks of Wordrobe going live, we had received 5,478 answers. Roughly half (1,673) of the questions received at least one answer, with an average of three answers per question. In order to test the validity of the method of using a GWAP to obtain reliable word sense annotations, we selected a subset of the questions with a reasonable response rate and created a gold standard annotation.

Gold standard annotation

We created a gold standard annotation for a test set of 115 questions with exactly six answers each, which was used to evaluate the answers given by the players of Wordrobe. Four trained human annotators individually selected the correct sense for each of the target words in the test set. Fleiss's kappa was calculated to evaluate inter-annotator agreement, resulting in κ = 0.79, which is generally taken to reflect substantial agreement. Unanimity was obtained for 64% of the questions and 86% of the questions had an absolute majority vote. In a second step of evaluation, the non-unanimous answers were discussed between the annotators in order to obtain 100% agreement on all questions, the result of which was used as the gold standard annotation.

Agreement measures

Given a question and a set of player answers, we need a procedure to decide whether to accept a particular choice into our annotated corpus. One important factor is agreement: if a great majority of players agrees on the same choice, this choice is probably the correct one. Smaller majorities of players are more likely to be wrong. Another important factor is the number of answers: the more players have answered a question, the more we can presumably rely on the majority's judgement. In this work, we focus on the first factor (agreement) because the average answer rate per question is quite low throughout our data set. We tested a couple of simple agreement measures that determine whether a choice is counted as a winning answer. We measure recall and precision for each measure with respect to the gold standard.

The simplest measure accepts every choice that has a relative majority. It always accepts some choice, unless the two choices with the most answers are tied. A stricter measure ("absolute majority") accepts only the choices that were chosen by at least a certain fraction of players who answered the question, with some threshold t ≥ 0.5. We used the values 0.5, 0.7 and 1.0 as threshold, the latter only accepting choices unanimously picked by players.

The measures described above simply choose the majority answer relative to some threshold, but fail to take into account the total number of players that answered the question and the number of possible choices for a question. These factors will become more important when we evaluate questions with a higher number of answers. We need a measure that determines whether the majority answer is chosen significantly more often than the other answers. This means that the answers should be significantly skewed towards one answer. In order to test such an effect, we can use Pearson's chi-square test, which determines the goodness-of-fit of a given distribution relative to a uniform distribution. If we take the distribution of answers over the set of possible choices, we can say that only those questions for which this distribution significantly differs from a uniform distribution (p < 0.05) are considered to provide an acceptable answer. Because the number of answers per question in our test set is relatively small, a significant result means that there is one choice towards which the answers accumulate. Determining which choice this is can accordingly be done using the relative-majority measure described above.

Evaluation

We evaluate the annotations obtained from Wordrobe by comparing the data of the test set (115 questions) to the gold standard. We used each of the agreement measures described above to select the answers with a high enough majority, and calculated precision (the number of correct answers with respect to the total number of selected answers), recall (the number of correct answers with respect to the total number of questions), and the corresponding F-score. The results are shown in Table 1. As expected, the highest recall is obtained using the relative majority measure since this measure is the least conservative in accepting a majority choice. As the threshold for accepting a choice is set higher, recall drops and precision rises, up to a very high precision for the unanimity measure, but with a significant loss in recall. The measure based on Pearson's chi-square test is similar in being conservative; having only six answers per question in the test set, only the questions that are very skewed towards one choice give a significant result of the chi-square test.

As described above, each answer is associated with a bet between 10% and 100% of the points available for a question, which players can adjust based on how certain they are about their answer. The distribution of bets over all answers shows two significant peaks for these extremes: in 66% of the cases the maximum bet was chosen, and the default minimum bet was chosen in 12% of the cases. The main motivation for inserting the betting function was to be able to identify questions that were more difficult for players by looking for low bets. We tested the correlation between the average bet per question and the relative size of the majority (indicating agreement between players) over all questions using Pearson's product-moment correlation and found a small but significant positive effect (r = 0.150, p < 0.01). We expect that this effect will increase if more data is available.

In order to test whether questions with high average bets were easier, we repeated the evaluation, including only questions with a high average bet: b ≥ 80% (see Table 2). Recall is reduced strongly, as one would expect, but we do observe an increase in precision for all measures except unanimity. This higher precision suggests that indeed the results of the questions for which players on average place a high bet are more similar to the gold standard. However, we will need more data to confirm this point.

Discussion

The goal of Wordrobe is to obtain annotations from non-expert annotators that are qualitatively close to gold standard annotations created by experts. This requires automatic techniques for filtering out lowquality answers. We evaluated the results obtained using some simple selection techniques with respect to a gold standard created by experts. We found that even with very conservative settings, optimizing for precision, we could still get a reasonably high recall (0.347). The highest precision, obtained using this most conservative measure (unanimity), was 0.975. In fact, a closer look at the data showed that there was exactly one question on which the choice unanimously picked by players differed from the gold standard annotation. This question is shown in (1).

(1) Although the last Russian troops left in 1994, the status of the Russian minority (some 30% of the population) remains of concern to Moscow. While according to the gold standard annotation the correct answer was (1b), the six players who answered this question in the game unanimously chose (1a) as the correct answer. This example illustrates the difficulty of the task at hand very well; one could argue for the correctness of both of the possible answers. In this case, the average bet posed by the players (83%) is not helpful either in determining the difficulty of the question. This example suggests that using a more fine-grained gold standard annotation, with a ranking rather than selection of possible answers, may result in higher quality results. Overall, the measures for calculating agreement show high numbers for precision, which were improved even more by only taking into account the questions that received a high average bet. The main drawback for this evaluation procedure is the restricted average number of answers per question. Although the recall for the unanimity measure remains at an acceptable level for the test set, this number is likely to decrease severely for questions with a higher number of answers. On the other hand, the measure based on the chi-square test is expected to become more reliable in the case of a larger dataset. In general, the evaluation measures discussed in section 3 are very basic and not robust against small datasets or unreliable annotators. With the recent uprise of crowdsourcing platforms such as Amazon's Mechanical Turk, there has been a revived interest in the task of obtaining reliable annotations from nonexpert annotators. Various methods have been proposed to model annotated data such that it can be used as a gold standard (see, e.g., [START_REF] Carpenter | Multilevel bayesian models of categorical data annotation[END_REF][START_REF] Snow | Cheap and fast-but is it good?: evaluating non-expert annotations for natural language tasks[END_REF][START_REF] Beigman Klebanov | From annotator agreement to noise models[END_REF][START_REF] Raykar | Learning from crowds[END_REF]. The goal of this paper was to provide a general idea of the quality of the data that can be obtained using games with a purpose. However, creation of a proper gold standard will require the collection of more data, and the use of more advanced techniques to obtain reliable annotations. As a first step towards this goal, we will make the data used in this paper available online,2 such that interested readers can perform their own evaluation methods on this data.

Conclusions and future work

In this paper we described and evaluated the first results about the use of a 'Game with a Purpose' for annotating word senses. Although the amount of data obtained for each question is still relatively small (the largest amount of answers given to a reasonably sized amount of questions was 6), the results on precision and recall compared to the gold standard annotation are promising. We proposed several measures for determining the winning answer of a question, and compared them with respect to the precision and recall results. In this paper we focused on obtaining high precision scores, because the goal of the project is to obtain gold standard annotations which can be used to improve the Groningen Meaning Bank [START_REF] Basile | Developing a large semantically annotated corpus[END_REF]. Future work will focus on obtaining larger amounts of data and evaluating the annotations as part of an integration into the GMB. Moreover, this method for obtaining annotations will be applied and evaluated with respect to other linguistic phenomena, such as named entity tagging, noun-noun compound interpretation, and co-reference resolution.

Figure 1 :

 1 Figure 1: Screenshot from Wordrobe game Senses.

  a. soldiers collectively (synonyms: military personnel, soldiery) b. a group of soldiers c. a cavalry unit corresponding to an infantry company d. a unit of Girl or Boy Scouts (synonyms: troop, scout troop, scout group) e. an orderly crowd (synonyms: troop, flock)

Table 1 :

 1 Precision and recall based on different agreement measures

	Strategy	Precision Recall F-score
	Relative majority	0.880 0.834	0.857
	Absolute majority (t = 0.5)	0.882 0.782	0.829
	Absolute majority (t = 0.7)	0.945 0.608	0.740
	Unanimity (t = 1)	0.975 0.347	0.512
	Chi-square test (p < 0.05)	0.923 0.521	0.666

Table 2 :

 2 Precision and recall based on different agreement measures for questions with b ≥ 80%

	Strategy	Precision Recall F-score
	Relative majority	0.917 0.478	0.629
	Absolute majority (t = 0.5)	0.930 0.461	0.616
	Absolute majority (t = 0.7)	0.956 0.383	0.547
	Unanimity (t = 1)	0.961 0.217	0.355
	Chi-square test (p < 0.05)	0.950 0.330	0.355

http://www.wordrobe.org/

http://gmb.let.rug.nl/

Acknowledgements

We'd like to thank Bob Carpenter for comments and discussion of the Wordrobe data, and the pointers he provided to related work. Obviously we also thank all Wordrobe players (962 so far) that generated so many answers (41,541 so far) in such a short time.


Antonio Bo

Christine Azevedo Coste

Christian Geny

Philippe Poignet

Charles Fattal

Tremor attenuation based on joint impedance modulation using FES

Keywords: Pathological tremor, Impedance modulation, Closed-loop FES control

Introduction

Tremor may be defined as an involuntary, approximately rhythmic and roughly sinusoidal movement [1] for which an absolutely effective treatment is not yet available. Although pharmacological and surgical therapies exist for the two most prevalent types of tremor, essential tremor (ET) and the tremor associated with Parkinson's Disease (PD), they still present limitations and hence one important alternative is the use of electrical stimulation to reduce the effects of tremor.

In this scenario, different technologies based on electrical stimulation have been proposed as an alternative for pathological tremor management. These therapies range from invasive interventions targeting specific structures in the brain, such as Deep Brain Stimulation (DBS) [START_REF] Grimaldi | Tremor: From Pathogenesis to Treatment[END_REF], to the stimulation of muscles involved in tremor using surface electrodes [START_REF] Prochazka | Attenuation of pathological tremors by functional electrical stimulation I: Method[END_REF]. However, the costs, effectiveness, and particularly the risks involved may vary greatly among these solutions.

In this work, we focus on the use of surface electrodes, such as in [START_REF] Prochazka | Attenuation of pathological tremors by functional electrical stimulation I: Method[END_REF], but with the main difference that FES is not used to generate an antiphase motion to counteract tremor, such as in the work from Prochazka. Our strategy here is to use FES to increase the impedance of the trembling joint in order to provide an effective functional benefit to the patient, i.e., reduce the effects of tremor while improving joint stability and minimizing the total associated discomfort and fatigue.

In order to evaluate the effectiveness of this strategy, open-loop and closed-loop trials were conducted involving one tremor patient and two healthy subjects.

Material and Methods

Methodology

The main compensation strategy applied in this work was based on the use of FES in order to increase joint impedance by co-contracting antagonist muscles and hence attenuate tremor. In a first moment, the validity of this approach was evaluated in open-loop experiments, i.e., the corresponding stimulation levels were tuned manually, and not in response to real-time readings from sensors measuring tremor. In this trials, the overall stimulation level was defined subjectively based on the subject's sensitivity, while the individual muscle FES intensity was chosen in order to reduce the induced motion on the joint.

Later, a closed-loop strategy based on the same general idea was developed. Within this approach, which was first detailed in [START_REF] Bó | Tremor attenuation using FES-based joint stiffness control[END_REF], portable sensors are used for online tremor estimation, and this information is then used by the control algorithm, which automatically sets appropriate stimulation levels that will increase joint impedance without affecting its motion.

In the scenario of assistive technologies for tremor attenuation, it is essential to use closed-loop strategies, since long-term use require constant evaluation of tremor onset.

Subjects and FES normalization

The experimental data discussed in this work refer to two different classes of subjects. First, the proposed approach was evaluated on open-loops trials involving one patient with ET. In the following stage, tests were conducted on two subjects with no neurological impairment, where tremor on the target joint was induced by an independent electrical stimulator.

Within the tests on healthy subjects, the target joint was the wrist, particularly the dorsi/palmar flexion. Two antagonist muscles were chosen for each subject to compose the pair of antagonist muscles to be controlled, such as the Flexor Carpi Ulnaris (FCU) and the Extensor Carpi Ulnaris (ECU). FES-induced tremor was produced by stimulating other muscles, such as the Flexor Carpi Radialis (FCR), the Palmaris Longus (PL), or the Extensor Digitorum Communis (EDC).

Due to inter and intra-subjects variations of electrically controlled muscles, each trial was preceded by a procedure where the maximum and minimum FES levels were set. The normalized stimulation level was computed based on these subjective limits. Stimulation frequency was constant in all experiments. The experimental setup is illustrated in Fig. 1. The stimulator is an 8-channel stimulator, the Prostim, designed jointly by the LIRMM and Neuromedics. The main sensor used in the control loop is the IDG-300, an angular rate sensor from Invensense, whose measurements are acquired by a National Instruments acquisition card. Both tremor tracking and tremor attenuation algorithms are executed in a 50 Hz-loop running in a Linux system. The whole system is electrically isolated to ensure the subject's safety.

Experimental Setup

In order to produce FES-induced tremor in trials involving healthy subjects, a commercial stimulator from CEFAR, the Physio 4, was used. It produces biphasic square pulses, opposed to the biphasic pulses with capacitive discharge generated by Prostim.

Results

In Figs. 2 to 4, motion data from tremor attenuation experiments involving one ET patient and two healthy subjects. For both open-loop and closed-loop trials, the periods when the compensatory FES system is turned on is highlighted using grey rectangles. Additionally, key features of each data set are indicated using black horizontal lines. Among the several trials conducted in this work, here we have chosen to illustrate those where a representative behaviour is observed. Those are qualitatively discussed within the Discussion. A more quantitative analysis of the method performance was conducted in [START_REF] Bó | Tremor attenuation using FES-based joint stiffness control[END_REF].

Discussion

The experimental results have illustrated the feasibility of attenuating the amplitude of tremor by co-contracting antagonist muscles acting on the concerned joint using FES. In this section, we discuss the scope of these results, focusing on the qualitative analysis of the different behaviours and on the limitations of the current protocol.

Concerning those limitations, important difficulties still prevent a complete evaluation of the method for different types of tremor. Some of these limitations refer to constraints of the stimulation technology used in the experiments. Indeed, since surface electrodes were used, correct positioning in order to minimize diffusion for other forearm muscles was a challenge.

Other limitations, however, were related to the very essence of the experiment. For instance, since pathological tremor is naturally variable in time, in some cases it is difficult to discern if tremor was attenuated due to the effect of FES, or if its amplitude was naturally decreased. Moreover, both patients and healthy subjects often react spontaneously to compensate tremor, while in ideal experimental conditions we would like to evaluate the effect of the stimulation only on tremor reduction.

However, even with those difficulties, the conducted trials have led to interesting conclusions. First, we have observed that the applied attenuation method is a feasible alternative for tremor patients, since no major complaints concerning pain or discomfort were made, and effective reduction on tremor amplitude was observed. Also, this attenuation on tremor amplitude was observed using both open-loop and closed-loop strategies on experiments involving both tremor patients and subjects with no neurological impairment.

Beyond those first conclusions, the obtained data may help us to further understand the effects FES may produce on joint impedance and consequently on tremor attenuation.

The data from Figs. 2 and3, for instance, illustrate that an adaptation period may exist between the first applied stimulation pulses and the consequent effect on tremor reduction. Since those adaptation periods were considerably longer than the expected values for the electromechanical delay between FES and muscle action, it is possible that the reaction from the subjects to the stimulation cause this effect. Indeed, in Fig. 4, an instantaneous tremor reduction was observed, indicating that this was probably a subject-dependent effect.

The data also enable further discussion on the modulation of joint active viscoelasticity due to FES and how this may affect tremor. Indeed, it may be inferred from Figs. 2 and 3 that a highintensity stimulation level may increase joint impedance such that stronger oscillations may also be attenuated. This observation is in accordance with the data from Fig. 4, where low-intensity stimulation parameters were chosen by the subject, in such a way that the faster peaks of tremor were barely attenuated.

Based on this discussion, it is likely that the performance of the proposed strategy is considerably dependent on the subject. First, in order to reduce the adaptation periods for tremor attenuation, and secondly for enabling higher stimulation levels that will produce more effective tremor attenuation.

Conclusions

In this work, we have presented an alternative method to attenuate the effects of pathological tremor using FES. The strategy is based on the use of electrical stimulation to modulate the joint impedance, and hence reduce the effects of tremor.

The strategy was evaluated on both patients and healthy subjects and satisfactory results were obtained. Furthermore, different interesting behaviours were observed on the tests, which may help on the improvement of the method. Future works will focus on the evaluation of the proposed method on longer trials involving daily tasks. In this way, we expect to compare the effectiveness of the approach with respect to alternative methods.

Fig. 1 :

 1 Fig. 1: The experimental setup used in this work.

Fig. 2 :

 2 Fig. 2: Open-loop trial on ET patient.

Fig. 3 :

 3 Fig. 3: Closed-loop trial on subject A.

Fig. 4 :

 4 Fig. 4: Closed-loop trial on subject B.

Acknowledgements

This work was partially funded by the Agence Nationale de Recherche, France, and Neuromedics/MXM, France.

Author's Address

Antônio Padilha Lanari Bó Universidade de Brasília antonio.plb@lara.unb.br http://lara.unb.br/~antonio


Nawal Benabbou

Serena Di Sabatino

Di Diodoro

Patrice Perny

Paolo Viappiani

Serena Di

Sabatino Di Diodoro

Incremental Preference Elicitation in Multi-Attribute Domains for Choice and Ranking with the Borda Count

Introduction

Voting is an effective method for collective decision-making, used in political elections, technical committees, academic institutions. Recently, interest in voting has increased in computer science, given the possibility offered by online web systems to support voting protocols, or protocols inspired by voting, for group decision-making (for example, for scheduling a meeting). In many real situations, however, it may be necessary to reason with partial preferences, as some preferences are not available and too expensive to obtain (with respect to a cognitive or economic cost). This observation has motivated a number of recent works on social choice with partial preferences, e.g., [8, 9, 3-6, 2, 12]. In this research stream, typical questions concern the determination of possible and necessary winners, the selection of preference queries to ask to the agents for further eliciting preferences, the approximation of optimal solutions or the determination of robust recommendations based on the available preference information.

Acquiring agents' preferences is expensive (with respect to time and cognitive cost). It is therefore essential to provide techniques that allow to reason with partial preference information, and that can effectively elicit the most relevant part of preferences to make a decision. Adaptive utility elicitation [START_REF] White | A model of multiattribute decision-making and trade-off weight determination under uncertainty[END_REF][START_REF] Wang | Incremental utility elicitation with the minimax regret decision criterion[END_REF][START_REF] Braziunas | Elicitation of factored utilities[END_REF] tackles the challenges posed by preference elicitation by representing the system knowledge about the agents' preferences in the form of a set of admissible utility functions. This set includes all functions compatible with the preferences collected so far, and is updated following agents' responses. In this way, one can often make good (or even optimal) recommendations with sparse knowledge of the users' utility functions.

The aim of this paper is to introduce an adaptive utility elicitation procedure in the context of voting, for the fast determination of a Borda winner or a social ranking based on the Borda score, and to test the practical efficiency of this procedure. In particular, we extend the work of [START_REF] Lu | Robust approximation and incremental elicitation in voting protocols[END_REF] to the multi-attribute case. Multiple attributes may appear in well-known collective decision problems such as committee elections or voting in multi-issue domains [START_REF] Lang | Sequential composition of voting rules in multi-issue domains[END_REF]. In these cases, attributes are boolean and represent elementary decisions on candidates or issues. More generally, the multi-attribute case occurs when the alternatives of a collective decision problem are described by different features, nonnecessarily boolean. Individual preferences are assumed here to be representable by a linear function of the attribute values. Since utilities are decomposable over attributes, a set of preference statements formulated by an agent on some pairs of alternatives will possibly allow to infer other preference statements with respect to other pairs, without asking them explicitly. We show in the paper how this type of inference mechanism can be implemented using mathematical programming to reduce the number of queries and speed-up the determination of a necessary Borda winner.

The paper is organized as follows: in Section 2, we introduce the basic framework for voting on multi-attribute domains. Then, we present the minimax regret decision criterion as a useful tool for decision under uncertainty and preference elicitation. In Section 3, we introduce a new method based on mathematical programming to minimize regrets based on the Borda count. Section 4 deals with preference elicitation for the Borda count; we introduce different strategies for generating preference queries and compare them experimentally. Finally, in Section 5, we extend the approach to ranking problems based on the Borda score and provide additional numerical tests to evaluate the efficiency of our approach in ranking.

Social Choice in Multi-attribute Domains with Incomplete Preferences

We consider a set of n voters or agents and a set X of m alternatives (candidates, options, items), characterized by a finite set of q attributes or criteria; an alternative is associated to a vector x = (x 1 , . . . , x q ) where each x k represents the value of an attribute k or a performance with respect to a given point of view. Individual preferences are assumed here to be represented by linear utilities of the form u i (x) = q k=1 ω i k x k , where ω i = (ω i 1 , . . . , ω i q ) is a vector of weights characterizing the preferences of agent i. Hence, an alternative x is as least as good as y for agent i whenever

q k=1 ω i k x k ≥ q k=1 ω i k y k .
Our framework can be used to address two different cases: a multi-criteria decision setting or a multi-attribute utility where the utility is defined as the weighted sum of attribute values. Formally, these preferences are defined by the following relation i :

x i y iff q k=1 ω i k (x k -y k ) ≥ 0
A preference profile 1 , . . . , n of an election is therefore completely characterized by the weight vectors ω 1 , . . . , ω n (each associated with an agent). We can now define the Borda score in our multi-attribute settings, where preferences are defined by the utility weights. Given ω = ω 1 , . . . , ω n , the Borda score s(x, ω) of an alternative x is

s(x, ω) = n i=1 s i (x, ω i )
where s i (x, ω i ) = |{y ∈ X | x i y}| counts the number of alternatives that are strictly beaten by x according to the preference relation induced from ω i , where i is the asymmetric part of i : x i y iff i and ¬(y i x). Our definition allows for ties in each ranking. When using only linear orders (i.e. the ω i s are such that there are no ties) we get the usual Borda count.

When the weights of the agents are not known to the system with certainty, we need to reason about partially specified preferences. This is done by assuming a vector Ω = Ω 1 , . . . , Ω n where each Ω i is the set of feasible ω i that are consistent with the available preference information on agent i. Later, we will use Ω (that represents our uncertainty about the weights associated with the agents) in order to provide a recommendation based on minimax regret. At the level of a single agent i, we can check whether pairs of alternatives are in a necessary preference relation given Ω i . Definition 1. Alternative x is necessarily weakly preferred to y for agent i, written

x N i y, iff ∀ω i ∈ Ω i , q k=1 ω i k (x k -y k ) ≥ 0.
Similarly, x is necessarily strictly preferred to y for agent i, written

x N i y, iff ∀ω i ∈ Ω i , q k=1 ω i k (x k -y k ) > 0.
The necessarily strictly preferred relation N i should not be confused with the asymmetric part 3 of the necessarily weakly preferred relation N i . At the level of the community of the agents, a possible Borda winner is an alternative such that there exists a feasible instantiation of the weights that makes it a Borda winner; a necessary Borda winner is a Borda winner for all feasible instantiations of the weights.

In general the sets Ω 1 , . . . , Ω n are not given directly but are inferred by available preference statements. Any preference statement of type x i y for agent i is indeed interpreted as a linear constraint ω i • (x -y) ≥ 0. Therefore, after collecting several preferences of this type, Ω i is a convex polyhedron in the space of weights.

When the utility weights are known and characterized by ω = ω 1 , . . . , ω n , the actual loss or real regret of an alternative x is the shortfall in Borda score that occurs by choosing x instead of the optimal choice x * ω ; more formally:

Regret(x, ω) = max y∈X {s(y, ω)} -s(x, ω) = s(x * ω , ω) -s(x, ω).
Instead, when the actual weights ω = ω 1 , . . . , ω n are not known, but some preferences are available, we are interested in quantifying how "bad" a choice can be with respect to the current uncertainty about the weights, encoded by Ω = Ω 1 , . . . , Ω n .

To this end, we first define pairwise max regret, then max regret and finally minimax regret as proposed in [START_REF] Wang | Incremental utility elicitation with the minimax regret decision criterion[END_REF][START_REF] Lu | Robust approximation and incremental elicitation in voting protocols[END_REF]. The pairwise max regret PMR(x, y, Ω) of alternative x relative to y under Ω is the worst-case loss, in terms of Borda score, of selecting the alternative x instead of y. The max regret MR(x, Ω) is the worst-case loss of choosing x: this can be viewed as an adversarial selection of the instantiation of the weights ω to maximize the loss between x and the true winner under ω. We want to choose the alternative x minimizing max regret: the minimax regret MMR(Ω) represents the smallest max regret under Ω. These concepts are formalized below:

PMR(x, y, Ω) = max ω∈Ω s(y, ω) -s(x, ω) , MR(x, Ω) = max y∈X PMR(x, y, Ω), (1)
MMR(Ω) = min x∈X MR(x, Ω). (2)
Finally the minimax optimal alternative x * Ω is any alternative x mininimizing regret MR over Ω (i.e. x * Ω ∈ arg min x∈X MR(x, Ω)). Solution x * Ω is an approximate winner of the current election according to the minimax regret criterion; it gives us the safest choice with respect to the uncertainty on the preference weights attached to the agents; this will be suggested as a recommendation for the social choice problem given the available preference information. We recall from [START_REF] Lu | Robust approximation and incremental elicitation in voting protocols[END_REF] the observation that the regretminimizing alternative may not be a possible winner. Another important property is that, if MMR(Ω) = 0, then x * Ω is a necessary winner.

Minimax Regret Computation for Borda

We are now interested in the computation of minimax regret, given the uncertainty sets Ω 1 , . . . , Ω n , when using Borda count as voting rule on a multi-attribute domain.

Note that the computation of the pairwise max-regret values PMR is the cornerstone of the problem: once we have computed PMR(x, y, Ω) for all x, y ∈ X, max regret MR(x, Ω) for all x and then minimax regret MMR(Ω) can be computed directly from the definitions (Equations 1 and 2).

The main intuition for computing minimax regrets comes from [START_REF] Lu | Robust approximation and incremental elicitation in voting protocols[END_REF]; however, in our multi-attribute settings, computing PMR is more involved as we need to deal with the multi-attribute structure of the domain. The key idea is to exploit the decomposition of PMR with respect to the different agents:

PMR(x, y, Ω) = n i=1 max ω i ∈Ω i s i (y, ω i )-s i (x, ω i )
This decomposition allows to decompose the PMR maximization problem into a series of simpler maximization problems. For each agent i, we maximise the contribution to PMR separately, which is defined as follows:

PMR i (x, y, Ω i ) = max ω i ∈Ω i s i (y, ω i ) -s i (x, ω i )
This optimization problem gives the maximal difference between the number of alternatives strictly less preferred than y and the number of alternatives strictly less preferred than x (according to the i th -agent's preferences); note that, if there is no tie, this corresponds to maximizing the difference between their rank. Let ω i be the weighted vector maximizing this value and i be the preference relation induced by ω i . From the definition of the scores, we have:

s i (y, ω i ) -s i (x, ω i ) = -|{z ∈ X, x i z i y}| if x i y |{z ∈ X, y i z i x}| otherwise
However, since we do not know in which case we are (ω i is not known), we make use of the necessarily preferred relation N i in order to check whether some conclusions can be drawn from the available information about the preference between x and y. More precisely, we distinguish whether it is known that x is necessarily weakly preferred to y or not. Then, we deduce the weighting vector that maximizes the contribution to regret of agent i. Note that checking whether x N i y can be simply performed using a linear program, by testing the condition min ω i ∈Ω i {(x -y) • ω i } ≥ 0}. We now express two mutually exclusive cases using the necessary preference relation.

1) case x N i y: in that case, we have s i (y, ω i ) -s i (x, ω i ) ≤ 0 for all ω i ∈ Ω i by definition of N i .
This induces that the contribution to PMR(x, y, Ω) is non-positive and more precisely, we have

PMR i (x, y, Ω i ) = -min ω i ∈Ω i |{z ∈ X, x i z i y}|.
Hence, to maximize the pairwise max regret PMR(x, y, Ω), we need to minimize over Ω i the cardinality of the set {z ∈ X, x i z i y} as much as possible.

2) case ¬(x N i y): there exists ω i ∈ Ω i such that s i (y, ω i )-s i (x, ω i ) ≥ 0 by definition of N i . Therefore, we know that the contribution to PMR(x, y, Ω) is non-negative here. More precisely, we have PMR i (x, y, Ω i ) = max ω i ∈Ω i |{z ∈ X, y i z i x}|. Hence, we need to maximize the cardinality of the set {z ∈ X, y i z i x} to maximize the pairwise max regret PMR(x, y, Ω).

In the following, we consider the problem of computing PMR i (x, y, Ω i ) for any x, y and i. First of all, we need to define the following sets for any a ∈ {x, y}:

U a = {z ∈ X \ {a}, z N i a}, L a = {z ∈ X, a N i z}, V a = X \ ({a} ∪ U a ∪ L a ) and for any pair of alternatives (a, b) ∈ {(x, y), (y, x)}: M a,b = L a ∩ U b , Z a,b 1 = L a ∩ V b , Z b,a 2 = U b ∩ V a , Z a,b 3 = V a ∩ V b
These sets are computed for each user i using linear programming (repeatedly testing N i or N i on pairs of alternatives) and allow us to partition the set X for the computation of PMR i (x, y, Ω i ). We refer the reader to Figure 1 where the different cases are visualized; for simplicity, we only show the transitive reduction of the preference relation and we distinguish whether it is known that y is necessarily weakly preferred to x or not (if not, set M y,x is empty). Note that, in the following, we may write Z 1 , Z 2 and Z 3 (dropping the superscripts) when the case considered is clear from the context.

M x,y x U x y L y Z x,y 1 Z y,x 2 Z x,y 3 (a) x N i y M y,x y U y x L x Z y,x 1 Z y,x 2 Z x,y 3 (b) ¬(x N i y) ∧ (y N i x) x y Z x,y 2 U x ∩ U y Z y,x 2 Z x,y 1 L x ∩ L y Z y,x 1 Z y,x 3 (c) ¬(x N i y) ∧ ¬(y N i x)
Fig. 1: Partition of set X with respect to the value of N i with x and y for agent i. The solid (resp. dashed) arcs represent necessary strict (resp. weak) preferences.

1) case x N

i y (Figure 1a): We want to compute PMR i (x, y, Ω i ). Recall that, in this case, PMR i (x, y, Ω i ) = -min ω i ∈Ω i |{z ∈ X, x i z i y}|. Hence, we want to find a feasible ω i ∈ Ω i such that as few of the alternatives z ∈ X are such that x i z i y. First, let us note that none of the alternatives z in U x ∪ L y verify x i z i y for some ω i ∈ Ω i (by definition of U x and L y ). Moreover, x i z i y for all alternatives z ∈ M x,y and all ω i ∈ Ω i (by definition of M x,y ). Therefore, we have:

PMR i (x, y, Ω i ) = -|M x,y | -min ω i ∈Ω i |{z ∈ Z 1 ∪ Z 2 ∪ Z 3 ∪ {y}, x i z i y}|
Thus, we need to compute min

ω i ∈Ω i |{z ∈ Z 1 ∪ Z 2 ∪ Z 3 ∪ {y}, x i z i y}| to de- termine PMR i (x, y, Ω i ).
We propose now a mixed-integer programming formulation (named MIP x,y ) to solve the latter optimization problem:

(MIP x,y ):

min b 0 + z∈Z1 b z 1 + z∈Z2 b z 2 + z∈Z3 b z 3 s.t. q j=1 ω i j = 1 (3)
ω i • (a -b) ≥ 0, ∀(a, b) ∈ P i ≥ ( 4
)
ω i • (a -b) ≥ ε, ∀(a, b) ∈ P i > ( 5
)
ω i • (y -x) + Cb 0 ≥ 0 (6)
ω i • (y -z) + Cb z 1 ≥ ε, ∀z ∈ Z 1 ∪ Z 3 (7)
ω i • (z -x) + Cb z 2 ≥ 0, ∀z ∈ Z 2 ∪ Z 3 (8) b z 3 ≥ b z 1 + b z 2 -1, ∀z ∈ Z 3 (9)
ω i j ≥ 0, ∀j ∈ {1, . . . , q}; b 0 ∈ {0, 1}; b z 3 ∈ {0, 1}, ∀z ∈ Z 3 b z 1 ∈ {0, 1}, ∀z ∈ Z 1 ∪ Z 3 ; b z 2 ∈ {0, 1}, ∀z ∈ Z 2 ∪ Z 3
In this program, the variables are ω i = (ω i 1 , . . . , ω i q ), a vector of q positive real numbers, binary variable b 0 and binary variables b z andb z 3 for each z ∈ Z 3 (we therefore have q

1 for each z ∈ Z 1 ∪ Z 3 , b z 2 for each z ∈ Z 2 ∪ Z 3 ,
+ |Z 1 | + |Z 2 | + 3|Z 3 | + 1 variables).
C is an arbitrary large constant value and ε is an arbitrary small and positive constant modelling strict inequalities. Constraint 3 simply states that the weights should be normalized to add up to 1. Constraints 4 and 5 model the fact that weight ω i should satisfy both the weak preference statements in P i ≥ and the strict preference statements in P i > obtained from agent i; indeed, set Ω i is defined by these preference statements.

Proposition 1 If x N i y, then PMR i (x, y, Ω i ) = -|M x,y | -OP T
, where OP T is the optimum of mixed-integer program MIP x,y .

Proof. We want to prove that min , so that we count the cardinality of {z ∈ Z 1 ∪ Z 2 ∪ Z 3 ∪ {y}, x i z i y}. We now prove that each binary variable is equal to one iff the corresponding constraint is satisfied. Since the objective is a minimization, the values of the binary variables b 0 , b z 1 , b z 2 and b z 3 (that appear in the objective function), will be 0 unless forced to 1.

ω i ∈Ω i |{z ∈ Z 1 ∪ Z 2 ∪ Z 3 ∪ {y}, x i z i y}| is the optimum of MIP x,y , i.
The binary variable b z 1 , for z ∈ Z 1 , represents whether alternative z verifies x i z i y. Equation 7 indeed enforces b z 1 = 1 when ω i • (z -y) ≥ 0, i.e. when z i y; otherwise, variable b z 1 is set to zero since we are minimizing the objective function. Then, since x i z (by definition of Z 1 ), we have that b z 1 = 1 iff x i z i y. For all alternatives z ∈ Z 2 , we know that z i y by definition. Therefore, z will be such that x i z i y iff x i z. The binary variable b z 2 will take value 1 in this case. This is indeed guaranteed by Constraint 8 enforcing b z 2 = 1 when ω i • (z -x) < 0, i.e. if x is strictly preferred to z. If instead z is preferred to x, then the value ω i • (z -x) is positive and Constraint 8 is vacuous; in this case, b z 2 will take value 0, as desired, because we are minimizing.

For all alternatives z ∈ Z 3 , the two previous conditions need to be satisfied in order for z to contribute to the score difference. Constraint 9 implements an and between these two conditions (b z 3 = 1 iff x i z and z i y). Finally, while we know that y cannot be strictly preferred to x (since x N i y), it might be the case that they are equally preferred. The binary variable b 0 represents whether x is strictly preferred to y; more precisely, Constraint 6 enforces that b 0 = 1 whenever ω i • (y -x) < 0.

2) case ¬(x N i y) (Figures 1b and1c): Recall that, in this case, PMR i (x, y, Ω i ) = max ω i ∈Ω i |{z ∈ X, y i z i x}|. Therefore, we aim to find a feasible ω i ∈ Ω i so that as many of the alternatives z ∈ X are such that y i z i x. Since we are maximizing, the optimal ω i ∈ Ω i will be such that y i x; thus, the case represented in Figure 1c reduces to the one depicted in Figure 1b. We now focus on the optimization of PMR i (x, y, Ω i ) for Figure 1b. Similarly to the first case, note that none of the alternatives z in U y ∪ L x verifies y i z i x for some ω i ∈ Ω i . Moreover, all alternatives z ∈ M y,x are such that y i z i x for all ω i ∈ Ω i . Therefore:

PMR i (x, y, Ω i ) = |M y,x | + max ω i ∈Ω i |{z ∈ Z 1 ∪ Z 2 ∪ Z 3 ∪ {x}, y i z i x}|
Thus, we need to compute max

ω i ∈Ω i |{z ∈ Z 1 ∪ Z 2 ∪ Z 3 ∪ {x}, y i z i x}|.
This can be performed by solving the following program (named MIP y,x hereafter):

(MIP y,x ): max b 0 + z∈Z1 b z 1 + z∈Z2 b z 2 + z∈Z3 b z 3 s.t. q j=1 ω i j = 1 ω i • (a -b) ≥ 0, ∀(a, b) ∈ P i ≥ ω i • (a -b) ≥ ε, ∀(a, b) ∈ P i > ω i • (y -x) + (1 -b 0 )C ≥ ε (10)
ω i • (z -x) + (1 -b z 1 )C ≥ 0, ∀z ∈ Z 1 ∪ Z 3 (11)
ω i • (y -z) + (1 -b z 2 )C ≥ ε, ∀z ∈ Z 2 ∪ Z 3 (12) b z 3 ≤ b z 1 , ∀z ∈ Z 3 (13) b z 3 ≤ b z 2 , ∀z ∈ Z 3 (14) ω i j ≥ 0, ∀j ∈ {1, . . . , q}; b 0 ∈ {0, 1}; b z 3 ∈ {0, 1}, ∀z ∈ Z 3 b z 1 ∈ {0, 1}, ∀z ∈ Z 1 ∪ Z 3 ; b z 2 ∈ {0, 1}, ∀z ∈ Z 2 ∪ Z 3 Proposition 2 If ¬(x N i y), then PMR i (x, y, Ω i ) = |M y,x | + OP T
, where OP T is the optimum of mixed-integer program MIP y,x .

The proof is similar to that of the previous condition, however since the objective is a maximization, the values of the binary variables b 0 , b z 1 (for z ∈ Z 1 ), b z 2 (for z ∈ Z 2 ) and b z 3 (for z ∈ Z 3 ) will be 1 unless forced to be 0. Constraints 10-14 formalize the required behaviour: the value of each binary variable, relative to a specifc z, will be set to 1 unless ω i is chosen in a way such that y i z i x.

Note that the MIP formulations might be too computationally demanding for problems involving a large number of alternatives (since there are one or more integer variables per alternative). For this reason, we will consider the linear programming relaxation of these programs, i.e., the linear programs obtained by replacing boolean variables b 0 , b z 1 , b z 2 , b z 3 by continuous variables belonging to the unit interval. The resulting optimization problems are solvable in polynomial time using linear programming; however the solution gives an upper bound on pairwise max regret values (instead of the exact value). The relaxed values for PMR are then aggregated giving a relaxed MMR value. Note that, since optimizing the relaxed problem gives an upper bound, the result can still be used in order to provide a robust recommendation with worst-case guarantees; the guarantee is less strong than if pairwise max regret values were computed exactly, but computation times are significantly improved as shown in Subsection 4.2.

Incremental Elicitation

Given the available preference information, the worst-case loss ensured by the minimax regret might be at unacceptable level. In order to approximate the Borda winner with the desired guarantee (expressed by the minimax regret value), we may ask additional preference information to the agents. By incorporating the responses to additional questions, we can indeed refine the uncertainty sets and therefore reduce this loss.

Elicitation Strategies

We adopt an incremental setting where preference queries are selected incrementally according to the current available information until the minimax regret is zero; at that point, we know that alternative x * Ω is a necessary Borda winner. We allow asking queries that may induce either weak or strict preference statements. In order to limit the cognitive effort of the agents, it is important to ask queries that are informative (roughly, a query is informative if it significantly reduces regrets whatever the answer); in particular, the computation of minimax regret can suggest queries that may be able to impose a significant reduction of regrets. One common technique, also known as the Current Solution Strategy (CSS), is to consider one of the current "best challenger" y * Ω of the approximate winner: y * Ω ∈ arg max y∈X PMR(x * Ω , y, Ω). New preference information involving the pair (x * Ω , y * Ω ) is indeed often useful to reduce the minimax regret efficiently, which is equal to PMR(x * Ω , y * Ω , Ω). We propose now two elicitation strategies of different complexity, that are aimed to reduce PMR(x * Ω , y * Ω , Ω).

Multi-Attribute-CSS0 (MA-CSS0). This strategy selects a pair (agent, query) such that the answer may reduce the agent's contribution to PMR(x * Ω , y * Ω , Ω). More precisely, an agent i is selected at random and the strategy proceeds as follows:

1) case x * Ω N i y * Ω : recall that, in this case, PMR i (x * Ω , y * Ω , Ω i ) = -|M x * Ω ,y * Ω | - min ω i ∈Ω i |{z ∈ Z 1 ∪ Z 2 ∪ Z 3 ∪ {y}, x * Ω i z i y * Ω }|.
We distinguish two cases:

-case Z 1 ∪ Z 2 ∪ Z 3 = ∅: if ¬(x * Ω N i y * Ω )
, then we ask the agent whether

x * Ω is strictly preferred to y * Ω . If, instead, x * Ω N i y * Ω , we know precisely the difference of scores between x * Ω and y * Ω for agent i, that is -|M x * Ω ,y * Ω | -1.
In this case, asking a query to agent i is useless (since his/her contribution to PMR(x * Ω , y * Ω , Ω) cannot be decreased) and so the strategy selects another agent at random.

-case ¬(Z 1 ∪ Z 2 ∪ Z 3 = ∅): an alternative z in Z 1 ∪ Z 2 ∪ Z 3 is selected at random.
For each z ∈ Z 1 ∪ Z 2 ∪ Z 3 , our current knowledge about the agent's preferences is not sufficient to conclude on whether x * Ω i z i y * Ω is satisfied or not. More precisely, if z ∈ Z 1 , then we know that x * Ω is strictly preferred to z by definition, but there exists ω i ∈ Ω i such that ¬(z i y * Ω ). Therefore, we ask the agent whether z is (weakly) preferred to y * Ω so as to obtain the missing information. Similarly, if z ∈ Z 2 , then we know that z is preferred to y * Ω , and so the agent is asked whether x * Ω is strictly preferred to z. Finally, if z ∈ Z 3 , then we ask one of the two previous questions, the choice between the two questions being randomly made.

2) case ¬(x * Ω N i y * Ω ): recall that, in this case, PMR i (x * Ω , y * Ω , Ω i ) = |M y * Ω ,x * Ω | + max ω i ∈Ω i |{z ∈ Z 1 ∪ Z 2 ∪ Z 3 ∪ {x}, y * Ω i z i x *
Ω }|. We distinguish three cases:

-case ¬(y * Ω N i x * Ω )
: in this case, x * Ω and y * Ω are incomparable for the system, and so we ask the agent to compare them directly.

case (y *

Ω N i x * Ω ) ∧ (Z 1 ∪ Z 2 ∪ Z 3 = ∅): if ¬(y * Ω N i x * Ω )
, then the agent is asked whether y * Ω is strictly preferred to x * Ω . If, instead, y * Ω N i x * Ω , then the difference of scores between x * Ω and y * Ω for this agent is equal to

|M y * Ω ,x * Ω | + 1.
In this case, asking a query to agent i is useless and another agent is selected at random.

-case (y * Ω N i x * Ω ) ∧ ¬(Z 1 ∪ Z 2 ∪ Z 3 = ∅): an alternative z in Z 1 ∪ Z 2 ∪ Z
3 is selected at random and we want to know whether y * Ω i z i x * Ω . More precisely, if z ∈ Z 1 , then we ask the agent whether z is (weakly) preferred to x * Ω . Instead, if z ∈ Z 2 , then we ask the agent if y * Ω is strictly preferred to z. Finally, if z ∈ Z 3 , then we ask one of the two previous questions.

Multi-Attribute-CSS1 (MA-CSS1). This strategy is based on the heuristics proposed by Lu and Boutilier [START_REF] Lu | Robust approximation and incremental elicitation in voting protocols[END_REF] but adapted to our multi-attribute setting. The aim is to choose the query with the highest potential of reducing PMR(x * , y * , Ω). More precisely, instead of choosing the agent and the alternative z ∈ Z 1 ∪ Z 2 ∪ Z 3 at random (as in MA-CSS0), strategy MA-CSS1 selects the pair (agent, query) that maximizes the minimax regret reduction in the most optimistic scenario; it therefore requires the computation of the resulting minimax regret for each pair (agent, query).

Numerical Tests

We performed a number of numerical experiments in order to evaluate the proposed elicitation procedures for determining the Borda winner in an incremental process. In these experiments, the attribute values for each alternative are randomly sampled in [0, 1] q . Starting from an empty set of preference statements, we repeatedly compute minimax regret and we ask a new question to one of the agent according to an elicitation strategy. We simulate answers to queries according to randomly generated vectors ω 1 , . . . , ω n (one vector per agent). Optimizations are performed using the Gurobi solver; the simulation enviroment is implemented in Java.

In the first experiment, we evaluate the impact of exploiting the fact that the domain is multi-attribute. We implemented the elicitation procedure proposed in [START_REF] Lu | Robust approximation and incremental elicitation in voting protocols[END_REF] (named CSS1 hereafter) where no assumption is made about the "structure" of the agents preferences, and compare it with our strategies MA-CSS0 and MA-CSS1. 4 In Figure 2a, we report the minimax regret, computed at each step of the incremental elicitation procedure. Regret values are expressed on a normalized scale, with 1 corresponding to the initial MMR (computed before acquiring any preference information). Note that a value of 0 for MMR implies identification of a Borda winner. We observe that the MMR reduces much more slowly with CSS1 than with its multi-attribute version MA-CSS1; after 20 queries, the MMR is still above 40% of the initial value with CSS1, while it is under 10% with MA-CSS1. Moreover, after 30 queries per agent on average, the MMR is still around 40% of the initial regret with CSS1 while MA-CSS1 has identified the Borda winner. Then, we observe (somewhat surprisingly) that the heuristics used by MA-CSS1 is less effective than MA-CSS0. Since MA-CSS1 is much more computational demanding than MA-CSS0, in the following experiments, we use MA-CSS0.

The second experiment evaluates the quality of the upper bound obtained when using the linear programming relaxation of the MMR optimization. Figure 2b shows the minimax regret, the upper bound obtained by linear programming relaxation and the real regret (the actual loss in terms of Borda score) at each iteration step of the elicitation procedure. We can see that the linear programming relaxation gives us a relatively tight upper bound on the minimax regret and its quality improves with the number of preference statements. Recall that the relaxed version is significantly faster than the exact version, as the former solves linear programming problems instead of mixed integer linear problems. For instance, when no preferences are given, the relaxed optimization takes about 1s on average while the exact method needs 30s to compute the value of initial minimax regret. The determination of the next query is also faster when using the relaxed optimization (2s againts 12s). Even if, by optimizing the relaxed problem, we are potentially ignoring some valuable information, the experiment shows that the elicitation performs well. The recommended choice is the alternative whose "relaxed" MMR is lowest; the real regret associated to this choice is small and quickly decreases to zero. Note that the fact that real regret is much smaller than minimax regret in practice has already been observed [START_REF] Wang | Incremental utility elicitation with the minimax regret decision criterion[END_REF].

The third experiment aims to evaluate the performance of MA-CSS0, using the relaxed optimization of regrets, when increasing the size of the problem (number of agents, number of alternatives and number of criteria). Figure 3 shows that, with 5 attributes, our incremental elicitation procedure determines a necessary Borda winner in about 30-35 queries asked to each agent; however, with 7 attributes, slightly more than 50 queries are needed. In all cases, the real regret is low even after a few queries.

Determination of the Social Ranking Induced by Borda Scores

There are many decision situations where knowing the top-k alternatives is the desirable output. When the preference profile is fully known, ranking alternatives with a scoring rule is straightforward. However, when preferences are incomplete, incremental elicitation methods need to be adapted to efficiently focus the elicitation effort on the determination of the top-k alternatives. We address here the problem of ranking as one of repeated choices, assuming that we want to incrementally rank alternatives from best to worst; we can generate preference queries until the minimax regret drops to 0, meaning that the Borda winner has been identified. Then, this alternative is put aside 5and the selection process is iterated on the remaining set of alternatives. The alternative selected in the second stage will be the second best alternative in the ranking induced by Borda scores and so forth.

Numerical Tests. We perform an experiment that evaluates the performance of our incremental assessment of ranking (when used with MA-CSS0) in comparison to approaches that are more systematic. We consider the following two elicitation procedures: strategy S1 determines the preference order of each agent by adapting a standard sorting algorithm (it requires O(m log 2 (m)) comparison queries per agent); the ranking is then obtained by straightforward computation of the Borda scores. Instead, strategy S2 iteratively applies a regret-based incremental elicitation procedure for the determination of the best alternative in terms of a linear utility model for a single agent. The procedure is repeated in order to find the second item, the third, and so on; this is done for all agents and finally Borda scores are computed. In Table 1, we report the average number of comparison queries per agent required to identify the top-10 alternatives, varying n the number of agents, m the number of alternatives and q the number of criteria. Our incremental ranking procedure based on Borda scores is referred to as Incremental Ranking Elicitation (IRE); overall, IRE outperforms both S1 and S2. We now present some experimental results about our incremental ranking method (when used with MA-CSS0). Figure 4 shows the average number of queries needed to determine the top-k alternatives in domains with 20 agents and 5 criteria. We observe that the marginal amount of queries needed to determine the next best alternative decreases as the rank of the alternatives increases. Actually, most of the elicitation "cost" in terms of queries occurs when determining the top alternative.

Conclusions

This paper dealt with social choice in a context where preferences are dictated by a latent (linear) utility function. We provided algorithms for the computation of an approximate winner and elicitation strategies based on minimax regret, extending previous work [START_REF] Lu | Robust approximation and incremental elicitation in voting protocols[END_REF] to multi-attribute domains. We also provided an iterative procedure for top-k ranking and compared our results with full elicitation procedures. Possible directions for future research include: dealing with other voting rules in multi-attribute domains, considering different kinds of queries, and addressing combinatorial domains.

  e. we want to show that the objective function counts the cardinality of {z ∈ Z 1 ∪ Z 2 ∪ Z 3 ∪ {y}, x i z i y}. In this program, we use a set of binary variables b z 1 , b z 2 and b z 3 to represent the condition x i z i y for alternatives z in Z 1 , Z 2 and Z 3 respectively. Binary variable b 0 represents whether x is strictly preferred to y (otherwise the contribution to PMR is null). The objective function sums up over all variables b 0 , b z 1 , b z 2 and b z 3

Fig. 2 :

 2 Fig. 2: Evaluation of the elicitation strategies; regret reduction is plotted as a function of the average number of queries per agent (30 alternatives, 5 criteria and 10 agents; results averaged over 30 runs). In (a) we plot the reduction of minimax regret obtained by different elicitation strategies; in (b) we compare the upper bound of MMR obtained with the relaxed optimization, the exact computation of MMR and the real regret.

(a) 10

 10 agents, 50 alt. and 5 attributes. (b) 50 agents, 50 alt. and 5 attributes. (c) 10 agents, 100 alt. and 5 attributes. (d) 10 agents, 50 alt. and 7 attributes.

Fig. 3 :

 3 Fig. 3: Performance of MA-CSS0 with the relaxed version of minimax regret (30 runs).

Fig. 4 :

 4 Fig. 4: Performance of top-k elicitation with MA-CSS0 (30 runs).

Table 1 :

 1 Average number of queries per agent for determining the top-10 (30 runs).

	n	m	q	IRE	S1	S2
	10	30	5	43.3	147.2	58.7
	10	50	5	43.7	282.2	67.4
	100	30	5	51.1	147.2	87.2
	10	30	10	93.3	147.2	178.2

The asymmetric part £ N i of N i is defined as x £ N i y iff (x N i y) ∧ ¬(y N i x).

Note that CSS1 and MA-CSS1 adopt the same heuristics for choosing the pair (agent, query); the difference is that MA-CSS1 makes use of the multi-attribute structure (using linear programming) for identifying the sets Z1, Z2, etc., and computing regrets, while CSS1 does not.

It may still be associated with a binary variable b z in the optimization problems for computing regrets (as it can impact the Borda score of other alternatives).

Acknowledgements

This work is supported by the ANR project 14-CE24-0007-01-Cocorico-CoDec.