○giovanni De Magistris

Asim Munawar

Phongtharin Vinayavekhin

Teaching a Robot Pick and Place Task using Recurrent Neural Network

Keywords: Machine Learning, Robotics, Pick and Place

Programming a robot to perform a specific task is generally time consuming. This paper proposes a novel method to teach new task to a robot. The main contribution is the idea of building a task planner based on a Recurrent Neural Network (RNN). The neural network learns how to plan a task from observing a task sequence generated from a general motion planner. The method is evaluated by teaching pick and place tasks to a Baxter robot. The experiences are performed in a physical simulator. It shows that the robot can adapt to pick and place an object in various initial positions.

Introduction

Robots are extensively used in production lines because they can help increasing in both production speed and consistency. They also save workers from tedious and dull repetitive tasks. However, when a production line is set to a new task, significant effort is required to program each robot for this new process. More specifically, human operators have to position the robot in all the desired configurations, record these values, and then control the robot to repeat this trajectory/path during the later execution. It is also required that all objects involved are placed precisely at the same positions.

Considering the significant progress in machine learning, this human effort can be completely automated to create a robust model that can be generalized for different object types and positions. In this way, we can simplify the establishment of the production line and at the same time gain flexibility for the operation of the line.

The paper proposes a deep learning based approach to learn a pick and place task for an industrial manipulator robot. The approach can be generalized to various object initial locations. The technique is biologically inspired.

Human neo cortex is essentially a prediction system that issue motor commands based on the current context and the visual and motor feedback (Fig. 1). The system uses a memory based learning system to learn the spatial and temporal encodings of an action. During the inference phase the system can predict the optimal next action to successfully complete the given task.

In this paper we have used a recurrent neural network (RNN) to teach the robot to perform the pick and place task. The system learns to take the next best action based on the previous actions and observations that it has made.

Due to the feedback at each step the system can correct itself in case of minor changes during the task. We give the joint angles and the object location to the system at each step and the system learns the spatial relationship between the object and robot angles.

Implicitly it is learning the inverse kinematics of the robot to perform a certain operation.

The remaining paper is organized as follows. Sec. 2 discuss the related work. The description of the pick and place task is given in Sec. 3. In Sec. 4 we illustrate the method to perform the task. Results are given in Sec. 5.

Conclusions and some future directions are given at the end of the paper.

Related work

Over the last few decades, there have been great improvements in industrial robot programming. Early methods required to control the robot movement defining the joint trajectories. Now the programming rather performed at the higher task level [START_REF] Hgele | Industrial Robotics[END_REF]. At the task level, a common approach is to acquire various key-points that represent the task and generate the program accordingly.

A limitation of this approach is that if anything in the recorded configuration of the environment has been modified, for instance if the object position, then the learned program is no longer valid.

To make the robot more flexible, it is becoming common to train the robot instead of explicit programming. Some research in this area use learning from demonstration to teach the robot to perform pick and place without programming to perform the task [START_REF] Toris | Spatial and Temporal Learning in Robotic Pick-and-Place Domains via Demonstrations and Observations[END_REF].

Another technique is to make the robot learn from its own experience using reinforcement learning. Deep learning combined with reinforcement learning is used to solve the pick and place task without explicit programming. Recent progress in using deep learning for robotics [START_REF] Levine | Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collection[END_REF][START_REF] Pinto | Supersizing Self-supervision: Learning to Grasp from 50K Tries and 700 Robot Hours[END_REF], an attractive idea is to develop a learning system that can be generalized to various environment conditions. In particular, this paper focuses on the change of object position of the pick and place task. They are less prone to noise. They also remember which phase are they in right now. Therefore, instead of going directly to the target such systems can also take a suboptimal action to follow a predefined motion trajectory to accomplish the task. In this paper we show how a memory based deep network can be used to teach the pick and place task to an industrial robot.

Task Description

A pick and place task is simulated in this paper to show the promising results of our approach. We perform this task using the left arm of the robot. The end-effector is the left arm gripper.

We divide the pick and place into two sub-tasks and we break down them into 5 states. The Finite State Machines of PICK and PLACE sub-tasks are shown in Fig. 2.

The states of the PICK are (the description of the Place states is similar):

• Start: at the start of the physics simulation, Baxter's left arm is at random 3D end-effector position (x end ,y end ,z end ).

• Approach: the end-effector moves to the object position in x and y directions and (z obj +h) in z direction.

• Grasp: the end-effector goes to the object position.

• Close Gripper: close the gripper attached to the left arm.

• Retract: the end-effector moves to (z obj +h) in z direction.

The place position in Fig. 2 is the same for all simulations (training and test data).

Data-driven Task Planner using LSTM

Robot learns how to plan the task using a specific type of Recurrent Neural Network (RNN) called Long Short-Term Memory (LSTM) [START_REF] Hochreiter | Long short-term memory[END_REF]. Two LSTM networks are trained to learn a pick task and a place task separately.

