Zaiani Mohamed
email: zaianimo@gmail.com

Djafer Djelloul

Chouireb Fatima

Irbah Abdanour

Hamidia Mahfoud

New Method for Clear Day Selection Based on Normalized Least 1 Mean Square Algorithm 2

Keywords: clearness index, NLMS, adaptive algorithm, solar radiation 26

A new method is proposed to select clear days from data sets of solar irradiation recorded with ground-13 based instruments. The knowledge of clear days for a given site is of prime importance both for the study of 14 turbidity and for the validation of empirical models of Global Solar Radiation (GSR). Our innovative method is 15 based on the Normalized Least Mean Square (NLMS) algorithm that estimates noise according to a GSR model. The 16 developed method named Clear Day Selection Method (CDSM) is compared to the well-known clearness index 17 criteria (kt) taking data collected at Tamanrasset in Algeria during the period 2005-2009. The root mean square error 18 (rmse), the mean absolute percentage error (mape) and the dependence of model error (mbe) are considered for the 19 comparison. A different number of clear days is found with both methods, with additionally a kt dependency for the 20 clearness index criteria. The average values of rmse, mape and mbe between the daily average of the measured GSR 21 and its estimate using a model are better in case of CDSM for the period 2005-2009. Indeed, we found 25.28 W/m 2 , 22 4.61 % and 2.09 W/m 2 respectively for CDSM and 42.48 W/m 2 , 7.63 % and -5.91 W/m 2 for the clearness index 23 method with kt = 0.7. We also found that GSR of clear days is well correlated with the model in case of CDSM, 24 which gives good confidence in our results. 25

1-Introduction

27

The Global Solar Radiation (GSR) is the total amount of solar radiation received by the Earth surface and 28 corresponds to the contribution of direct, diffuse and reflected solar radiation. Direct solar radiation is the 29 propagation of the beam directly through the atmosphere to the surface of the Earth, while diffuse solar radiation is 30 scattered in the atmosphere. Solar radiation is affected during its propagation through the atmosphere by atoms and 31 molecules (ozone, water vapor, carbon dioxide ...) as well as by liquid and solid aerosols dispersed or grouped in 32 clouds [START_REF] Kaskaoutis | Comparison of the Angstrom parameters retrieval in different spectral 236 ranges with the use of different techniques[END_REF]. Solar radiation measurements on the ground then depend on the site location. The 33 location must indeed be taken into account when we are interested in the quality and amount of solar radiation. GSR 34 is one of the most important parameters in solar energy designs and/or applications [START_REF] Badescu | 214 Accuracy analysis for fifty-four clear-sky solar radiation models using routine hourly global irradiance 215 measurements in Romania[END_REF]Reno et al. 35 2012). Analyzing solar radiation properties in a given location requires long-term data and both use of empirical, 36 semi-empirical or physical models and specific techniques such as neural networks [START_REF] Senkal | Solar radiation and precipitable water modeling for Turkey using artificial neural networks[END_REF][START_REF] Mohandes | Modeling global solar radiation using Particle Swarm Optimization (PSO)[END_REF].

37

Many studies were carried out to estimate and/or predict solar radiation using available meteorological (air 38 temperature, relative humidity ...) and geographical (sunshine hours, latitude ...) parameters [START_REF] Wong | Solar radiation model[END_REF] 39 [START_REF] Victor | Empirical models for estimating daily global solar radiation in 276 Yucatán Peninsula, Mexico[END_REF][START_REF] Gueymard | Clear-sky irradiance predictions for solar resource mapping and large-scale applications: 226 Improved validation methodology and detailed performance analysis of 18 broadband radiative models[END_REF]. These models are needed to obtain the correct designs and outputs of solar

43

2012; [START_REF] Mellit | Methodology for predicting sequences of mean 247 monthly clearness index and daily solar radiation data in remote areas: Application for sizing a stand-alone 248 PV system[END_REF]. Authors then sorted day types using the parameter according to their own criteria. The 44 sky is, for some, clear when its value is between 0.65 and 1, partly cloudy when and cloudy if 45 [START_REF] Gueymard | Clear-sky irradiance predictions for solar resource mapping and large-scale applications: 226 Improved validation methodology and detailed performance analysis of 18 broadband radiative models[END_REF][START_REF] Mdc | Effects of Sky Conditions Measured by the Clearness 211 Index on the Estimation of Solar Radiation Using a Digital Elevation Model[END_REF] 109

The NLMS algorithm is implemented according to the following steps:

110

The output signal of the adaptive filter is calculated by: 111

(5) 112

The estimated filter error signal at step (n) is computed as the difference between the desired signal and Each daily GSR is fitted with a clear sky GSR model.

129

The measured GSR is subjected to a parameterized FIR filtering with coefficients (see previous section):

130 7 a sample of the modeled GSR is obtained.

131

The estimated filter error between samples of modelled GSR and clear sky GSR model is calculated.

132