Once learned, the network is used to plan the task by varying the initial object location and robot joint positions. This section starts by explaining how training data is prepared. Then the details of how LSTM network is used to learn the task is given in the later subsection.

Preparing Training Data

Training data is generated in a physics-based virtual environment. A motion planning framework is used to create multiple samples of pick and place motion. Although the place location (x place , y place , z place ) is same for all samples, the last four columns of the place task are different due to the redundancy of the robot arm.

Building a Task Planner

The task planner is constructed by learning from the training data using LSTM. As mentioned earlier, a pick task and a place task is learned separately using two networks, but with the same network architecture as shown in Fig. 3. The network is trained to output the next state, i.e. when a description of state i is given as an input, the expected output would be the description of the state i+1 .

The loss function of a network is a mean squared error of the output and actual desired state description.

To plan both task, the initial state of the robot arm and object location is given to the trained network of a pick task. The network will output the state description stating the joint angles that the robot arm needed to move to. An interpolator is currently used in practice, while a more complicate motion planner can also be cooperated to move between two states of joint angles if any collision avoidance is required. The procedure is repeated until the last states of a place task is achieved.

Results

We evaluate our approach on Baxter robot in a simulated physics-based virtual environment (Gazebo

Conclusion and future works

In this paper, we illustrated a method to perform a robot task using LSTM. Given a FSM, the robot learns the relationship between the joint angles and object position to perform the task. We used this approach to simulate an experimental Pick and Place robot activity.

These encouraging results show the potentials of current deep learning techniques in robotics. In a near future, we plan to apply similar techniques to different industrial tasks and real robots.

Figure 1 :

 1 Figure 1: Human neural system decides the next action it needs to take based on the previous observations.

Figure 2 :

 2 Figure 2: Images of the the pick and place states taken during Baxter performing the task: the whole task is divided and learned (using two LSTM) into two parts: Pick and Place

  Although each sample of pick and place sequences are continuously generated in practice, they are divided and stored separately into two training data for each task. Each training sample for a pick task is a 10x5 matrix. Each column representing a state in a task description. The first seven dimensions represent the joint angles of the robot (left) arm, while the remaining three values are the object location. The first column among samples are randomly initialized which correspond to random end effector position and object location. Similarly, in a place task each training sample is a 10x5 matrix and each column represents joint angles of the robot arm and object location. During data generation, the first column is copied from the last column of pick task.

Figure 3 :

 3 Figure 3: Network Architecture

Figure 4 :

 4 Figure 4: Loss function


Mostapha Diss
email: diss@gate.cnrs.fr

Ahmed Doghmi
email: ahmeddoghmi@hotmail.com

Abdelmonaim Tlidi

Startegy proofness and unanimity in private good economies with single-peaked preferences

Keywords: Strategy-proofness, Unanimity, Maskin monotonicity, Private good economies, Single-peaked preferences C72, D71 Strategy-proofness, Unanimity, Maskin monotonicity, Private goods economies, Single-peaked preferences. JEL classification: C72, D71

In this paper we establish the link between strategy-proofness and unanimity in a domain of private good economies with single-peaked preferences. We introduce a new condition and we prove that if this new property together with the requirement of citizen sovereignty are held, a social function satisfies strategy-proofness if and only if it is unanimous. As an implication, we show that strategy proofness and Maskin monotonicity become equivalent. We also give applications to implementation literature: We provide a full characterization for standard Nash implementation, and partially honest Nash implementation and we determine a certain equivalence among these theories.

Introduction

Arrow [START_REF] Arrow | Social Choice and Individual Values. 2nd Edition[END_REF] was the first who wondered about the issue of constructing non-dictatorial welfare functions by examining the combination of some desirable properties. These well-known prespecified properties are called unrestricted domain, Pareto efficiency, and independence of irrelevant alternatives. He showed that any social welfare function satisfying these properties, with at least two individuals and at least three alternatives, is dictatorial. Gibbard [START_REF] Gibbard | Manipulation of voting schemes: a general result[END_REF] and Satterthwaite [START_REF] Satterthwaite | Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions[END_REF] inspected the possibility of constructing non-dictatorial and non-manipulable (strategy-proof) social choice functions. They proved that, in a strategic voting, if there are at least three alternatives, strategyproofness of any social choice function is equivalent to dictatorship.

From these two well-known impossibility results, the literature on social welfare and social choice functions contains two main approaches in order to derive possibility results. The first one is based on the relaxation of some properties provided by Arrow [START_REF] Arrow | Social Choice and Individual Values. 2nd Edition[END_REF] for social welfare functions and by Gibbard [START_REF] Gibbard | Manipulation of voting schemes: a general result[END_REF] and Satterthwaite [START_REF] Satterthwaite | Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions[END_REF] for social choice functions. The second approach with which we are concerned in this paper, is based on the restriction of preference domains available to the individuals. The most commonlyused domain restriction on individual preferences is single-peakedness which allows to have very nice and interesting results. This notion introduced by Black [START_REF] Black | On the rationale of group decision making[END_REF], requires that each agent has a unique best alternative. In this domain, a large number of research papers have examined the class of strategy-proof rules in different types of economies and voting schemes. For instance, Dummett and Farquharson [START_REF] Dummett | Stability in voting[END_REF] and, subsequently, Pattanaik [START_REF] Pattanaik | Collective rationality of group decision rules[END_REF] have shown that majority rule with Borda completion is strategy-proof if both admissible preferences and admissible ballots are restricted to be single-peaked. Moulin [START_REF] Moulin | On strategy-proofness and single peakedness[END_REF] showed that, when adding some fixed ballots to the agent's ballots, all strategy-proof anonymous and efficient voting rules can be derived from the Condorcet procedure. Nehring and Puppe [START_REF] Nehring | The structure of strategy-proof social choice -Part I: General characterization and possibility results on median spaces[END_REF] provided a characterization of the set of social choice functions called voting by issues. They showed that the set of voting by issues coincides with the set of onto social choice functions satisfying strategy-proofness.

In this paper we deal with strategy-proofness versus efficiency on private good economies with single-peaked preferences. Differently to the wide range of literature that has analyzed the relation between strategy-proofness and efficiency in different domain restriction in pure exchange economies, public good economies and voting schemes 1 , there are few studies that inspected strategy-proofness and Pareto-efficiency in private good economies with single-peaked preferences. The well-known work in this subject is the one of Sprumont [START_REF] Sprumont | The division problem with single-peaked preferences: A characterization of the Uniform Rule[END_REF] who characterized the uniform rule of Benassy [START_REF] Benassy | The Economics of Market Disequilibrium[END_REF] on singlepeaked domain. He established that this rule is the only rule that is strategy-proof, anonymous, and Pareto-efficient. Ching [START_REF] Ching | An alternative characterization of the Uniform Rule[END_REF] reinforced this result by replacing anonymity by symmetry. He proved that the uniform rule is the only rule that satisfies strategy- 1 The examination of the link between strategy-proofness and efficiency begins with Hurwicz [START_REF] Hurwicz | On informationally decentralized systems[END_REF] who studied the structure of strategy-proof and Pareto-efficient social choice functions in classical exchange economies. In these domains, Zhou [START_REF] Zhou | Inefficiency of strategy-proof allocation mechanisms in pure exchange economies[END_REF] proved that there is no allocation mechanism that is efficient, non-dictatorial, and strategy-proof. Both Hurwicz [START_REF] Hurwicz | On informationally decentralized systems[END_REF] and Zhou [START_REF] Zhou | Inefficiency of strategy-proof allocation mechanisms in pure exchange economies[END_REF] considered a classical domain where agents preferences are assumed to be continuous, strictly monotonic and strictly convex. Schummer [START_REF] Schummer | Strategy-proofness versus effeciency on restricted domains of exchange economies[END_REF] assumed that agents have homothetic and strictly convex preferences and examined the existence of rules that verify the properties of strategy-proofness and Pareto-efficiency. He proved that any rule satisfying these two properties is dictatorial. Hashimoto [START_REF] Hashimoto | Strategy-proofness versus efficiency on the Cobb-Douglas domain of exchange economies[END_REF] considered a domain of Cobb-Douglas preferences and demonstrated that a SCF is strategy-proof and Pareto-efficient if and only if it is dictatorial. More recently, in a specific quasi-linear domain of pure exchange economies, Goswami et al [START_REF] Goswami | Strategy proofness and Pareto efficiency in quasilinear exchange economies[END_REF] showed that if a SCF satisfies Pareto-efficiency, strategy-proofness, non-bossiness and a mild continuity property, then it is dictatorial. proofness, symmetry, and Pareto-efficiency.

Our main concern in this paper is to show the equivalence between strategy-proofness and unanimity. We introduce the property of Unanimity as a principle requirement to characterize strategy-proof social choice functions for fair allocation problem. Unanimity is a very mild efficiency requirement that tends to be quite compatible with strategyproofness and also with other requirements, but not much attention has been paid to this property in previous literature. By providing a new property (Condition 1), we prove that, if this requirement together with citizen sovereignty are held, a SCF satisfies strategy-proofness if and only if it is unanimous. This result has an implication on the relationship between strategy-proofness and Maskin monotonicity 2 . Thus, we show that if the requirements of citizen sovereignty and Condition 1 are satisfied, strategy-proofness and Maskin monotonicity become equivalent.

In connection with implementation literature, the properties of Maskin monotonicity, unanimity, and strategy-proofness play a central role. Specifically, they constitute respectively necessary conditions for Nash implementation with standard agents, Nash implementation with partially honest agents, and dominant strategy implementation. In our context of private good economies with single-peaked preferences, Doghmi and Ziad [START_REF] Doghmi | On partially honest Nash implementation in private good economies with restricted domains: A sufficient condition[END_REF][START_REF] Doghmi | Nash implementation in private good economies with singleplateaued preferences and in matching problems[END_REF], and Doghmi [START_REF] Doghmi | A simple necessary condition for partially honest Nash implementation[END_REF] proved that Maskin monotonicity and unanimity are not only necessary but become also sufficient when the property of citizen sovereignty is met. Hence, basing on the equivalence results for Maskin monotonicity, unanimity, and strategy-proofness (Theorems 1 and 2), we give a full characterization for standard Nash implementation (Corollary 2) and partially honest Nash implementation (Corollary 3) and we prove that if the requirements of citizen sovereignty and Condition 1 are satisfied, these theories become equivalent (Corollary 4). Hence, we conclude that the property of strategy-proofness is not only a necessary condition for dominant strategy implementation, but provides a full characterization for Nash implementation with standard agents and with partially honest ones. This shows that these later theories and dominant strategy implementation are very near each other in our setup. Therefore, it would be interesting to study the problem of implementation in dominant strategy equilibria rather than in Nash equilibria in private good economies with single-peaked preferences. This is a fruitful area which we leave for future research.

The rest of this paper is organized as follows: In Section 2, we introduce notations and definitions in our framework of private good economies with single-peaked preferences. In Section 3, we present the main result of the paper that establishes the equivalence between strategy-proofness and unanimity. In Section 4, we study the implication of this result on the relationship between strategy-proofness and Maskin monotonicity. In Section 5 we examine the connection between these results and implementation literature and in Section 6 we conclude. 2 Among the works that have been interested in the connection between strategy-proofness and Maskin monotonicity is that of Muller and Satterthwaite [START_REF] Muller | The equivalence of strong positive association and strategy-proofness[END_REF] who the first were showed that, in a model of public good economies, the two properties are equivalent. Bochet and Storcken [START_REF] Bochet | Maximal domains for Maskin monotone Pareto optimal and anonymous rules[END_REF] defined several conditions to construct maximal domains for Maskin monotone and strategy-proof rules. They proved that a choice rule is strategy-proof if and only if it is Maskin monotone. Recently, Klaus and Bochet [START_REF] Klaus | The ralation between monotonicity and strategy-proofness[END_REF] generalized the model of Muller and Satterthwaite by covering private goods economies and they proved that there is a close link between the two properties.

Notations and definitions

In this section, we provide the terminology and notations required for our results. We use the standard model of private good economies with single-peaked preferences. We consider an amount Ω ∈ R ++ of a certain infinitely divisible good that is to be allocated among a set N = {1, ..., n} of n agents. We represent the preference of each agent i ∈ N by a continuous and single-peaked preference relation R i over [0, Ω]. For all x i , y i ∈ [0, Ω], x i R i y i means that, for the agent i, to consume a share x i is as good as to consume the quantity y i . The asymmetrical and symmetrical parts of the relation R i are given by P i and ∼ i , respectively. Single-peakedness means that there is a number p(R i ), called the peak of R i , such that for all

x i , y i ∈ [0, Ω], if y i < x i ≤ p(R i ) or p(R i ) ≤ x i < y i , then x i P i y i .
The class of all single-peaked preference relations is represented by sp i ⊆ i . Let sp = sp 1 × ... × spn be the domain of single-peaked preferences. For R ∈ sp , let p(R) = (p(R 1 ), ..., p(R n )) be the profile of peaks (or of preferred consumptions). A singlepeaked preference relation R i ∈ sp i can be described by the function r i : [0, Ω] → [0, Ω] which is defined as follows: r i (x i ) is the consumption of the agent i on the other side of the peak which is indifferent to x i if it exists, or else, it is 0 or Ω. In other words, if

x i ≤ p(R i ), then, r i (x i ) ≥ p(R i ) and x i ∼ i r i (x i ) if such a number exists or r i (x i ) = Ω otherwise. However, if x i ≥ p(R i ), then, r i (x i ) ≤ p(R i ) and x i ∼ i r i (x i ) if such a number exists or r i (x i ) = 0 otherwise. For R ∈ sp , a feasible allocation for the economy (R, Ω) is a vector x ≡ (x i ) i∈N ∈ R n +
such that i∈N x i = Ω and X is the set of the feasible allocations. For all R i ∈ sp i and all x ∈ X, the lower contour set for agent i at allocation x is denoted by

L(x, R i ) = {y ∈ X | x R i y}.
The strict lower contour set and the indifference lower contour set are denoted LS(x, R i ) = {y ∈ X | x P i y} and LI(x, R i ) = {y ∈ X | x ∼ i y}, respectively. We note that the feasible allocations set is

X ⊆ [0, Ω] × ... × [0, Ω]. Thus, L(x, R i ) = X is equivalent to L(x i , R i ) = [0, Ω].
In addition, for all two feasible allocations x ≡ (x i ) i∈N and y ≡ (y i ) i∈N in the set of the feasible allocations X, the expression x R i y implies x i R i y i . Finally, we note that the free disposability of the good is not assumed and we introduce the definitions that will be useful throughout the paper. Our first definition is the notion of Social choice function.

Definition 1. (Social choice function)

A social choice function (SCF) is a single-valued mapping from sp into X, that associates to every R ∈ sp an element of X.

In other words, a SCF is a function that maps the individual preferences (here assumed to be single-peaked preferences) to a single collective choice in the set X. We now discuss in turn the properties that will play a central role throughout this essay.

The property of Strategy-proofness gives agents an incentive to bid their true preferences since it is a property which requires that no agent ever benefits from misrepresenting his preference relation. For agent i ∈ N and a preference profile R ∈ sp , we obtain a preference profile (R i , R -i ) ∈ sp i by replacing the i's true preference R i by R i and keeping the preferences of other agents R -i unchanged. Then, strategy-proofness is formally defined as follows: Definition 2. (Strategy-proofness) A SCF f satisfies the strategy-proofness property if for all R ∈ sp , all i ∈ N , and all

R i ∈ sp i , f i (R)R i f i (R i , R -i ).
Next, the well-known Unanimity condition means that if everyone prefers a particular allocation over all other allocations, then the SCF should choose this particular allocation. In our context, it is equivalent to the requirement that if there is an allocation at which each agent receives his peak amount, then it should be chosen by the society. The formal statement of this property is given as follows:

Definition 3. (Unanimity) A SCF f satisfies unanimity if for any x ∈ X, any R ∈ sp , and any i ∈ N , L(x i , R i ) = [0, Ω] implies f (R) = x.
The next axiom is called Citizen sovereignty which requires that every possible allocation can be achieved from a set of individual preference ranking. In other terms, this condition implies that everyone must, without restriction, have a say in the allocation process. Formally, we have the following definition: Definition 4. (Citizen sovereignty) A SCF f satisfies the property of citizen sovereignty if for each x ∈ X, there is a profile

R ∈ sp such that f (R) = x.
We also consider the well-known Maskin monotonicity condition. Loosely speaking, consider some profile of preferences R and an allocation x chosen as a solution by the social choice function f : f (R) = x. Now, consider a second preference profile R such that, for each agent, the set of allocations that he now finds at most as good as that allocation contains the corresponding set for his initial preferences:

L(x i , R i ) ⊆ L(x i , R i ).
Then, the allocation should still be chosen as a solution for the new profile: f (R ) = x. Maskin monotonicity is formally defined as follows: Definition 5. (Maskin monotonicity) For all R, R ∈ sp , a SCF f satisfies Maskin monotonicity if for any f (R) = x and any

i ∈ N , L(x i , R i ) ⊆ L(x i , R i ) implies f (R ) = x.

The main result

In this section we study the relation between strategy-proofness and unanimity in private good economies with single-peaked preferences. More precisely, in this framework and under a certain condition, we prove in Theorem 1 that a SCF satisfies strategy-proofness if and only if it is unanimous. In this way, both Proposition 1 and Proposition 2 present a complete proof of this theorem. To show this, we introduce the following lemma.

Lemma 1. If a SCF f satisfies strategy-proofness, and there are two preference profiles

R, R ∈ sp such that for i ∈ N , L(f i (R), R i ) = [0, Ω], then f i (R) = f i ( R). Proof. Let R, R ∈ sp such that for i ∈ N , L(f i (R), R i ) = [0, Ω] (1). We want to show that f i (R) = f i ( R). We first show that f i (R) = f i ( R i , R -i ). From (1), f i (R) R i f i ( R i , R -i ). By strategy-proofness, f i ( R i , R -i ) R i f i (R), and hence f i (R) ∼ i f i ( R i , R -i ). We have in (1), L(f i (R), R i ) = [0, Ω], therefore, by single-peakedness, f i (R) = f i ( R i , R -i ) (2). Now, to prove that f i (R) = f i ( R), we assume that R k = ( R 1 , ..., R k-1 , R k , ..., R n ), i.e., the k -1
first elements come from the profile R and the rest comes from R noting that for k = 1 and k = n+1, we have R

1 = R and R n+1 = R (3). Now, R k+1 = ( R 1 , ..., R k , R k+1 , ..., R n ), i.e., R k+1 = ( R k , R k -k ). We also have R k = (R k , R k -k ). From (2), f i (R k , R k -k ) = f i ( R k , R k -k ), i.e., f i (R k ) = f i (R k+1 ), and hence f i (R 1 ) = f i (R n+1 ). From (3), f i (R) = f i ( R). Q.E.D Proposition 1.
In the private good economies with single-peaked preferences, if the property of citizen sovereignty holds, any strategy-proof SCF satisfies unanimity.

Proof. Assume that a SCF f satisfies citizen sovereignty and strategy-proofness, but not unanimity. Unanimity is violated if, for any x ∈ X, any R ∈ sp , and any i ∈ N , we have

L(x i , R i ) = [0, Ω] (1), but f (R) = x. Denote f i (R) = y i = x i for some i ∈ N (2)
. By citizen sovereignty, there is a profile

R * ∈ sp such that f i (R * ) = x i . From (1), L(f i (R * ), R i ) = [0, Ω]. By Lemma 1 we have f i (R * ) = f i (R), which contradicts (2). Q.E.D.
To examine the converse, we need to introduce the following condition.

Condition 1. Let R ∈ sp , i ∈ N , x, y ∈ X, and let x = f (R). If x i ∈ LS(y i , R i ), then there exists R * ∈ sp such that (i) f i (R * ) = y i and (ii) L(x j , R * j ) = [0, Ω]
for all j ∈ N . Roughly, Condition 1 means that if at a profile Ra socially chosen share x i is strictly dominated by a share y i for an agent i , then there exists a new profile R * , in which the agent i s component y i is chosen, and x i improves it's ranking and becomes top-ranked for all agents. This condition is introduced recently by Diss et al [START_REF] Diss | Strategy proofness and unanimity in many-to-one matching markets[END_REF] in the context of many-to-one matching markets. They provided as examples satisfying this requirement any sub-solution to the stable matching correspondence associated with the set of weakly Pareto efficient outcomes. In our setup, we show in Remark 1 below that this condition is checked by all social choice functions satisfying citizen sovereignty and the following property of external stability: An SCF f (R) ⊆ X is externally stable under R if every allocation in X \ f (R) is dominated by f (R). This property and its weak version are used by Sönmez [START_REF] Sönmez | Strategy-proofness and single-valued cores[END_REF] and Demange [START_REF] Demange | Nonmanipulable cores[END_REF] to characterize strategy-proofness of essentially singlevalued cores and coalitional strategy-proofness of the core correspondence respectively in a general model of indivisible good allocation 3 . Remark 1. If the requirements of citizen sovereignty and external stability hold, any SCF satisfies Condition 1. Proof. Assume not; i.e., for R ∈ sp , i ∈ N , x, y ∈ X, and x = f (R) we have x i ∈ LS(y i , R i ), but for all R * ∈ sp , we have either f i (R * ) = y i (1) or there exists j ∈ N , L(x j , R * j ) = [0, Ω] (2). The statement (1) contradicts the fact that f satisfies citizen sovereignty. For statement (2), L(x j , R * j ) = [0, Ω] for some j ∈ N means that there exists z j ∈ [0, Ω] such that z j P j x j , that is f is not externally stable, a contradiction. Q.E.D Proposition 2. In the private good economies with single-peaked preferences, if Condition 1 holds, then any unanimous SCF satisfies strategy-proofness.

Proof.

Assume that a SCF f satisfies unanimity, but not strategy-proofness. The strategy-proofness is violated if there exist R ∈ sp , i ∈ N , and

R i ∈ sp i , such that f i (R i , R -i )P i f i (R). Denote f i (R) = x i and f i (R i , R -i ) = y i . Hence x i ∈ LS(y i , R i ) (1)
and by Condition 1, there exists R * ∈ sp such that f i (R * ) = y i and L(x j , R * j ) = [0, Ω] for all j ∈ N . By unanimity f (R * ) = x, i.e., f i (R * ) = x i . Therefore, x i = y i which contradicts [START_REF] Arrow | Social Choice and Individual Values. 2nd Edition[END_REF].

Q.E.D.

From Propositions 1 and 2, we complete the proof of the following theorem.

Theorem 1. In the private good economies with single-peaked preferences, if Condition 1 and the property of citizen sovereignty hold, then a SCF satisfies strategy-proofness if and only if it is unanimous.

Implications

As described in the Introduction, the investigation of the relation between Maskin monotonicity and strategy-proofness is not new and there is considerable literature dealing with this issue. In this section, we study the consequence(s) of introducing of the property of unanimity on the relationship between strategy-proofness and Maskin monotonicity. For this, we begin by examining the relation between unanimity and Maskin monotonicity. In this way, we give the following proposition.

Proposition 3. In the private good economies with single-peaked preferences, if the property of citizen sovereignty holds, then any Maskin monotonic SCF satisfies unanimity.

Proof. Suppose not. Let x ∈ X and R ∈ sp be such that for any i ∈ N , [0, Ω] = L(x i , R i ), and f ( R) = x. By the property of citizen sovereignty, for all x ∈ X, there is a profile R ∈ sp such that f (R) = x and so for all i ∈ N , L(

x i , R i ) ⊆ [0, Ω] = L(x i , R i ). By Maskin monotonicity, f ( R) = x, a contradiction. Q.E.D.
From Proposition 2 and Proposition 3, we give the following corollary.

Corollary 1. In the private good economies with single-peaked preferences, if the requirements of citizen sovereignty and Condition 1 hold, then any Maskin monotonic SCF satisfies strategy-proofness. Now, by using Proposition 1, we prove that strategy-proofness implies Maskin monotonicity.

Proposition 4. In the private good economies with single-peaked preferences, if Condition 1 and the property of citizen sovereignty holds, any strategy-proof SCF satisfies Maskin monotonicity.

Proof. Assume that a SCF f satisfies strategy-proofness and citizen sovereignty, but not Maskin monotonicity. Then, for any R, R ∈ sp , any f (R) = x, and any i ∈ N ,

L(x i , R i ) ⊆ L(x i , R i ) (1), but f (R ) = x (2)
. We have f satisfies strategy-proofness; that is for all R ∈ sp , all i ∈ N , and all

R i ∈ sp i , f i (R)R i f i ( R i , R -i ). Hence x i R i f i ( R i , R -i ).
From Proposition 1, f is unanimous. Hence, by (2), f (R ) = x implies that there exist i ∈ N and y i ∈ [0, Ω] such that y i P i x i and by (1) we have

y i P i x i . Let f i ( R i , R -i ) = z i . Therefore y i P i z i (3), by Condition 1, there exists R * ∈ sp such that f i (R * ) = y i and L(z j , R * j ) = [0, Ω] for all j ∈ N . By unanimity f (R * ) = z, i.e., f i (R * ) = z i . Therefore, z i = y i which contradicts (3). Q.E.D.
Through Corollary 1 and Proposition 4, we complete the proof of the second main theorem of the paper.

Theorem 2. In the private good economies with single-peaked preferences, if Condition 1 and the requirement of citizen sovereignty hold, a SCF satisfies strategy-proofness if and only if it is Maskin monotonic.

From Propositions 2, 3, and 4 we complete the proof of the following theorem. Theorem 3. In the private good economies with single-peaked preferences, if Condition 1 and the requirement of citizen sovereignty hold, a SCF satisfies unanimity if and only if it is Maskin monotonic.

Applications to Nash implementation with standard and partially honest agents

In this section we present two applications of our findings on some results from implementation theory. We begin this section by recalling key ideas from implementation theory that are relevant to the topics of our applications.

Implementation theory provides a framework for situations where resources have to be allocated among agents but the information needed to make these allocation decisions is dispersed and privately held. In addition, the agents possessing the private information behave strategically. When a social designer want to maximize the welfare of a society, which is represented by a social choice rule that selects desired outcomes, she/he confronts some agents who state false preferences on alternatives in order to improve their payoff. To address this problem of the truthful revelation, the social designer must conceive a mechanism (game form) which interacts individuals according to their strategic behavior. These individual strategic interactions can produce the predicted outcomes via a solution concept (equilibrium) of the game. A social choice rule is said to be implementable if both the desired and predicted outcomes coincide. This is eventually the aim of implementation theory.

As we have already said in the Introduction, in implementation literature, the properties of strategy-proofness, Maskin monotonicity, and unanimity are central. More precisely, strategy-proofness is a necessary condition for dominant strategy implementation, Maskin monotonicity is a necessary condition for standard Nash implementation, and unanimity is a necessary condition for partially honest Nash implementation. Using the above results of Theorems 1 and 2, we provide in the next subsections a full characterization.

Strategy-proofness versus Nash implementation with standard agents

A SCF f provides desired outcomes for a social designer. To implement this function, the social designer organizes a non-cooperative game (game form) among a set of agents. This game form is a pair Γ = (S, g) with S = S 1 × ... × S n and g : S → X. For each agent i ∈ N , S i is agent i's strategy space, and g is the outcome function that associates an outcome with each profile of strategies. Let R ∈ sp a profile of preferences, and let Nash equilibrium be a solution concept of the game (Γ, R). The set of Nash equilibria at state R is denoted by N E(S, g, R) and the set of Nash equilibria outcomes is g(N E(S, g, R)).

A mechanism Γ = (S, g) implements a SCF f in Nash equilibria if for all R ∈ sp , f (R) = g(N E(S, g, R)). We say that a SCF f is implementable in Nash equilibria if there is a mechanism which implements it.

From Theorem 2 of Doghmi and Ziad [START_REF] Doghmi | Nash implementation in private good economies with singleplateaued preferences and in matching problems[END_REF], it follows that in the private good economies with single-plateaued preferences, when there are at least three alternatives and if the requirement of citizen sovereignty holds, any SCF is Nash implementable if and only if it satisfies Maskin monotonicity. Notice that this result remains true for the domain of single-peakedness which is a particular case of the large domain of single-plateauedness. This domain, which allows agents to be indifferent among several best elements, has been explored by several authors in social choice theory and games theory. The reader is referred to the more recent work of Bossert and Peters [START_REF] Bossert | Single-plateaued choice[END_REF].

The relation of strategy-proofness with Nash implementation can be summarized from Theorem 2 and Theorem 2 of Doghmi and Ziad [START_REF] Doghmi | Nash implementation in private good economies with singleplateaued preferences and in matching problems[END_REF] as follows.

Corollary 2. Let n ≥ 3. In the private good economies with single-peaked preferences, if Condition 1 and the requirement citizen sovereignty hold, a SCF is Nash implementable if and only if it satisfies strategy-proofness.

Strategy-proofness and unanimity versus Nash implementation with partially honest agents

Here, we present an environment of partial honest agents. We consider the same wellknown model as the one considered in Dutta and Sen [START_REF] Dutta | Nash implementation with partially honest individuals[END_REF], Lombardi and Yoshihara [START_REF] Lombardi | Partially-honest Nash implementation: A full characterization[END_REF], Doghmi and Ziad [START_REF] Doghmi | On partially honest Nash implementation in private good economies with restricted domains: A sufficient condition[END_REF], Korpela [START_REF] Korpela | Bayesian implementation with partially honest individuals[END_REF], Holden et al [START_REF] Kartik | Simple mechanisms and preferences for honesty[END_REF], Saporiti [START_REF] Saporiti | Securely implementable social choice rules with partially honest agents[END_REF], Ortner [START_REF] Ortner | Direct implementation with minimal honest individuals[END_REF], Hagiwara et al [START_REF] Hagiwara | An outcome mechanism for partially honest Nash implementation[END_REF], among others. More precisely, we assume that there are some players who have a "small" intrinsic preference for honesty and each honest individual expresses her preferences in a lexicographic way. For a domain of single-peaked preferences sp , let C i be the other components of the strategy space (which depends on individual preferences, social states, . . . ). The set S i = sp × C i represents the strategy profiles for a player i and S = S 1 × ... × S n is a set of strategy profiles. The elements of S are denoted by s = (s 1 , ..., s n ). A domain is a set D sp ⊂ sp . For each i ∈ N , and R ∈ D sp , let τ i (R) = {R} × C i be the set of truthful messages of agent i. We denote by s i ∈ τ i (R) a truthful strategy as player i is reporting the true preference profile. We extend a player's ordering over the set X to an ordering over strategy space S. This is because, the players' preference between being honest and dishonest depends on strategies that the others played and the outcomes which they obtain. Let R i be the preference of player i over S in preference profile R. The asymmetrical and symmetrical parts of R i are denoted respectively by R i and ∼ R i . Let Γ be a mechanism (game form) represented by the pair (S, g), where S i = D sp × C i and g : S → A is a payoff function. Definition 6. A player i is partially honest if for all preference profile R ∈ D sp and (s i , s -i ), (s i , s

-i ) ∈ S, (i) When g(s i , s -i )R i g(s i , s -i ) and s i ∈ τ i (R), s i / ∈ τ i (R), then (s i , s -i ) R i (s i , s -i ). (ii) In all other cases, (s i , s -i ) R i (s i , s -i ) iff g(s i , s -i )R i g(s i , s -i ).
Let N E(g, R , S) be the set of Nash equilibria of the game (Γ, R ). A mechanism Γ = (S, g) implements a SCF f in Nash equilibria if for all R ∈ D sp , f (R) = g(N E(g, R , S)). We say that a SCF f is partially honest implementable in Nash equilibria if there is a mechanism which implements it in these equilibria. In this framework, we recall the Assumption A of Dutta and Sen [START_REF] Dutta | Nash implementation with partially honest individuals[END_REF].

Assumption A. There exists at least one partially honest individual and this fact is known to the planner. However, the identity of this individual is not known to her.

According to Doghmi and Ziad [START_REF] Doghmi | On partially honest Nash implementation in private good economies with restricted domains: A sufficient condition[END_REF], under Assumption A, the property of unanimity alone is a sufficient condition for partially honest Nash implementation in private good economies with single-peaked preferences. Doghmi [START_REF] Doghmi | A simple necessary condition for partially honest Nash implementation[END_REF] shows that, when the requirement of citizen sovereignty holds, unanimity also becomes a necessary property in this area. In connection with strategy-proofness, Proposition 7 and Theorem 2 of Doghmi [START_REF] Doghmi | A simple necessary condition for partially honest Nash implementation[END_REF] give together with Theorem 1 the following result.

Corollary 3. Let n ≥ 3. In the private good economies with single-peaked preferences, if the requirements of citizen sovereignty, Assumption A, and Condition 1 hold, a SCF is partially honest Nash implementable if and only if it satisfies strategy proofness.

From Corollaries 2 and 3, we give the following important result. Corollary 4. Let n ≥ 3. In the private good economies with single-peaked preferences, if the requirements of citizen sovereignty and Condition 1 hold, then standard Nash implementation and partially honest Nash implementation become equivalent.

Conclusion

We have introduced the property of unanimity as a mild requirement of efficiency to characterize strategy-proof social choice functions. We have showed that, under a certain simple condition, if the requirement of citizen sovereignty holds, a SCF satisfies strategyproofness if and only if it is unanimous. We have proved that this result has an impact on the relation between strategy-proofness and Maskin monotonicity, which become equivalent. We have applied these results to implementation setting and we have showed Nash implementation and partially honest implementation are equivalent.

Finally, we would like to mention that our work is based on single-valued rules, thus, it seems very interesting to extend these results for multi-valued rules in a future research. Another important open question is whether our findings can be extended to other environments of individual preferences.

The core is the set of all allocations wich are not dominated by any other allocation. A core is essentially single-valued if it is nonempty-valued, and Pareto indifferent, i.e. two allocations are Pareto indifferent under a preference profil R if they are indifferent for all agents at R.