The obtained estimated filter error is used to calculate the next step that is used to readjust FIR filter the method allows having a modelled GSR more or less disturbed according to the data considered. It will be close 141 to the GSR model when the estimated filter error is small i.e. the case of clear days. We will consider in our study 142 that clear days correspond to the estimated filter error less than 20 / ; otherwise they are considered as turbid. Irbah [START_REF] Djafer | Estimation of atmospheric turbidity over Ghardaia city[END_REF]. The main difference is that the three components of solar radiation are recorded every 151 minute at Tamanrasset together with temperature, humidity and pressure. Instruments that measure direct, global and 152 diffuse solar radiation components are EKO type instruments (http://eko-eu.com/) (see Figure 6). They are cleaned 153 two to three times a week depending on weather conditions and calibrated every three years. Data were calibrated 154 with the TSI of 1367 / since it was the current value at this period (2005 -2009). A correction factor is applied 155 to the data since the TSI of 1361 / is now adopted. This factor is the ratio between current and previous TSI.

4-2. Results and discussion

157

We used the five years of GSR measurements (see section 4.1) and determined clear days present in the data set with 158 the clearness index, wavelet based method [START_REF] Djafer | Identification of clear days from solar irradiance observations using a new 224 method based on the wavelet transform[END_REF] (see right plot of Figure 7). Curves have similar shapes but the number range for the clearness method is large 168 relative to the CDSM one. There is quasi no clear days found for months between May and August with 169 leading to suppose that its value needs to be adjusted during processing as reported in section 1. We note that the 170 number of clear days at Tamanrasset is lower during the months of May and September-October compared to the 171 others.

172

Finally, we compared GSR of clear days obtained with both and CDSM to those estimated by the model 173 described in [START_REF] Zaiani | New Approach to Establish a Clear Sky Global Solar Irradiance Model[END_REF] 198 estimated with the model. We found that the GSR of clear days selected with CDSM are better correlated with the 199 model than those obtained with the clearness index method. The correlation coefficient is 0.99 for CDSM and 0.95 200 using criteria. We can emphasize that our method was developed using daily measured GSR but may also be 201 adapted to detect clear and turbid short periods in measurements. These short periods are very useful for studying 202 the environment and regional frequency of clouds. In addition, knowledge of the occurrence of clear days on a site 203 also has many other interests. This is particularly the case before any photovoltaic or thermal installation for which 204 solar radiometric measurements over a longer or shorter period are necessary. Our work is then very useful to give 205 the relevant information on the number of clear days for a given site and consequently to predict the energy that 206 these facilities will produce in this region.

207

  40 power plants in case of clear sky conditions. Selecting clear days from recorded datasets is the first step in modelling 41 solar radiation under these conditions. The clearness index method, based essentially on the calculation of a 42 parameter related to measured solar radiation, is widely used for this purpose (Alves et al. 2013; Khem et al.

(

  vector with delayed values in time. w(n) = [w0(n) w1(n) w2(n) … wL-1 (n)] T is a vector with 93 components containing the tap weight coefficients of the adaptive FIR (Finite Impulse Response) filter at time , 94 is the estimated filter error at and the subscript stands for transpose operator. The parameter is known as 95 the step size parameter and is a small positive constant. This parameter controls the influence of the updating factor.96Selection of a suitable value of is imperative for the performance of the LMS algorithm. The time taken by the 97 adaptive filter to converge into the optimal solution will be too long if its value is too small. The adaptive filter 98 becomes unstable if is too large and its output diverges(Sharma and Mehra 2016; Dixit and Nagaria 2017). The 99 stability condition of the LMS algorithm is / , where is is the largest eigenvalue of the 100 autocorrelation matrix of the input signal . The main disadvantage of LMS algorithm is the fixed step size 101 parameter for every iteration. This requires knowledge of the input signal statistics prior to starting the adaptive 102 filtering operation. The NLMS algorithm is an extension of the LMS one, which by passes this issue by calculating 103 the maximum step size value. This step size is proportional to the inverse of the total expected energy of 104 instantaneous coefficients of the input vector . The recursion formula for NLMS algorithm is given by 105 step size of NLMS and is a regularization constant used to avoid division 108 by zero.

Figure 2 .(Figure 3 .

 23 Figure 1. Adaptive filtering

Figure 4 .

 4 Figure 4. CDSM behavior in case of a clear (left) and a turbid day (right).

Figure 3

 3 Figure 3 plots an example of daily measured GSR (dashed line) superposed to the clear sky GSR model (full line)

Figure 5 .

 5 Figure 5. Estimated filter error of the GSR estimate for a clear (left) and a turbid day (right).

156Figure 6 .

 6 Figure 6. Radiometric station for measuring global, direct and diffuse solar radiation: (1) Pyranometer for measuring the global solar irradiance. (2) Pyranometer for measuring the diffuse. (3) Pyrheliometer for measuring the direct solar irradiance, (4) Shaded pyranometer. (5) The 2-axis solar tracker.

  163 wavelet method seems to underestimates the yearly number of clear days due to excessive constraints on GSR 164 disturbances when setting the selection threshold. The three methods show the same trend of the yearly number of 165 clear days with a maximum around 2008. If we look at the monthly values of clear days computed over the period 166 2005-2009, we observe a difference between CDSM results and those obtained with the clearness index with 167

Normalized Least Mean Square Method for Clear Days Selection 82

	78		This condition is only intended to prevent the presence of haze early in the morning or late in the afternoon.
	79		This could lead to considering a clear day as not being one.
	80		Calculation of the extraterrestrial solar radiation	for the same day.
	81		Calculation of the instantaneous clearness index between sunrise and sunset using Equation 1.
	83	3-We present in this section the Normalized Least Mean Square (NLMS) algorithm and then how we use it to select
	84	clear days from data sets.
	85	3-1. The NLMS algorithm
	86	The Least Mean Square (LMS) algorithm was first developed by Widrow and Hoff in 1959 for speech recognition
	87	applications. It is today one of the most widely used algorithms in adaptive filtering mainly due to its efficiency and
	88	computational simplicity. LMS algorithms are a class of adaptive filters used to generate a desired filter that
	89	produces least mean squares of the error signal i.e. difference between desired and real signal. The algorithm starts
	67	by assuming small weights (zero in most cases) at each step and finding the gradient of the estimated error. Weights
	68		on a horizontal surface and the extraterrestrial one :
	69				(1)
	70	where	in /	is given by:
	71				(2)
	72	is the Total Solar Irradiance (TSI) equal to 1361 /	(Myhre et al. 2013) and N the day number in the year
	73	(N=1 is the first day in the year and N=365 the last one). , and are respectively the latitude of the location, the
	74	solar declination angle and the hour angle at sunrise in degrees.
	75	An algorithm based on the instantaneous clearness index was first developed for our work to automatically select
	76	days from a huge dataset. The main steps of the algorithm are:
			Selection of	records of a given day where the Sun elevation is higher than 10°.
					4

. For other authors, a clear sky is when

(Bendt et al.

66 models. The clearness index is defined over time as the ratio between the terrestrial global solar radiation

Table 1 .

 1 and CDSM. Results are given in Table 1 and plotted Number of clear days per year selected with different methods Number of clear days selected with the different methods: number per year (left) and per month (right). We observe in the left plot of Figure 7 that the number of clear days per year obtained with CDSM is close to what is 162 found with . Lower values overestimate the number of clear days while higher ones underestimate it. The

	159
	160	in Figure 7 where error bars are one standard deviation.	values widely used in the literature to select clear days
	161	were considered for the comparison, that is		.
		Years	2005	2006	2007	2008	2009
		Wavelet method	59	30	65	98	24
		CDSM	136	133	173	173	120
		=0.5	303	316	319	322	305
		=0.6	244	254	279	274	254
		=0.7	114	133	158	170	139
		=0.8	2	7	6	14	7

  . This parametric model used Artificial Neural Network to estimate GSR of a given 174 clear day. We used several parameters to quantify the comparison among which are the root mean square error 175 (rmse), the normalized root mean square error (nrmse), the mean absolute percentage error (mape), the dependence 176 of model error (mbe) and the normalized dependence of model error (nmbe). Comparison results are given in Table 0.94, an rmse of 42.58 / , an mbe of 1.97 / and a mape of 7.55 % for the clearness index method. Figure 8 clear days selected by both methods to model daily GSR. The analysis of the difference between 194 GSR of the clear days selected with CDSM and calculated for these days with the model shows a very good 195 agreement. We found that yearly values vary between (i) 4.20 and 5.33 % for mape, (ii) 0.95 and 0.99 for , (iii) 196 24.63 and 26.75 / for rmse and (iv) 2.00 and 2.25 / for mbe. Finally, we performed a comparison of daily 197 average GSR of clear days obtained with both CDSM and the clearness index method with and those

	180 189	5-Conclusion
	181 190	plots the correlation between daily average measured GSR of clear days selected with CDSM (left plot) and with the A new method to select clear days in data sets of solar radiation is presented in this work. This method we denoted
	182 191	clearness index method ( CDSM, is based on NLMS algorithm. We first compared CDSM to the clearness index method taking the most used ) (right plot) versus daily average calculated GSR. We note that GSR of clear days
	183 192	selected with CDSM are very well correlated with the model compared to what we obtain with the clearness index value and found that our method gives a higher number of clear days when using the same data set. We
	184 193	method. The correlation factor is 0.99 for CDSM and 0.95 using took a data set of 5 years of solar radiation measurements collected at the Tamanrasset ONM. We then validated criteria. We may conclude when looking at this
	185	plot that we can be confident in the results obtained from CDSM. CDSM using the
	186		Table 2. Annual average errors between measured and calculated GSR
		Method	Errors	2005	2006	2007	2008	2009	Average
			rmse ( / )	24.63	24.72	26.75	25.51	24.79	25.28
			nrmse (%)	3.63	3.64	4.43	4.19	3.54	3.88
			mape (%)	4.26	4.27	5.33	5.01	4.20	4.16
		CDSM	mbe ( / )	2.01	2.00	2.25	2.15	2.05	2.09
			nmbe (%)	0.27	0.27	0.59	0.55	0.27	0.39
				0.99	0.99	0.95	0.95	0.99	0.97
			rmse ( / )	42.00	41.45	44.11	37.47	47.84	42.58
			nrmse (%)	6.92	6.60	7.07	5.89	7.38	6.77
			mape (%)	7.56	7.29	7.82	6.68	8.40	7.55
		kt	mbe ( / )	1.24	2.97	2.89	2.54	-0.2	1.97
			nmbe (%)	0.11	0.43	0.40	0.35	0.03	0.27
				0.94	0.94	0.94	0.95	0.93	0.94
	187	Figure 8. Correlation between daily average of calculated and measured GSR obtained with CDSM (left) and with
	188		the clearness index with		.

We note that the model fits better the measured GSR of clear days determined with CDSM. Indeed, we have a 178 mean of 0.97, an rmse of 25.28 / , an mbe of 2.09 / and a mape of 4.16 % while we have a mean of


Hui Zhou
email: hui.zhou@cranfield.ac.uk

Renaud Jourdain

Vincent Serantoni

Jose Endrino Armenteros

Paul Shore

Creation of a control system for plasma delivery to increase determinism and robustness while processing using an ICP torch

Keywords: Inductively Coupled Plasma, RF generator, RF network

The Cranfield University Precision Engineering Institute team has created a unique plasma figuring capability to correct large optical surfaces at atmospheric pressure. In the context of ever increasing dimensions of optical components, there is a need for improving the robustness and securing the performance of our Plasma Delivery System (PDS). The current PDS is based on an inductive output L type RF circuit, Inductively Coupled Plasma (ICP) torch and computer numerically controlled (CNC) motion system. The combination of optical component surface areas and the nature of the sub-aperture plasma tool lead to significant processing duration. This atmospheric pressure processing environment is more cost-effective than vacuum chamber based ones which are often used by competitors. However it requires deep awareness and fine understanding of technologies used. Based on the knowledge acquired for the past eight years, we have created a smart control system for our unique PDS that equips a machine called Helios1200. This novel control system aims at securing the process determinism and assisting the machine operator by tuning some key electrical components of the RF network and monitoring some processing parameters. Furthermore, specific assistance is provided during the different phases of the plasma processing. This paper describes the main design aspects.

Plasma Figuring Technology

This work supports the development of the Plasma Figuring (PF) technology [1]. PF provides a unique rapid surface figuring capability for large optics. PF benefits from bespoke plasma tool and tool path algorithm. PF has been shown suitable to process silicon based materials.

At Cranfield University, there are two plasma figuring machines. They are called RAP300 [2] and Helios1200 [3] (Fig. 1). These machines combine plasma technology operating at atmospheric pressure and computer numerically controlled (CNC) motion systems. However the radio frequency (RF) plasma systems are different. RAP300 is equipped with a matching network RF network unlike Helios1200 that is equipped with a fixed match RF network [1]. In each machine, a RF inductively coupled plasma (ICP) torch is used to atomize the reactive gas and create free radicals [1]. The combined torch, RF network, and signal generator will be named Plasma Delivery System (PDS) in this paper. The electrical designs of these two PDS are based on inductive output L type RF circuit. In Helios1200, a fixed match electrical design was chosen because this design enables to reduce the weight of the plasma torch assembly. Thus the axis of the CNC machine tool that drives the torch has better dynamic performances and consequently higher capability to correct complex surfaces. Here below the torch assembly and the electrical circuit (RF network) are displayed [START_REF] Serantoni | Internal document[END_REF].

Research motivation

The aim of this project is to secure hundreds of processing hours for PF of metre scale surfaces. This aim will be reached by designing a novel control system to monitor and assist the PDS of Helios1200. Hereafter are detailed features that the control system does ensure.

Expected capability of the control system

The capability of the novel system is to control the impedances of the load of the PDS and monitor the reflected power of the RF signal generator.

The first capability will be secured through the modification of the torch assembly through the motorization of capacitors. Thus a certain degree of automation will be implemented in the PDS. The second capability will be secured by a micro controller, micro actuators, and sensors. This capability will enable to gather on-flight process information for diagnostic purposes.

Indeed, authors have identified the important features that are needed for the entire range of operations. Thus the novel features of the control system address plasma ignition, regular plasma delivery, and critical circumstances. These three phases are experienced during regular operations. Details and benefits of each phase are provided hereafter.

Plasma ignition phase is characterised by moderate RF signal power ~300W and tuning of the capacitors. Regular plasma delivery phase ~1.2kW is characterised by monitoring of various parameters such as reflected power, coolant temperature and gas temperature. Critical circumstance is a phase where un-expected events may occur. Shutting down of the PDS will be executed to preserve its integrity.

Novel approach for RF circuit design

Way to overcome the need for matching network

Matching network enables to tune the impedance of the loads. This load is typically made by coil, load capacitor, tune capacitor, and transmission line. The matching network maintains the plasma in stable condition. Thus temperature increase of the electrical components, environmental perturbations and process parameter variations cannot disturb critically the plasma created by the RF network. From a technical viewpoint, capacitors are motorized to tune the impedance of the load. However matching network systems are expensive, heavy and have moderate capability to quickly tune the load. These are the reasons for utilizing another load tuning system.

The PDS of Helios1200 does not use a matching network as described above. Helios1200 PDS was created based on fixed match RF circuit. Basically, fixed match are designed to fit tightly the type of load driven so there is only a unique frequency. Also, the frequency signal provided by free running RF generator [6] is swept across a well-defined range to reduce the reflected power (RP). This RP is known to damage critically the PDS [6].

The two RF electrical designs have got pros and cons. Fixed match PDS is faster to reduce the reflective and offer gain from weight and cost viewpoint. However, only matching network can reduce the RP down to zero when environmental conditions change strongly. Then our design combines the best features of these two RF network designs.

Proposed fixed match automation and control

Through the means of actuators, sensors, and micro controller, the impedance of the load will be adjusted by tuning the values of the capacitors (tune and load). Those capacitance values are intended to be changed using stepper motors mounted at the end of cylindrical vacuum capacitors. In addition, the free running RF signal generator will be used to determine finely and rapidly the optimum output frequency. Figure 3 illustrates the motorization of the capacitors.

Result

Two technical aspects of the design work were completed: electrical and mechanical design (Fig. 4).

From an electrical viewpoint, the control system hardware is defined and secured. The control system will be programmed using an open-source language based on Arduino technology. That controller will manage inputs and outputs.

The mechanical design addressed capacitor motorization, shielding of the electrical components from electromagnetic fields, and securing the position of all sensors.

Conclusion

The design of the novel control system was completed. A pioneering approach is being explored to enhance the processing capability of plasma delivery systems used in CNC machine tools created for high-end optical fabrication. A highly reliable and deterministic plasma processing system is expected to satisfy the needs of ultra-precision applications. Next step will focus on the fabrication and testing of this control system.

Figure 1 .

 1 Figure 1.RAP300 (left) and Helios1200 (right)

Figure 2 .

 2 Figure 2. Torch assembly (left), inductive output L type RF circuit (right)

Figure 3 .

 3 Figure 3. Motorized fixed match RF network

Figure 4 .

 4 Figure 4. Electrical components (left), Mechanical components (right)


Nawal Benabbou
email: nawal.benabbou@lip6.fr

Patrice Perny
email: patrice.perny@lip6.fr

Incremental Approval Voting for Multi-agent Knapsack Problems

In this paper, we study approval voting for multi-agent knapsack problems under incomplete preference information. The agents consider the same set of feasible knapsacks, implicitly defined by a budget constraint, but they possibly diverge in the utilities they attach to items. Individual utilities being difficult to assess precisely and to compare, we collect approval statements on knapsacks from the agents with the aim of determining the optimal solution by approval voting. We first propose a search procedure based on mixed-integer programming to explore the space of utilities compatible with the known part of preferences in order to determine or approximate the set of possible approval winners. Then, we propose an incremental procedure combining preference elicitation and search in order to determine the set of approval winners without requiring the full elicitation of the agents' preferences.

Introduction

Collective decision making on a combinatorial domain appears in various contexts such as investments planning, resource allocation or group configuration. Due to strategic aspects often surrounding group decision-making and the possible divergences in individual values, developing formal methods and tools for modeling preferences and solving multi-agent combinatorial optimization problems is a critical issue. This has motivated a lot of work in the recent years, in the field of computational social choice [START_REF] Brandt | Handbook of Computational Social Choice[END_REF]. We focus here on the multi-agent knapsack problem which consists of determining, given a finite set of items, a subset of maximal utility under a budget constraint. This is a standard example of combinatorial problem with many potential applications such as project selection, portfolio management or committee election, see e.g. [Lu and Boutilier, 2011b[START_REF] Klamler | Committee selection under weight constraints[END_REF][START_REF] Elkind | Properties of multiwinner voting rules[END_REF][START_REF] Oren | Online (budgeted) social choice[END_REF], Skowron et al., 2015a] for examples of recent contributions.

In combinatorial optimization problems, the agents cannot be expected to provide extensive preference models. Compact representations are needed to handle individual and collective preferences. Usually, in knapsack problems, preference over subsets of items are represented by additive utility functions. More precisely, the utility of a subset of items for an agent is defined as the sum of the utilities of its elements. Individual utilities are difficult to assess, especially on a combinatorial domain. Although the elicitation task is simplified when utilities are decomposable, elicitation methods based on systematic pairwise comparisons are practically unfeasible due to the large amount of feasible subsets and their implicit definition. Hence we are interested in designing incremental elicitation procedures, in which preference queries are selected iteratively, to be as informative as possible at every step, so as to progressively reduce the set of admissible utility profiles until the set of optimal knapsacks can be determined. This approach has been successfully used in AI for additive utility elicitation on explicit sets [START_REF] Chajewska | Making rational decisions using adaptive utility elicitation[END_REF][START_REF] Wang | Incremental Utility Elicitation with the Minimax Regret Decision Criterion[END_REF][START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF], but also on combinatorial solution spaces [Gelain et al., 2010, Benabbou and[START_REF] Benabbou | Incremental Weight Elicitation for Multiobjective State Space Search[END_REF].

We remark that, even if numerical representations of individual preferences are accessible under the form of utility functions, they are generally constructed independently for each agent. Hence, it is unlikely that such representations allow the welfare of individuals to be compared. In this context, the definition of a social utility as the sum of individual utilities (utilitarism), for example, would be meaningless. Assuming that utilities of items are expressed on the same scale or that utilities are normalized would not be sufficient to overcome the problem, as shown by the following example:

Example 1. Consider a multi-agent knapsack problem involving 3 items and 2 agents with utilities: u 1 = u 1 1 x 1 + u 1 2 x 2 + u 1 3 x 3 and u 2 = u 2 1 x 1 + u 2 2 x 2 + u 2 3 x 3 to be maximized under the constraint x 1 + x 2 + x 3 ≤ 2, where x i ∈ {0, 1}, i = 1, 2, 3, are the decision variables and u i j represents the utility of item j for agent i. This problem could appear to elect a committee of size 2, given 3 candidates and 2 voters. Assume that individual preference orders over committees have been elicited, and are equal to {2, 3} 1 {1, 3} 1 {1, 2} and {1, 2} 2 {1, 3} 2 {2, 3} for agents 1 and 2 respectively. One possible numerical representation of these preferences (using the same utility scale for the two agents) is given by:

(u 1 1 , u 1 2 , u 1 3 ) = (1, 2, 4) and (u 2 1 , u 2 2 , u 2
3 ) = (4, 2, 1) which leads to the following utilities for solutions of size 2:

{1, 2} {2, 3} {1, 3} u 1 3 6 5 u 2 6 3 5
Note that these individual values are consistent with preference orders 1 and 2 . Now, if we are utilitarian, we could be tempted to deduce that {1, 3} is the optimal knapsack because it maximizes the total utility (5 + 5 = 10). However, such a conclusion would be meaningless, it is only due to the particular numerical representation chosen for individual utilities. Let us change the initial numerical scale by replacing numbers (1, 2, 4) by (0, 3, 4). In this case we obtain two new utility functions characterized by (u 1 1 , u 1 2 , u 1 3 ) = (0, 3, 4) and (u 2 1 , u 2 2 , u 2 3 ) = (4, 3, 0) which leads to the following utilities for solutions of size 2:

{1, 2} {2, 3} {1, 3} u 1 3 7 4 u 2 7 3 4
Note that these new individual values are still consistent with preference orders 1 and 2 . Yet, with the same utilitarian principle, we should admit now that {1, 3} is the least preferred knapsack. Therefore, choosing the solution maximizing the sum of individual utilities would not be a good procedure. It would merely be a consequence of arbitrary choices of numerical representations of preferences rather than a robust conclusion derived from the observed preference profile. Note that the problem persists if we normalize u 1 and u 2 utilities to obtain value 1 for set {1, 2, 3}. Other examples could be found for other aggregators than the sum (e.g. the minimum for an egalitarian aggregation).

In order to be able to compare the solutions of a knapsack problem when individual utility scales are not commensurate and/or not rich enough to allow the construction of a social utility, it seems natural to resort to a voting rule. The main advantage of a voting rule is indeed to perform an ordinal aggregation procedure. There is no need to know how the welfare of individuals should be compared, we only need to elicit individual preference orders. Preference elicitation can be performed incrementally so as to determine the winner with a reduced amount of preference queries. Various incremental elicitation procedures have been proposed and studied in the context of singlewinner elections with incomplete preferences [START_REF] Kalech | Practical voting rules with partial information[END_REF], Lu and Boutilier, 2011a[START_REF] Dery | Reaching a joint decision with minimal elicitation of voter preferences[END_REF]. In this setting, several contributions study the determination of possible and necessary winners from a partial preference profile, e.g., [START_REF] Konczak | Voting procedures with incomplete preferences[END_REF][START_REF] Xia | Determining possible and necessary winners given partial orders[END_REF][START_REF] Lang | Winner determination in voting trees with incomplete preferences and weighted votes[END_REF][START_REF] Ding | Voting with partial information: what questions to ask[END_REF], when the set of candidates is defined explicitly.

In knapsack problems however, solutions are numerous and defined implicitly, which is an additional challenge for the winner determination. This explains the current interest for incremental voting procedures on combinatorial domains and the purpose of this paper. Our aim here is to propose an incremental voting rule in which individual preferences are progressively revealed until a collective decision can be made, and to apply this procedure on the multi-agent knapsack problem, taking advantage of the fact that individual preferences are representable by additive utilities.

It is important to note that implementing a voting rule is not in contradiction with the representation of individual values by utilities. Individual utility functions are indeed seen as convenient representations of individual preference orders, and their use will significantly contribute to relieve the preference elicitation burden. In the standard knapsack problem, due to the linearity of preferences, the set of all preference orders compatible with a given partial order can be characterized by a convex polyhedron in the utility space. This makes it possible to resort to mathematical programming to explore all possible completions of any partially known preference profile, but also to look for possible winners, and to develop an efficient incremental elicitation procedure for winner determination, as it will be seen later in the paper.

Implementing a voting rule for the knapsack problem with a partially specified preference profile could be related to multi-winner voting rules studied in the field of computational social choice. Most approaches recently proposed for multi-winner elections assume that individual preferences over items are sufficient to explain preference over subsets because they derive satisfaction from their most preferred candidate (see e.g., [START_REF] Chamberlin | Representative deliberations and representative decisions: Proportional representation and the Borda rule[END_REF][START_REF] Monroe | Fully proportional representation[END_REF][START_REF] Potthoff | Proportional representation broadening the options[END_REF], Procaccia et al., 2008[START_REF] Meir | Complexity of strategic behavior in multi-winner elections[END_REF], Lu and Boutilier, 2011b[START_REF] Betzler | On the computation of fully proportional representation[END_REF][START_REF] Elkind | Properties of multiwinner voting rules[END_REF], Skowron et al., 2015b], and see [START_REF] Lu | Multi-winner social choice with incomplete preferences[END_REF] for incremental elicitation of voter preferences). This assumption is well-suited to the election of representatives. However, for any agent, it may happen that the selection of the most preferred candidate is not sufficient to counterbalance the presence of multiple least preferred candidates in the elected committee. This limitation also applies to the selection of items in the multi-agent knapsack problem.

In this paper, we focus on approval voting because this is a simple rule that can be decisive even if only a part of the preference profile is known. In approval voting, we only need to learn, for every agent, which are the approved or disapproved subsets, so as to elect a solution receiving the maximal support. We therefore investigate incremental procedures for approval voting and their application to the knapsack problem. This work differs from multi-winner approval voting [START_REF] Kilgour | Approval balloting for multi-winner elections[END_REF] which only collects approval statements over items instead of feasible subsets of items.

The paper is organized as follows: after introducing our framework for preference elicitation in multi-agent knapsack problems in Section 2, we study the determination of possible winners for approval voting in Section 3. Then, an incremental voting procedure to determine the set of winners are proposed in Section 4 and experimented in Section 5.

The General framework

We consider a collective decision problem where a set of agents N = {1, . . . , n} has to jointly select a set of items (e.g., candidates, projects, objects) in a set P = {1, . . . , p}. Any subset of items can be represented by a solution vector x = (x 1 , . . . , x p ) ∈ {0, 1} p where x j = 1 if item j is in the subset and x j = 0 otherwise. Some linear constraints on variables x j , j ∈ P , are imposed to define the admissible solution vectors. For instance, one may want to impose cardinality constraints to control the size of the set and/or to ensure gender parity in the elected committee; there may also exist budget constraints (e.g., when the decision is subject to a maximum total cost) or capacity constraints as in knapsack problems, making some subsets of items unfeasible. For the simplicity of the presentation, we will only consider the standard knapsack constraint of the form j∈P w j x j ≤ W where w j is the (positive) weight of item j and W is a positive value representing the maximum total weight; the set of feasible solutions will be denoted by X in the sequel. Our purpose and the algorithms proposed in the paper also apply when additional (linear) feasibility constraints are considered.

We assume that the preference of agent i can be represented by a function u i : {0, 1} p → R measuring the overall utility of any solution. Hence, given two solutions x, y representing two subsets of items, x is at least as good as y for agent i ∈ N whenever u i (x) ≥ u i (y). Here u i (x) = j∈P u i j x j , where u i j ∈ R represents the utility of item j for agent i. The profile (u 1 , . . . , u n ) of utility functions will be denoted by u. Note also that u i , as a numerical representation of a preference order, is generally not unique and any transform preserving inequalities of type u i (x) ≥ u i (y) for all solutions x, y could be considered as well.

Nevertheless, numerical representations of individual preferences by utility functions u i , i ∈ N , can be used in approval voting. Recall that approval voting is a single-winner voting method which allows each agent to approve of (vote for) as many candidates as she wishes. The candidate with the most approval votes is the winner of the election [START_REF] Brams | Approval voting[END_REF]. Under the assumption that individual preferences are represented by utility functions u i , i ∈ N , a solution x is approved by agent i if and only if u i (x) ≥ δ i where δ i ∈ R is an approval (or utility) threshold that separates approved and non-approved solutions. The profile of thresholds (δ 1 , . . . , δ n ) will be denoted by δ in the sequel. The pair (u, δ) characterizes approved and non-approved solutions for all agents and enables the computation of approval scores for any feasible solution x. This score is given by f (x, u, δ) = |{i ∈ N, u i (x) ≥ δ i }|, and the winner of the election is a feasible solution maximizing this score; various tie-breaking rules can be considered. The approval multi-agent knapsack problem can be defined as follows:

APPROVAL MULTI-AGENT KNAPSACK PROBLEM (AMKP) Input: Finite set P of items, for each j ∈ P , a weight w j and a positive integer W ; a finite set N of agents, for each i ∈ N , an approval threshold δ i , for each j ∈ P , a utility value u i j and a positive integer K. Question: Is there a subset X ⊆ P such that j∈X w j ≤ W and |{i ∈ N, j∈X u i j ≥ δ i }| ≥ K?

This problem is NP-complete, due to a simple reduction from the knapsack decision problem. Testing the existence of an admissible knapsack having a utility greater or equal to a given value K is indeed equivalent to solving an instance of the AMKP problem involving a single agent with the same utilities over items, an approval threshold equal to K and with K = 1. Therefore, finding the knapsack maximizing the approval score is NP-hard.

Moreover, well-known pseudo-polynomial solution methods for the knapsack problem based on dynamic programming are no longer valid for the approval winner determination problem, as shown by the following example:

Example 2. Consider a collective decision problem where 2 agents have to choose 2 representatives from a pool of 3 candidates, i.e. N = {1, 2} and P = {1, 2, 3}. Assume that utilities and approval thresholds are the following:

u 1 1 u 1 2 u 1 3 δ 1 u 2 1 u 2 2 u 2 3 δ 2 0.5 0.3 0.2 0.5 0.1 0.5 0.3 0.7 In this case, we have f ({1}, u, δ) = 1 > 0 = f ({2}, u, δ) but f ({1, 3}, u, δ) = 1 < 2 = f ({2, 3}, u, δ).
We observe a preference reversal because {1} is preferred to {2} whereas {2, 3} is preferred to {1, 3}. Thus, preferences induced by the approval score are not additive with respect to union with disjoint items. This precludes to construct the optimal knapsack from optimal subsets of items.

Nevertheless, the winner can be obtained by solving the following mixed integer program:

max i∈N a i s.t. j∈P u i j x j -δ i ≥ M (a i -1), ∀i ∈ N j∈P w j x j ≤ W x j ∈ {0, 1}, a i ∈ {0, 1}, ∀i ∈ N, ∀j ∈ P
The first constraint allows the introduction of a boolean variable a i which is equal to 1 if and only if agent i approves solution x. The second constraint is the knapsack constraint. Finally, M is a constant greater than max{δ i -u i (x), i ∈ N }.

However, in practice, the full elicitation of individual utilities and approval thresholds is too expensive. Usually, we can observe simple preference statements of type "I prefer solution x to solution y", and in the case of approval voting, "I approve solution x", or "I don't approve solution y". These preference statements enable to restrict the sets of possible utility functions but generally do not allow to derive a precise utility function for each agent (see Example 1). Instead, uncertainty sets representing all possible utility functions compatible with the preference information obtained so far must be considered. The same observation applies to approval thresholds. Under such utility uncertainty, we investigate now the determination of possible winners.

Determination of Possible Approval Winners

In this section, we propose an algorithm that enables to compute the set of possible approval winners given some partial knowledge of the agents' preferences. More precisely, the input of the algorithm consists of three sets of preference information for each agent i ∈ N : a set A i (resp. Āi ) of solutions that are known to be approved (resp. not approved) by agent i, and a set P i of pairs (y, z) such that solution y is known to be preferred to solution z by agent i. The elements of P i are not explicit approval statements, but can be used to derive new positive or negative approval statements from those included in A i and Āi .

Let U i (resp. ∆ i ) denote the set of utility functions (resp. approval thresholds) compatible with the available preference statements A i , Āi and P i . Formally, (U i , ∆ i ) is the set of all pairs (u i , δ i ) such that: ∀x ∈ A i , u i (x) ≥ δ i ; ∀x ∈ Āi , u i (x) < δ i and ∀(y, z) ∈ P i , u i (y) ≥ u i (z), where u i is a function of the form u i (x) = j∈P u i j x j and δ i ∈ R. Let U (resp. ∆) be the cartesian product

U 1 × . . . × U n (resp. ∆ 1 × . . . × ∆ n ).
Given such uncertainty sets, the set PW(X , U, ∆) of possible approval winners is defined as follows:

Definition 1. P W (X , U, ∆) = u∈U,δ∈∆ arg max x∈X f (x, u, δ)
In other words, the set of possible approval winners is the set of all solutions x ∈ X that maximize the approval score f (x, u, δ) for some utility profile u = (u 1 , . . . , u n ) ∈ U and some approval threshold vector δ = (δ 1 , . . . , δ n ) ∈ ∆. Recall that Example 2 shows that standard dynamic programming procedures cannot be used to determine the approval winners when utilities and approval thresholds are known. This difficulty remains when utilities and/or approval thresholds are partially known.

The branch and bound approach is the most commonly used tool for solving NP-hard optimization problems. We propose here a branch and bound procedure to compute the set PW(X , U, ∆), where nodes of the search tree represent partial instances of the decision variable vector x = (x 1 , . . . , x p ). More precisely, each node η of the tree is characterized by a pair (P 0 η , P 1 η ) where P k η = {j ∈ P, x j = k}, k = 0, 1. Let P η = P \ (P 0 η ∪ P 1 η ) denote the set of all undecided variables at node η. Thus, each node η is associated with a region of the solution space as follows: solution x = (x 1 , . . . , x p ) is attached to node η if and only if x j = k for all j ∈ P k η , k = 0, 1. The set of feasible solutions attached to node η is denoted by S η hereafter. The main features of the search procedure are the following:

Initialization. Using a heuristic, a branch and bound procedure determines some feasible solutions before performing the search so as to define an initial bound on candidate solutions.

In order to obtain such a bounding set for the knapsack problem, denoted by S 0 hereafter, we propose to initially ask the agents to rank all the items by preference order. Let r i (j) denote the rank of item j in the preference order provided by agent i, we can define the score α i (j) = p-ri(j) wj for each agent i ∈ N and each item j ∈ P representing the tradeoff achieved between preference and weight. Hence, for each agent i, a "good" solution to the knapsack problem can be obtained by a greedy algorithm selecting items one by one, by decreasing order with respect to scoring function α i , skipping elements whose weight is greater than the residual weight capacity. The resulting solution is inserted in S 0 for initialization because it represents a good solution from the point of view of agent i. This process is repeated for all agents i ∈ N .

Moreover, a similar procedure is used with the average scoring function defined by α(j) = 1/n n i=1 α i (j), to complete S 0 with a solution which is likely to be more consensual. This solution will be denoted by s in the sequel.

Evaluation and pruning. Our pruning rule is based on the notion of setwise regret defined as follows: the setwise max regret R(A, B, U, ∆) of a set A ⊆ X with respect to a set B ⊆ X is the maximal feasible approval score difference between the best solution in B and the best solution in A. More formally:

R(A, B, U, ∆) = max u∈U,δ∈∆ max b∈B f (b, u, δ) -max a∈A f (a, u, δ)
If R(A, B, U, ∆) < 0, then we know that B does not contain any possible approval winner; it indeed induces that, for all solutions b ∈ B, for all u ∈ U and for all δ ∈ ∆, there exists a ∈ A such that f (b, u, δ) < f (a, u, δ).

Let S be the set of solutions found so far (initially S = S 0 ) and O be the current set of nodes to be explored. We propose to prune a node η ∈ O if the setwise max regret R(S, S η , U, ∆) of set S with respect to set S η is strictly negative. Note that R(S, S η , U, ∆) = max x∈Sη max u∈U,δ∈∆ min s∈S {f (x, u, δ) -f (s, u, δ)}. This alternative formulation enables to compute R(S, S η , U, ∆) as the optimal value of the mixed-integer quadratic program (denoted MIQP η ) given in Figure 1.

In this program, ξ > 0 is an arbitrary small value allowing us to model strict inequalities. Equations (5-7) enable to restrict utility functions and approval thresholds to those compatible with the available preference information. Since preferences of agent i, for any i ∈ N , are invariant by positive affine transformations jointly applied to function u i and threshold δ i , we can assume without loss of generality that utilities are positive and bounded above by a constant M > 0 (cf. Equation ( 4)). Moreover, a i s is a boolean variable equal to 1 iff agent i approves solution s, s ∈ S, and a i is a boolean variable equal to 1 if agent i approves solution x. Finally, Equation (1) introduces variable t ∈ R representing the smallest approval score difference between solution x and solution s, s ∈ S.

max t s.t. t ≤ i∈N a i - i∈N a i s , ∀s ∈ S (1) j∈P 1 η u i j + j∈Pη u i j x j -δ i ≥ M (a i -1), ∀i ∈ N (2) j∈P u i j s j -δ i + ξ ≤ M a i s , ∀s ∈ S, ∀i ∈ N (3) j∈Pη w j x j + j∈P 1 η w j ≤ W j∈P u i j = M, ∀i ∈ N (4) j∈P u i j y j ≥ δ i , ∀i ∈ N, ∀y ∈ A i (5) j∈P u i j y j ≤ δ i -ξ, ∀i ∈ N, ∀y ∈ Āi (6) j∈P u i j y j ≥ j∈P u i j z j , ∀i ∈ N, ∀(y, z) ∈ P i (7) x j ∈ {0, 1}, ∀i ∈ N, ∀j ∈ Pη a i ∈ {0, 1}, a i s ∈ {0, 1}, ∀i ∈ N, ∀s ∈ S u i j ≥ 0, δ i ≥ 0, ∀i ∈ N, ∀j ∈ P Figure 1: Problem MIP η
Note that constraints given in Equation (2) include quadratic terms of type u i j x j , j ∈ P η , since u i j are also variables of the optimization problem. In order to linearize theses constraints, we introduce positive variables v i j , i ∈ N, j ∈ P η , representing the product u i j x j and Equation ( 2) is replaced by the following constraints:

j∈P 1 η u i j + j∈Pη v i j -δ i ≥ M (a i -1), ∀i ∈ N v i j ≤ u i j , ∀i ∈ N, ∀j ∈ P η v i j ≤ M x j , ∀i ∈ N, ∀j ∈ P η v i j -u i j ≥ M (x j -1), ∀i ∈ N, ∀j ∈ P η
The resulting mixed-integer linear program is denoted by MIP η in the sequel.

Branching. Values R(S, S η , U, ∆) available for all nodes η ∈ O is also used to select the next node to be explored. We select here a node η ∈ O which maximizes R(S, S η , U, ∆). This selection strategy aims at maximally improving the current solution set S. The optimal solution of MIP η indeed maximizes the gap f (x, u, δ) -max s∈S f (s, u, δ) over all u ∈ U , all δ ∈ ∆ and all x ∈ η ∈O S η . Then, set S η is split in two by considering possible instantiations of a new variable x j , j ∈ P η . This variable is chosen among those equal to 1 in the optimal solution of MIP η .

Filtering. As we will see in Proposition 1, the proposed Branch and Bound outputs, in general, a superset of the set of possible approval winners. To remove undesirable elements, we use a final filtering process which deletes solution s ∈ S such that R(S\{s }, {s }, U, ∆) < 0, using a simplified version of MIP η .

The algorithm implementing these principles is referred to AS (Approval-based Search) in the sequel and it is summarized by Algorithm 1.

Algorithm 1: Possible Approval Winners Determination

Input: S 0 : initial solutions Output: PW(X , U, ∆) Proof. Since the pruning rule only discards nodes including no possible approval winner, we know that S is a superset of PW(X , U, ∆) at the end of the while loop. Let x be an element inserted in S such that x ∈ PW(X , U, ∆), if it exists. Since x is not a possible winner, we know that, for all u ∈ U and for all δ ∈ δ, there exists x ∈ PW(X , U, ∆) ⊆ S such that f (x, u, δ) < f (x , u, δ). Therefore, x is necessarily removed from S during the filtering by definition of the filtering process.

1 S ← S 0 2 η ← [∅, ∅] 3 O ← {η} 4 while O = ∅ do 5 Select a node η ∈ O 6 if P η = ∅ then 7 S ← S ∪ S η
Depending on the uncertainty sets (U and ∆) implicitly defined by the available preference information, possible approval winners might be too numerous to be enumerated efficiently. In order to save time, one may be interested in approximating the set of possible approval winners with performance guarantee. We propose below a variant of Algorithm AS for approximating possible winners with some guarantee on the quality of the output.

Approximation. Given a constant ε > 0, a set X ⊆ X is an (1 + ε)-approximation of the set of possible winners if, for all x ∈ X , all u ∈ U and all δ ∈ ∆, there exists x ∈ X such that f (x, u, δ) ≤ (1 + ε)f (x , u, δ). In order to compute an (1 + ε)-approximation of the set of possible winners, we introduce an approximate version of the setwise max regret. The setwise max ε-regret R ε (A, B, U, ∆) of a set A ⊆ X with respect to a set B ⊆ X is defined as follows:

R ε (A, B, U, ∆) = max u∈U,δ∈∆ max b∈B f (b, u, δ) -(1 + ε) max a∈A f (a, u, δ)
If R ε (A, B, U, ∆) ≤ 0, then we know that, for all b ∈ B, all u ∈ U and all δ ∈ ∆, there exists a ∈ A such that f (b, u, δ) ≤ (1 + ε)f (a, u, δ). Therefore, we propose a variant of AS where a node η ∈ O is discarded if R ε (S, S η , U, ∆) ≤ 0. This pruning rule is sharper than the previous one and is more likely to discard nodes in the search tree. The implementation is simple within Algorithm AS: computations of R values must simply be replaced by computations of R ε values. Moreover, the value R ε is obtained using MIP η in which Equation ( 1) is replaced by:

t ≤ i∈N a i -(1 + ε) i∈N a i s , ∀s ∈ S
The resulting algorithm is denoted by AS ε in the sequel. Then, the following proposition holds.

Proposition 2. AS ε returns an (1 + ε)-approximation of the set PW(X , U, ∆).

Proof. Let x be a solution that does not belong to S at the end of the search procedure. Let u ∈ U and δ ∈ ∆. We want to prove that f (x, u, δ) ≤ (1 + ε)f (s, u, δ) for some s ∈ S.

If x was inserted in S at some step, then x has necessarily been deleted during the filtering of S. In that case, by definition of the filtering, we know that there exists s ∈ S such that f

(x, u, δ) ≤ f (s, u, δ); hence, f (x, u, δ) ≤ (1 + ε)f (s, u, δ).
Assume now that x was discarded at some step without ever belonging to S. In that case, we know that, there exists at this step s ∈ S such that f (x, u, δ) ≤ (1 + ε)f (s, u, δ). If solution s belongs to S at the end of the procedure, then we can directly infer the result. If solution s is deleted during the filtering, then we know that there exists

s ∈ S such that f (s, u, δ) ≤ f (s , u, δ). Therefore, f (x, u, δ) ≤ (1 + ε)f (s, u, δ) ≤ (1 + ε)f (s , u, δ
) which completes the proof (note that there is no chaining of errors).

Elicitation for Winners Determination

In Section 3, we have introduced a procedure to determine the set of possible approval winners. It can be used in situations where a significant part of approval judgements is available. However, with incomplete preference information, the number of possible winners often remains very large, due to the combinatorial nature of the knapsack problem. Actually, the notion of possible winner (even its approximate version) is not sufficiently discriminant to support efficiently a collective decision making process. On the other hand, the full elicitation of approval statements in a multi-agent knapsack problem requires O(n2 p ) queries, for n agents and p items. This prevents to perform a full elicitation of approval statements prior to the aggregation of preferences.

In order to overcome these problems, we propose now an incremental approach that combines preference elicitation and search to determine the approval winner(s). The basic principle of our approach is to collect approval statements from individuals so as to progressively reduce the uncertainty attached to approval scores until the actual winners can be determined.

The number of possible winners reduces with the uncertainty about the agents' preferences. More precisely, for any U ⊆ U and any ∆ ⊆ ∆, we have PW(X , U , ∆ ) ⊆ PW(X , U, ∆). If U reduces to a single utility profile and ∆ to a single approval threshold vector, then the possible winners become the actual winners of the election, i.e. the solutions maximizing the approval score, among which the final winner is selected using a tie-breaking rule. If we consider an incremental elicitation procedure which progressively collects preference information so as to reduce sets U and ∆, we will reach a point where all possible winners are necessary winners. This will generally happen long before reducing U and ∆ to singletons.

We propose now an incremental elicitation procedure progressively reducing uncertainty sets to U and ∆ such PW(X , U , ∆ ) = NW(X , U , ∆ ) where NW(X , U , ∆ ) represents the set of necessary winners, i.e., the set of elements in X which are optimal for all u ∈ U and all δ ∈ ∆ . Our incremental elicitation algorithm consists in inserting preference queries in Algorithm AS (see the previous section) so as to discriminate between the current best solutions (those that were stored in S). In practice, S is now restricted to the most approved solutions found so far. Within this set we can arbitrarily select a representative, named the incumbent. Initially, the incumbent may be any feasible solution to the knapsack problem (e.g., solution s, see the initialization in Section 3). Each time a new solution is found (a challenger), it is compared to the incumbent w.r.t. approval scores.

Note that, given the current uncertainty sets U and ∆, a solution x ∈ X is necessarily approved by an agent i, i ∈ N, if and only if u i (x j ) ≥ δ i holds for all u ∈ U and all δ ∈ ∆. This can be checked by solving the following linear program: min j∈P u i j x j -δ i subject to Equations (4-7) and u i j ≥ 0, δ i ≥ 0, ∀i ∈ N, ∀j ∈ P , and testing whether the optimum is positive. Similarly, testing whether a solution x ∈ X is necessarily disapproved by an agent can be performed using linear programming. Thus, each time a new solution is found, we can efficiently determine the agents -if they exist -that necessarily approve/disapprove it. Then, a natural query generation strategy, denoted by σ 0 hereafter, consists in questioning all the other agents to know whether they approve this solution. The challenger will be inserted in S if it has the same approval score as the incumbent. If the challenger is strictly better than the incumbent, then S is reinitialized to include only the challenger. This strategy provides an incremental search algorithm to determine the set of approval winners, named Algorithm IAS (Incremental Approval-based Search) in the sequel.

Proposition 3. For any initial uncertainty sets U and ∆, IAS terminates with uncertainty sets U ⊆ U and ∆ ⊆ ∆ such that PW(X , U , ∆ ) = NW(X , U , ∆ ). Proof. Let s ∈ S be any solution returned by IAS. For all x ∈ X , we want to prove that, at the end of the search procedure, we have f (s, u, δ) ≥ f (x, u, δ) for all u ∈ U and all δ ∈ ∆ . First, whenever a node η is pruned at some step k of IAS using the current incumbent s k , we know that, for all x ∈ S η , f (x, u, δ) ≤ f (s k , u, δ) for all u ∈ U k and all δ ∈ ∆ k where U k and ∆ k are the current uncertainty sets at step k. Since U ⊆ U k and ∆ ⊆ ∆ k , we have f (x, u, δ) ≤ f (s k , u, δ) for all u ∈ U and all δ ∈ ∆ . Then, according to strategy σ 0 , we know that s k is such that f (s k , u, δ) ≤ f (s, u, δ) for all u ∈ U and all δ ∈ ∆ . The result is obtained by transitivity.

Numerical Tests

We report here numerical experiments where mixed-integer and linear programs are solved using the Gurobi Optimizer.

The first series of tests aims at evaluating the computation times (given in seconds) of possible winners calculation using AS and AS ε . In these experiments, instances of the multi-agent knapsack problem with p = 12 are generated as follows: weights w j , j ∈ P are uniformly drawn in {1, . . . , 100}. Then, capacity W is set to d × j∈P w j where d = 0.3, 0.4 and 0.5 so as to vary the number of solutions: for p = 12, the number of feasible solutions is then approximatively equal to 500, 1000 and 2000 respectively. Moreover, to evaluate the impact of the uncertainty sets, we randomly generate q = 10, 20 preference statements per agent before running the algorithms. The computation times obtained by averaging over 50 runs for instances with n = 20 are reported in Table 1. We also report the average number of possible winners denoted by #S. As expected, we can see that computation times increase with the size of the problem, and decrease as the number of available preference statements increase. Moreover, we observe that AS 0.1 is drastically faster than AS. More precisely, AS 0.1 determines an 1.1-approximation of possible winners in a few seconds while AS needs a few minutes on average.

The second series of experiments aims at evaluating the performance of IAS in terms of computation times (given in seconds) and average number of queries per agent (denoted by #Q hereafter). We also report the average number of actual winners (denoted by #S hereafter). Initially, only the preference ranking over single items is available for each agent. Then, answers to approval We focus now on the evaluation of the branching strategy which is of crucial importance for the efficiency of the query generation strategy proposed in Section 4. This elicitation strategy indeed consists in asking agents whether they approve or not some solutions found during the search; these solutions are obviously dependent on the branching strategy. For comparison, we also consider the interactive branch and bound procedure (named Random hereafter) that differs from IAS only on the branching strategy as follows: the next node to be explored and the next variable to be instantiated are both selected at random. For both branching strategies, each time an agent answers an approval query during the resolution, we compute the maximum regret attached to the incumbent s, which is equal to max x∈X max u∈U,δ∈∆ f (x, u, δ) -f (s, u, δ) . This quantity is an upper bound on the actual regret when choosing the incumbent instead of any other solution in terms of approval scores. Whenever this value equals zero, the incumbent is necessarily an approval winner. Regrets are here expressed on a normalized scale assigning value 1 to the initial maximum regret (computed before collecting any preference information) and value 0 when the maximum regret is zero. Figure 2 shows the results obtained by averaging over 30 runs for decision problems involving 30 agents. We can see that the maximum regret reduces much more quickly with IAS than with Random. For instance, after 240 queries (i.e., 8 queries per agent) on average, the regret of choosing the incumbent is under 10% of the initial regret, whereas it remains above 65% with the random branching strategy. Hence, our elicitation strategy is much more informative when using our regret-based branching strategy rather than the random branching strategy.

d = 0.3 d = 0.4 d = 0.5 method q time #S

Conclusion

We have presented a new approach for incremental approval voting on combinatorial domains, illustrated on the knapsack problem. The first specificity of this approach is to exploit compact numerical representations of individual preferences (additive utilities) to propose more efficient elicitation sequences. Thus, learning that agent i approves or not solution x is no longer an isolated preference information; it induces a constraint on the utility space possibly reducing the set of weak-orders consistent with the observed preferences. This contributes to derive implicitly other approval judgements on other knapsacks, which saves many preference queries.

The second specificity of our approach is to interleave preference elicitation and search. This makes it possible to elicit preferences on a combinatorial set implicitly defined with a twofold benefit in view of winner determination: on the one hand, working on partial instances of feasible solutions in the search tree facilitates the identification of relevant preference queries and relieves the elicitation burden. On the other hand, the search is earlier focused on the relevant part of the solution space due to the integration of new preference information at any decisive step of the search algorithm, which saves a significant part of the computational effort. This enables to solve large instances for which the systematic elicitation of all approval statements is not feasible.

We see several directions to extend this work. The first one is to relax the additivity of individual utilities so as to be able to model interactions between items. In this line, it seems natural to use generalized additive utilities functions (GAI) that could also be elicited incrementally [START_REF] Braziunas | Minimax regret based elicitation of generalized additive utilities[END_REF]. Another direction would be to consider alternative voting rules using possibly more information than approval statements. For example, positional scoring rules may be worth investigating under the assumption that individual preferences are representable by additive utilities. This is a challenging issue because, when preferences are only partially known, the ranges of possible ranks of solutions in individual rankings is generally too large to be decisive. Similar difficulties may also occur with other standard voting rules (e.g., single transferable voting, Copeland's rule) when applied to a combinatorial problem.

O

  Select an item j ∈ P η 10 Generate the nodes η = [P 0 η ∪ {j}, P 1 η ] and η = [P 0 η , P 1 η ∪ {j}] 11 if S η = ∅ and R(S, S η , U, ∆) ≥ 0 then 12 O ← O ∪ {η } 13 end 14 if S η = ∅ and R(S, S η , U, ∆) ≥ 0 then 15 solution set S 21 return S This algorithm is justified by the following proposition: Proposition 1. AS returns the set PW(X , U, ∆).

Figure 2 :

 2 Figure 2: Maximum regret attached to the incumbent with respect to the total number of queries (p = 12, d = 0.4).

Table 1 :

 1 Computations of possible winners (in seconds). queries are simulated using approval thresholds and utility functions randomly generated with negative correlations so as to obtain difficult instances. Due to the possibility of collecting preference information during the search, algorithm IAS is significantly faster than AS and can solve much larger instances. For example, we report the results obtained for p = 15 and p = 18 (with d = 0.5), which approximatively represents 2000, 16000 and 130000 feasible solutions respectively. Results obtained by averaging over 50 runs are reported in Table2for instances involving 10 and 30 agents. We can see that IAS is very efficient both in terms of number of queries per agent and computation times; for instance, for problems with 10 agents and 18 items (130000 feasible solutions), it enables to determine the set of optimal knapsacks for approval voting in about 70 seconds with less than 16 queries per agent on average, whereas the full elicitation of approval statements would require 130000 queries per agent.

					time #S	time	#S
	AS	10 26.6 19.8 71.8 29.8 614.4 111.4
	AS	20 25.2 17.4 55.7 23.9 442.3	90.3
	AS 0.1	10	1.1	1.9	2.7	3.8	13.9	8.3
	AS 0.1	20	1.0	1.6	2.3	2.7	9.4	5.0
			p = 15		p = 18
	n	time #S #Q	time #S #Q
	10	24.3 26.5 10.3	69.8 71.9 15.5
	30	90.3 11.4	9.3 314.5 16.8 13.9

Table 2 :

 2 Computations of necessary winners (in seconds).