Eve Floriane Fabre
email: eve.fabre@isae-supero.fr

Mickael Causse

Mélody Mailliez

Lorella Lotto

Investigating the Impact of Decision Framing Manipulations On Ultimatum Game Players

Keywords: Framing effect, Ultimatum game, Responder, Proposer, Decision frame. 1. INTRODUCTION

Decision framing & UG players

The present exploratory study aimed at investigating the impact of decision framing manipulations on ultimatum game players. In Experiment 1 (N = 400), participants played as proposer and were asked to indicate which offer(s), from €1 to €9, they wanted to either keep for themselves or give to the responder. Participants offered a higher minimal amount of money to responders in the keep frame than in the give frame, suggesting that proposers modulated their strategic behavior according to the frame. In Experiment 2 (N = 188), participants played as responders and were asked to indicate which offer(s) they would either accept or reject. Responders' minimal offer acceptable was higher in the reject frame than in the accept frame, suggesting that the accept/reject frame manipulation might modulate responders' balance of concerns (i.e., maximizing their gains versus punishing unfairness).

The present study offers new insights into framing effects.

According to normative models (i.e., game theory;[START_REF] Von Neumann | Theory of games and economic behavior[END_REF], decisions should not be affected by the way the different alternatives of a problem are presented (i.e., invariance axiom). [START_REF] Kahneman | Prospect theory: An analysis of decision under risk[END_REF] were the first to disprove the invariance axiom by demonstrating that equivalent descriptions of a decision problem can systematically lead to different decisions, a phenomenon called framing effect [START_REF] Fox | Prospect theory and the brain[END_REF][START_REF] Tversky | The framing of decisions and the psychology of choice[END_REF]. Framing effects have been widely investigated in the field of economics using a great diversity of paradigms [START_REF] Kahneman | Frames and brains: Elicitation and control of response tendencies[END_REF], among which the Ultimatum Game (UG; i.e., a key paradigm in the investigation of fairnessrelated decision making; [START_REF] Camerer | Anomalies, Ultimatums, Dictators and Manners[END_REF][START_REF] Camerer | Behavioral Game Theory: Experiments in Strategic Interaction[END_REF][START_REF] Güth | An Experimental Analysis of Ultimatum Bargaining[END_REF]. In the UG, frame manipulations can be performed both on the offers and the decisions of the players [START_REF] Fabre | Investigating the impact of offer frame manipulations on responders playing the ultimatum game[END_REF][START_REF] Leliveld | Initial ownership in bargaining: Introducing the giving, splitting, and taking ultimatum bargaining game[END_REF][START_REF] Sarlo | Framing the ultimatum game: gender differences and autonomic responses[END_REF][START_REF] Tomasino | Framing the ultimatum game: the contribution of simulation[END_REF]. To our knowledge, the impact of decision framing manipulations on UG players' decision-making has never been properly investigated. The present study aims at filling this gap in the literature.

Proposers and Responders Playing the Ultimatum Game

The UG is a two-player game in which the first player called proposer is given a fixed amount of money (e.g., 10 euro) that s/he has to split with a second player called responder [START_REF] Güth | An Experimental Analysis of Ultimatum Bargaining[END_REF]. In the case the responder rejects that offer, the money is lost and the two players get nothing, while in the case the responder accepts the offer, the money is divided as decided by the proposer. The expected utility theory predicts that in order to maximize their outcomes, the proposer should offer the smallest amount possible, and that the responder should accept every offer without distinction (Von Neumann & Morgensen, 2007). However, a large literature shows that the great majority of UG players do not behave as predicted by this theory [START_REF] Camerer | Behavioral Game Theory: Experiments in Strategic Interaction[END_REF].

As for proposers, they offer on average about 40% of the total amount of money to responders (for a meta-analysis see [START_REF] Falk | A theory of reciprocity[END_REF][START_REF] Fehr | A theory of fairness, competition, and cooperation[END_REF][START_REF] Oosterbeek | Cultural differences in ultimatum game experiments: Evidence from a meta-analysis[END_REF]. According to some models, as proposers know that responders expect to be treated fairly, they feign to be altruistic to maximize the chances of acceptance and avoid the negative affective response triggered by a rejection [START_REF] Avrahami | Learning (not) to yield: An experimental study of evolving ultimatum game behavior[END_REF][START_REF] Kagel | Fairness in ultimatum games with asymmetric information and asymmetric payoffs[END_REF][START_REF] Nelissen | Fear and guilt in proposers: Using emotions to explain offers in ultimatum bargaining[END_REF] . Other models assume that proposers choose to offer fair shares because they anticipate the feelings of guilt they would suffer if they behaved selfishly (i.e., guilt aversion model; [START_REF] Battigalli | Guilt in games[END_REF][START_REF] Ketelaar | The effects of feelings of guilt on the behaviour of uncooperative individuals in repeated social bargaining games: An affect-as-information interpretation of the role of emotion in social interdecision[END_REF][START_REF] Nelissen | Fear and guilt in proposers: Using emotions to explain offers in ultimatum bargaining[END_REF]. Furthermore, the literature suggest that the proposers' behavior can strongly vary from one individual to another [START_REF] Baumeister | Guilt: an interpersonal approach[END_REF]Morishima et al., 2013) and as a function of the responder's identity (e.g., [START_REF] Fabre | The responders' gender stereotypes modulate the strategic decision-making of proposers playing the ultimatum game[END_REF].

With regard to responders, the literature shows that they tend to adopt ready-to-go responses based on internal heuristics (i.e., an easy to implement short cut "rules of thumb"; [START_REF] Civai | Rejecting unfairness: emotion-driven reaction or cognitive heuristic[END_REF], consisting in almost always accepting fair shares and rejecting low shares (i.e., 20% of the amount or less; [START_REF] Güth | An Experimental Analysis of Ultimatum Bargaining[END_REF][START_REF] Camerer | Behavioral Economics: Reunifying Psychology and Economics[END_REF][START_REF] Camerer | Behavioral Game Theory: Experiments in Strategic Interaction[END_REF][START_REF] Sanfey | Expectations and social decision-making: biasing effects of prior knowledge on Ultimatum responses[END_REF]. Receiving an unfair share triggers a negative affective response (e.g., anger, disappointment, frustration; [START_REF] Koenigs | Irrational economic decision-making after ventromedial prefrontal damage: evidence from the Ultimatum Game[END_REF][START_REF] Pillutla | Unfairness, anger, and spite: Emotional rejections of ultimatum offers[END_REF][START_REF] Sanfey | The neural basis of economic decision-making in the ultimatum game[END_REF][START_REF] Van't Wout | Affective state and decision-making in the ultimatum game[END_REF] and responders can react to it in two different ways. First, they can choose to punish the proposer and reject the unfair offer [START_REF] Gabay | The Ultimatum Game and the brain: A meta-analysis of neuroimaging studies[END_REF]. Second, if they are sufficiently motivated and are able to recruit enough cognitive resources, responders can engage in the reappraisal (i.e., "a cognitive change involving the reinterpretation of an event's meaning to alter its emotional impact"; [START_REF] Gross | The emerging field of emotion regulation: An integrative review[END_REF] of the negative affective response to unfairness, which increases responders' likelihood of accepting the unfair share (e.g., [START_REF] Grecucci | Reappraising the ultimatum: an fMRI study of emotion regulation and decision making[END_REF][START_REF] Van't Wout | The influence of emotion regulation on social interactive decision-making[END_REF]. As for proposers, the behavior of responders can strongly vary from one individual to another [START_REF] Camerer | Behavioral Game Theory: Experiments in Strategic Interaction[END_REF][START_REF] Knoch | A neural marker of costly punishment behavior[END_REF][START_REF] Oosterbeek | Cultural differences in ultimatum game experiments: Evidence from a meta-analysis[END_REF] and according to the proposer's identity (e.g., [START_REF] Fabre | Sex and the money-how gender stereotypes modulate economic decision-making: an ERP study[END_REF].

Framing the Ultimatum Game

Offer framing manipulations

Three studies have investigated the impact of offer frame manipulations on the responders' decisions [START_REF] Fabre | Investigating the impact of offer frame manipulations on responders playing the ultimatum game[END_REF][START_REF] Sarlo | Framing the ultimatum game: gender differences and autonomic responses[END_REF][START_REF] Tomasino | Framing the ultimatum game: the contribution of simulation[END_REF]. In these experiments, the offers were framed either in a positive way with the focus being put on the money received by the participants (e.g., "the proposer gives you"), or in a negative way highlighting the money removed from the latter (e.g., "the proposer keeps"). In these three studies, greater negative affective responses (i.e., cardiac and brain activity) to unfair offers were found in the negative frame than in the positive frame. However, a framing effect was found at a behavioral level in only one of these studies [START_REF] Sarlo | Framing the ultimatum game: gender differences and autonomic responses[END_REF]) -with male participants, but not female ones, rejecting more frequently mid-value offers (i.e., €3 out of €10) in the negative frame.

Give/take decision framing manipulations

Another type of framing manipulation can be conducted on the UG. It consists in manipulating the way decisions are framed and is referred as decision frame manipulations (e.g., [START_REF] Eriksson | Costly punishment in the ultimatum game evokes moral concern, in particular when framed as payoff reduction[END_REF][START_REF] Leliveld | Initial ownership in bargaining: Introducing the giving, splitting, and taking ultimatum bargaining game[END_REF] . In the study of Leliveld and colleagues (2008), participants played as proposers to three variants of the UG: the Splitting-UG, the Taking-UG and the Giving-UG. In the Splitting-UG, the chips were located in between the two players and participants were asked to decide how much money the responder would get.

In the Taking-UG, the chips were located at the responder's side and asked how much money they wanted to take from the responder. In the Giving-UG, the chips were located at participant's side and the latter were asked how much money they wanted to give to the responder. Participants offered significantly higher shares to the responders in the Taking-UG than in both the Splitting-and the Giving-UGs, and in the Splitting-UG than in the Giving-UG. In this experiment, the decision framing manipulations were used to highlight the initial ownership of the amount of money, making it impossible to disentangle the effects of the decision frame and the initial ownership of the money [START_REF] Van Dijk | Decision-induced focusing in social dilemmas: Give-some, keep-some, take-some, and leave-some dilemmas[END_REF][START_REF] Zhao | From windfall sharing to property ownership: Prosocial personality traits in giving and taking dictator games[END_REF] and therefore to conclude on the impact of decision frames alone on the proposers' decision-making.

Accept/reject framing manipulations

Two studies investigated the impact of decision framing manipulations on responders [START_REF] Eriksson | Costly punishment in the ultimatum game evokes moral concern, in particular when framed as payoff reduction[END_REF][START_REF] Fabre | Investigating the impact of offer frame manipulations on responders playing the ultimatum game[END_REF]. In the study of Eriksson and colleagues (2017 ), participants played a one-shot UG as responders in which they were offered $25 out of $100 by the proposer. Participants playing in the rejection condition were told that they could either accept or reject this offer, while participants playing in the reduction condition were told that they could use the $25 they had earned to reduce the other player's payoff to zero. Greater rejection rates were found in the reduction frame than in the rejection frame. Similarly to the study of Leliveld and colleagues (2008) , the effects of the decision frame and the initial ownership of the money cannot be disentangled (i.e., in the reduction frame responders owned the money before making their decision while in the rejection frame they did not). In the study of Fabre and colleagues (2022; i.e., Experiment 3), a decision framing manipulation was used in addition to an offer framing manipulation. Participants had to indicate the amount of money they would accept versus reject (i.e., decision frame manipulation) to be given by the proposer versus the proposer to keep (i.e., offer framing manipulation). While the results revealed an offer framing effect in female responders, no decision framing effect was found.

The present study

To our knowledge, the impact of decision framing manipulations on UG players' decisions has never been properly investigated (i.e., testing one decision framing manipulation at a time without concomitantly manipulating the initial ownership of the money). The present study aimed at filling a gap in the framing effect literature, investigating the impact of simple decision frame manipulations on UG players. In Experiment 1, proposers were asked which offer(s) they would either give the responder or keep for themselves, and in Experiment 2 responders were asked which offer(s) they would either accept or reject from the proposer. In these two exploratory experiments, the amount of money was initially allocated to the proposer as this is usually the case in the UG [START_REF] Güth | Is it all about the self? The effect of self-control depletion on ultimatum game proposers[END_REF].

EXPERIMENT 1

Experiment 1 aimed at investigating the impact of decision frame manipulations on proposers' decision behavior. Participants played a one-shot ultimatum game as proposer and were asked which offer(s) from €1 to €9 they would either keep for themselves or give to the responder. Making predictions regarding the results of Experiment 1 based on the literature investigating the impact of keep/take versus give/leave frame manipulation appears to be quite challenging, since the results of these studies tend to be inconsistent and mostly attributable to a difference in initial ownership of the money. According to the decisioninduced focusing proposed by [START_REF] Van Dijk | Decision-induced focusing in social dilemmas: Give-some, keep-some, take-some, and leave-some dilemmas[END_REF], a decision frame induces an initial focus on the decision that one is explicitly asked to make, which tends to make the implicit embedded option fade. Based on this model, we predicted that proposers might behave more generously in the give frame, resulting in a lower minimal offer (i.e., the lowest share they would offer) proposed by participants in the keep frame than in the give frame. As gender differences in response to framing manipulations were found in some UG studies [START_REF] Fabre | Investigating the impact of offer frame manipulations on responders playing the ultimatum game[END_REF][START_REF] Sarlo | Framing the ultimatum game: gender differences and autonomic responses[END_REF], we also investigated whether participants reacted diversely to the decision frame manipulations as a function of their biological gender. As for experiment 1, the discrepancy in the results of previous framing effect studies did not allow us to make specific predictions on the way participants' gender would impact their reaction to decision frame manipulations.

2.1.

Material and Methods

Participants

Bujang et colleagues ( 2018) demonstrated that two rules of thumb can be used to calculate the minimal sample size for logistical regressions. While 500+ participants allow to properly derive the statistics representing the parameters, the sample size can also be estimated using the following formula n = 100 + 50i, where n refers to the sample size and i refers to number of independent variables in the final model. We calculated that around 200 participants would be needed to investigate the effect of both frame and participants' gender.

We collected as much data as possible during the given period of two months and were eventually able to recruit 400 French participants (200 females; mean age: 29 ± 12 years) via social media (i.e., mainly Facebook). They received no compensation for their participation in the study.

Ethics statement

This study was carried out in accordance with both the Declaration of Helsinki and the recommendations of the Research Ethics Committee of the University of XXX in XXX (CER n° 2023-690). All participants were informed of their rights and gave written informed consent.

Procedure

A website hosted by the University was created to conduct the present on-line experiments, allowing the protection of participants' personal data. The link to the experiment (i.e., questionnaire form) was shared on different social media. When clicking on the link, participants were directed to the first page of the questionnaire. They were informed that the experiment would last less than three minutes and that they should click on the "participate" icon to continue to start the experiment. After they clicked on the icon, they were redirected to the second page of the questionnaire that presented the instructions. Participants were asked to attentively read the instructions before they started the experiment. They were explained that no IP address would be collected to guarantee the respect of their anonymity and kindly requested to participate in the experiment only once. They were informed that they were free to leave the experiment at any time (i.e., incomplete responses would not be accounted for)

and that once they had clicked on the "finalize" icon, they would no longer have the possibility to modify their response. They were informed that they could click on the "contact" icon to contact the researchers in charge of the experiment and communicate any information they wanted. By clicking a second time on the icon "participate" they acknowledged that they had read and understood the instructions and accepted the terms of the experiment. On the third website page, the ultimatum game statement was presented as follows: "You are about to play a game called ultimatum game. In this game, a proposer is given a fixed amount of money (i.e., €10) and has to choose how to divide it with a second player called responder. The responder can either accept the division, in which case the amount of money gets divided as proposed by the proposer, or reject it, in which case neither of the two gets any money". For the 200 participants (100 females) who were tested in the keep decision frame, the final sentence of the problem was: "If you were playing as proposer, which amount(s) of money would you keep for yourself"; while for the remaining 200 participants (100 females) who were tested in the give decision frame: "If you were playing as proposer which amount(s) of money would you give to the responder". Participants' task was to select the icon(s) corresponding to the amount(s) of money they wanted to keep for themselves versus give to the responder (i.e., €1, €2, €3, €4, €5, €6, €7, €8, €9) and to click on the icon "Finalize" to validate their choice and complete the experiment, after providing their age and gender information.

Statistical analysis

The offers were assessed in terms of minimal offer proposed to the responder. In the give frame, the minimal offer proposed was the lowest offer selected by participants. In the keep decision frame, the minimal offer proposed was computed by subtracting the highest offer kept by the participant from €10. A 2 x 2 (Decision Frame [keep, give] x Participants' Gender [male, female]) ordinal logistic regression was performed on the minimal offer proposed (i.e., €1, €2, €3, €4, €5, €6, €7, €8, €9) in IBM SPSS Statistics 26 ©. A manual stepwise analysis was performed to remove non-significant interactions from the model.

Results

The analysis revealed a main effect of decision frame [B (SE) = -.501 (.193), CI (95%) = (-.879, -.123), Wald χ² (1) = 6.758, p = .009; see Figure 1 A Insert Figure 1 here

Discussion

The present experiment aimed at investigating the impact of decision frame manipulations on the decision behavior of proposers playing the UG. Participants were asked to indicate either how much money they wanted to keep for themselves or give to the responder. We predicted that the give decision frame would make proposers behave in a more generous manner than the keep decision frame. However, we found the opposite pattern of results, with proposers offering a higher minimal offer in the keep frame than in the give frame. Compared to the give frame, the keep frame places greater focus on the amount of money retained by the proposers and might more strongly highlight proposers' unfair behaviour (i.e., offering unfair offers). As stated earlier, proposers anticipate responders' reactions and adapt their offer to maximize the chances of acceptance [START_REF] Avrahami | Learning (not) to yield: An experimental study of evolving ultimatum game behavior[END_REF][START_REF] Kagel | Fairness in ultimatum games with asymmetric information and asymmetric payoffs[END_REF][START_REF] Nelissen | Fear and guilt in proposers: Using emotions to explain offers in ultimatum bargaining[END_REF] . The higher minimal offer proposed by participants playing in the keep frame compared to those playing in the give frame appears to reflect proposers strategically adjusting their offers to enhance the probability of responders accepting them.

EXPERIMENT 2

Experiment 2 aimed at investigating the impact of decision frame manipulations on the responders playing a one-shot UG. In this on-line experiment, participants were asked to indicate which amount(s) of money, from €1 to €9, they would either accept or reject. The results of the previous studies investigating the impact of accept/reject framing manipulations are quite contradictory and do not allow to reliably predict the results of the present experiment. As for Experiment 1 and based on the concept of decision-induced focusing [START_REF] Van Dijk | Decision-induced focusing in social dilemmas: Give-some, keep-some, take-some, and leave-some dilemmas[END_REF] , we predicted that the accept/reject frame manipulation would modulate participants' initial focus and result in a difference in minimal acceptable offer (i.e., the lowest share they would accept), with a higher minimal acceptable offer observed in the reject decision frame than in the accept decision frame. We also investigated the impact of the participants' gender, but made no specific predictions due to the discrepancy in the results of previous studies [START_REF] Fabre | Investigating the impact of offer frame manipulations on responders playing the ultimatum game[END_REF][START_REF] Sarlo | Framing the ultimatum game: gender differences and autonomic responses[END_REF].

Material and Methods

Participants

Based on the formula of Bujang and colleagues (2018; see section 2.1. for further information), we calculated that similarly to Experiment 1, around 200 participants would be needed to investigate the effect of both frame and participants' gender. We collected as much data as possible during the given period of two months and were eventually able to recruit 188

French participants (91 females; mean age: 26 years ± 8) via advertisements published on social media. They received no compensation for their participation in the study. These participants did not participate in Experiment 1.

Ethics statement

This study was carried out in accordance with both the Declaration of Helsinki and the recommendations of the Research Ethics Committee of the University of XXX in XXX (CER n° 2023-690). All participants were informed of their rights and gave written informed consent.

Procedure

The experimental procedure was the same as Experiment 1 until participants were presented with the third website page. On the third website page, the UG statement was presented in the same way as Experiment 1, except for the last sentence. For 100 of the participants (48 females), the final sentence of the problem was: "If you were playing as responder, which amount(s) of money would you accept?"; while for the other 88 participants (43 females) the final sentence was: "If you were playing as responder, which amount(s) of money would you reject?". The participants' task was to select the icon(s) corresponding to the amount(s) of money they would accept versus reject (i.e., €1, €2, €3, €4, €5, €6, €7, €8, €9) and to click on the icon "Finalize" to validate their choice and complete the experiment after providing their age and biological gender. On the last page, they were thanked for taking part to the study and kindly asked to participate in the study only once.

Statistical analysis

The offers were assessed in terms of the minimal acceptable offer (i.e., the lowest offer the responders would accept) in both frames. In the accept frame, the minimal acceptable offer was the lowest offer selected by the participants. In the reject frame, the minimal acceptable offer was computed by adding €1 to the highest offer rejected by participants. In the reject frame, when participants selected none of the offer, it meant that their minimal acceptable offer was €1. A 2 x 2 (Decision Frame [accept, reject] x Participants' Gender [male, female]) ordinal logistic regression was performed on the minimal acceptable offer (i.e., €1, €2, €3, €4, €5, €6, €7, €8, €9) in IBM SPSS Statistics 26 ©. A manual stepwise analysis was performed to remove non-significant interaction from the model.

Results

The analysis revealed a main effect of decision frame [B (SE) = -.683 (.273), CI (95%) = (-1.219, -.147), Wald χ² (1) = 6.241, p = .012; see Figure 2 A Frame interaction from the model are reported in the Supplementary (see Experiment 2 section).

Insert Figure 2 here

Discussion

The aim of Experiment 2 was to investigate the impact of decision frame manipulations on responders' decision-making. Participants were asked to indicate which amount(s) of money, from €1 to €9, they would either accept or reject. In line with our predictions and the concept of decision-induced focusing [START_REF] Van Dijk | Decision-induced focusing in social dilemmas: Give-some, keep-some, take-some, and leave-some dilemmas[END_REF] , responders asked for a lower minimal acceptable offer in the accept decision frame than in the reject decision frame. In other words, participants were more inclined to accept unfair offers in the accept decision frame than in the reject decision frame.

In the UG, responders can adopt two different strategies [START_REF] Blount | When social outcomes aren′ t fair: The effect of causal attributions on preferences[END_REF][START_REF] Camerer | Behavioral Game Theory: Experiments in Strategic Interaction[END_REF][START_REF] Gabay | The Ultimatum Game and the brain: A meta-analysis of neuroimaging studies[END_REF] . In the case they are more concerned by fairness, responders tend to reject unequal offers to punish the proposer for behaving unfairly. While when their major concern is to maximize their gain, responders tend to accept unfair offers. Compared to the accept frame, the reject frame appears to have enhanced participants' motivation to punish unfairness, resulting in a higher minimal acceptable offer in the reject frame than in the accept frame. In other words, participants' balance of concerns tipped more towards fairness in the reject frame and more towards gain maximization in the accept frame.

GENERAL DISCUSSION

To our knowledge, the present study is the first to investigate the impact of decision frame manipulations on the decision behavior of UG players. In Experiment 1, participants played as proposers and were asked to indicate the amount(s) of money (from €1 to €9) they would either give to the responder or keep for themselves, whereas in Experiment 2 participants played as responders and were asked to indicate which offer(s) they would either accept or reject.

The results of Experiment 1 revealed a significant decision framing effect. Compared to the give frame, the keep frame places greater focus on the amount of money retained by the proposers and therefore might more strongly highlight proposers' unfair behaviour (i.e., offering unfair offers). Proposers who anticipate responders' reactions to maximize the chances of acceptance, appear to have strategically adapted their offers to the frame, with proposers playing in the keep frame offering a higher minimal offer than proposers playing in the give frame [START_REF] Avrahami | Learning (not) to yield: An experimental study of evolving ultimatum game behavior[END_REF][START_REF] Kagel | Fairness in ultimatum games with asymmetric information and asymmetric payoffs[END_REF][START_REF] Nelissen | Fear and guilt in proposers: Using emotions to explain offers in ultimatum bargaining[END_REF] .

The results of Experiment 2 also revealed a significant decision framing effect, with responders asking for a higher minimal acceptable offer in the reject than in the accept frame.

The accept/reject frame manipulation appears to have modulated responders' balance of concerns (i.e., maximizing their gains versus punishing unfairness), with a greater interest in maximizing gains in the accept frame and in punishing unfairness in the reject frame.

The present study was exploratory and only aimed at investigating whether decision framing effects could be found in UG players. Further research is therefore needed to test whether these results are replicated and to investigate the psychological mechanisms underlying such decision framing effects. Because framing effects tend to be small, elusive and are likely to vanish when repeated-measure paradigms are used (e.g., [START_REF] Amsalem | Real, but limited: A meta-analytic assessment of framing effects in the political domain[END_REF][START_REF] Fabre | Investigating the impact of offer frame manipulations on responders playing the ultimatum game[END_REF][START_REF] Gong | The framing effect in medical decision-making: a review of the literature[END_REF], we chose to use a one-shot UG and to limit as much as possible the number of manipulated factors in the present study. In the case decision framing effects are also found in repeated-measure UGs, the latter paradigm could be used to investigate the affective and cognitive processes underpinning UG players' decisions as a function of the decision frame (e.g., cardiac, ocular and/or brain correlates; [START_REF] Chen | Role of accentuation in the selection/rejection task framing effect[END_REF][START_REF] Fabre | Investigating the impact of offer frame manipulations on responders playing the ultimatum game[END_REF][START_REF] Sarlo | Framing the ultimatum game: gender differences and autonomic responses[END_REF][START_REF] Tomasino | Framing the ultimatum game: the contribution of simulation[END_REF].

Overall, we predict that the give/keep and the accept/reject decision frames will be associated with different affective charge and/or cognitive effort [START_REF] Chen | Role of accentuation in the selection/rejection task framing effect[END_REF]Sokolova & Krisna, 2016). Regarding the keep/give frame manipulation, we predict that the proposers' increased strategic concerns in the give frame would motivate them to engage in a greater cognitive effort to maximize their gains and estimate the lowest share responders might accept, resulting in longer decision times in the give than in the keep frame [START_REF] Avrahami | Learning (not) to yield: An experimental study of evolving ultimatum game behavior[END_REF][START_REF] Kagel | Fairness in ultimatum games with asymmetric information and asymmetric payoffs[END_REF][START_REF] Nelissen | Fear and guilt in proposers: Using emotions to explain offers in ultimatum bargaining[END_REF] . We also predict that a difference in affective response as a function of the frame will be observed, with a greater fear of seeing the offer rejected in the keep frame than in the give frame [START_REF] Nelissen | Fear and guilt in proposers: Using emotions to explain offers in ultimatum bargaining[END_REF].

Regarding the accept/reject decision frame manipulation, we predict that unfair offers might trigger a stronger negative affective reaction in the reject frame than in the accept frame (in line with [START_REF] Fabre | Investigating the impact of offer frame manipulations on responders playing the ultimatum game[END_REF][START_REF] Sarlo | Framing the ultimatum game: gender differences and autonomic responses[END_REF][START_REF] Tomasino | Framing the ultimatum game: the contribution of simulation[END_REF]. We also predict that responders' greater motivation to maximize their gains in the accept frame would be associated with a greater cognitive effort to accept unfair offers in the accept frame than in the reject frame, resulting in longer decision times in the accept frame; [START_REF] Fabre | Investigating the impact of offer frame manipulations on responders playing the ultimatum game[END_REF].

Limitations

In the present study, participants were only asked to imagine how much money they would either offer or accept, and no real economic incentive was used. Therefore, further research is necessary to confirm that decision manipulations also affect UG players when a real incentive is used. It is very likely that similar results will be found since UG players were found to behave similarly (at least in the first round of the game) when they were playing with a real incentive and when they were not [START_REF] Gillis | Hypothetical and real incentives in the ultimatum game and Andreoni's public goods game: an experimental study[END_REF].

Conclusion

The present study demonstrates that decision frame manipulations modulate UG players' decision-making. Further investigation is necessary to test whether these results can be replicated and to assess the processes underpinning decision framing effects. Beyond this, we believe that understanding how decision framing manipulations work may be useful in several areas, such as nudging generosity in fundraising campaign (e.g., [START_REF] Bhati | A literature review of experimental studies in fundraising[END_REF] or improving tax compliance [START_REF] Dimant | Requiem for a nudge: Framing effects in nudging honesty[END_REF].

Figure Captions

  & B] with the keep decision frame predicting for a higher minimal offer from the proposers (M = 4.82€) than the give decision frame (M = 4.57€). The main effect of participants' gender did not reach significance [B (SE) = .324 (.191), CI 95% = (-.051, .699), Wald χ² (1) = 2.865, p = .091]. The statistical results prior the removal of the non-significant Participants' Gender x Decision Frame interaction from the model are reported in the Supplementary materials (see Experiment 1 section).

  & B] with the "accept" decision frame predicting acceptance of a lower minimal acceptable offer (M = 3.35€) than the "reject" decision frame (M = 3.93€). The main effect of participants' gender did not reach significance [B (SE) = -.184 (.271), CI (95%) = (-.715, .348), Wald χ² (1) = .460, p = .498]. The statistical results prior the removal of the non-significant Participants' Gender x Decision

Figure 1 .

 1 Figure 1. Illustrations of A) the frequency of the offers, and B) the mean offer proposed to the responder in the keep decision frame (dark grey) and the give decision frame (light grey).

Figure 2 .

 2 Figure 2. Illustrations of A) the distribution of the minimal acceptable offers, and B) the minimal acceptable mean offer in the accept decision frame (dark grey) and the reject decision frame (light grey).

  Figure 1.

Figure 2 .

 2 Figure 2.

The present research has been funded by the European Community's Seventh Framework Program (FP7/2007-2013) under grant agreement n° 237907. We would like to thank Vincent Bonnemain for his help with the data collection.


Franklin Camacho
email: fcamacho@yachaytech.edu.ec

Rigoberto Fonseca-Delgado

Ramón Pino Pérez
email: pinoperez@cril.fr

Guido Tapia
email: guido.tapia@yachaytech.edu.ec

Generalized binary utility functions and fair allocations

Keywords: Allocation of indivisible goods/chores, envy-free up to one good/chore, efficiency, additive utility function

The problem of finding envy-free allocations of indivisible goods cannot always be solved; therefore, it is common to study some relaxations such as envy-free up to one good (EF1) and envy-free up to any positively valued good (EFX). Another property of interest for the efficiency of an allocation is the Pareto Optimality (PO). Under additive utility functions for goods, it is possible to find EF1 and PO allocations using the Nash social welfare. However, finding an allocation that maximizes the Nash social welfare is a computationally costly problem. Maximizing the utilitarian social welfare subject to EF1 constraints is an NP-complete problem for the case where three or more agents participate. In this work, we propose a restricted case of additive utility functions called generalized binary utility functions. The proposed utilities are a generalization of binary and identical utilities simultaneously. In this scenario, we present a polynomial-time algorithm that maximizes the utilitarian social welfare and, at the same time, produces an EF1 and PO allocation for goods as well as for chores. Moreover, a slight modification of our algorithm gives a better allocation: one which is EFX.

Introduction

The resource allocation problem has been widely studied in mathematics and economics for almost a century, [START_REF] Steinhaus | The problem of fair division[END_REF][START_REF] Steinhaus | Sur la division pragmatique[END_REF][START_REF] Nash | The bargaining problem[END_REF][START_REF] Aziz | Fair allocation of combinations of indivisible goods and chores[END_REF][START_REF] Caragiannis | The unreasonable fairness of maximum nash welfare[END_REF][START_REF] Camacho | Asignación de recursos con eficiencia y justicia débil en el bienestar social utilitario[END_REF]. The main elements in the problem are agents and resources. The goal is to distribute (or allocate) the resources among the agents in a "good manner." The agents can represent individuals, objects, government institutions, among others, depending on the application. The set of resources or goods to be distributed can be divisible or indivisible. In general, these sets are considered finite. In this work, we study the problem of allocating indivisible resources among a group of agents, with the aim of satisfying both the group and each individual in the best possible way.

This topic has many applications, for instance in solving divorce disputes, dividing an inheritance, sharing apartment rents, or even assigning household chores. In the last decade, there has been a considerable interest in the computational aspects of this problem. In particular, in Artificial Intelligence and more specifically in MultiAgent Systems, these problems are studied and renamed MultiAgent Resource Allocations (MARA) problems [START_REF] Aziz | Optimal reallocation under additive and ordinal preferences[END_REF][START_REF] Chevaleyre | Distributed fair allocation of indivisible goods[END_REF].

Finding a correct distribution of resources consists of distributing all the resources among the agents fairly and efficiently. To establish efficiency and some criterion of fairness, it is necessary to consider the preferences that each agent has over resources. In general, these preferences over resources are established through additive utility functions.

Traditionally, fairness is established through properties such as envy-freeness or proportionality. However, there are situations where it is impossible to find allocations that meet any of these properties. Thus, other weaker versions of fairness, such as envy-free up to one good [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF] or proportionality up to one good [START_REF] Conitzer | Fair public decision making[END_REF] are considered. Although there are results that, under certain conditions, guarantee the existence of allocations with some fairness property (see [START_REF] Caragiannis | The unreasonable fairness of maximum nash welfare[END_REF]), finding them is a computationally complicated problem [START_REF] De Keijzer | On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences[END_REF]. Just considering fairness may not be enough, because it could imply loss in group satisfaction.

Efficiency, also known as Pareto efficiency or Pareto optimality, is related to the group satisfaction by an allocation. One way to find efficient allocations is through social welfare functions. Caragianis et al, [START_REF] Caragiannis | The unreasonable fairness of maximum nash welfare[END_REF], showed that, under additive utility functions for goods, it is always possible to find an allocation that is Pareto optimal and envy-free up to one good. Actually, they prove that some of the allocations that maximize the Nash social welfare are Pareto optimal and envy-free up to one good. Unfortunately, finding allocations which maximize the Nash welfare is also an NP-hard problem [START_REF] Ramezani | Nash social welfare in multiagent resource allocation[END_REF] (see also [START_REF] Aziz | Optimal reallocation under additive and ordinal preferences[END_REF]).

Searching allocations which maximize the utilitarian social welfare is in general a more tractable problem from the computational point of view and, because of that, commonly used. A well-known result is that, under additive utility functions, allocations that maximize this social welfare are Pareto optimal (see Theorem 1), although the converse is not true. Moreover, allocations that maximize this social welfare do not always satisfy fairness properties. In Example 2, an allocation that is Pareto optimal and does not maximize utilitarian social welfare is proposed; besides, we find, in this example, that no allocation that maximizes utilitarian social welfare is envy free up to one good.

When we consider additive utility functions, it is possible to define a procedure that allows to find all the allocations which maximize utilitarian social wel-fare, see [START_REF] Camacho | Asignación de recursos con eficiencia y justicia débil en el bienestar social utilitario[END_REF]. Moreover, finding these allocations is a computationally tractable problem. Actually, in this work we propose a very simple algorithm in polynomial time, for scenarios of additive utilities, that finds an allocation which maximizes the utilitarian social welfare for goods as well as for chores.

Unlike the allocations that maximize the Nash social welfare which are EF1, the allocations that maximize the utilitarian social welfare are not, in general, EF1. Moreover, there are additive scenarios in which the property EF1 fails for every allocation which maximizes the utilitarian social welfare (see Example 2). Indeed, in this example we can see that Nash and utilitarian social welfares are independent.

Finding an allocation that maximizes the utilitarian social welfare and satisfies the EF1 criteria is an NP-complete problem when the number of agents is greater than or equal to three (see [START_REF] Aziz | Computing welfare-maximizing fair allocations of indivisible goods[END_REF]). However, for some specialized scenarios, there are very simple algorithms in polynomial time which find EF1, and even EFX allocations. That is the case of identical utilities (see Barman et al. [5]) and others like bivaluated utilities (Ebadian et al. [START_REF] Ebadian | How to fairly allocate easy and difficult chores[END_REF]) or binary utilities [START_REF] Barman | Greedy algorithms for maximizing nash social welfare[END_REF] (see Section 6).

In this work, we consider a class of additive functions, called generalized binary utility functions. This class is more general than the classes of binary and identical utilities. Intuitively, each resource has a market-price; each agent either does not want the resource at all, or wants it and values it by its market price. In the framework of these utility functions, the following results are established:

1. A characterization for Pareto optimal allocations (Theorem 3).

2. Each allocation that maximizes the Nash social welfare also maximizes the utilitarian social welfare (Theorem 4).

3. Constructive proofs of the existence of allocations which maximize the utilitarian social welfare, which are PO and respectively EF1 and EFX for goods and for chores. These allocations are obtained in polynomial time (Theorems 7 and 8).

Moreover, we propose a basic algorithm in O(nm) which finds, under additive utility functions, an allocation that maximizes the utilitarian social welfare (Theorem 6). The rest of this work is organized as follows. Section 2 introduces the concepts and problems studied in this paper. Section 3 is devoted to a characterization of Pareto Optimality in our particular scenarios. In Section 4, we propose a very simple and tractable algorithm for maximizing the utilitarian social welfare and we study its justice properties in the case of generalized binary utilities. In Section 5, we give a slight generalization of our generalized binary scenarios and prove that most of the results obtained in the previous sections don't hold for this new class of scenarios. Section 6 contains a comparison of our work with other works using specialized scenarios for tackling the problems of fairness and efficiency. We conclude in Section 7 with some final remarks. The proofs, our detailed algorithm and some detailed examples can be found in Appendix A.

Preliminaries

The set of agents is denoted by A = {1, . . . , n} and the set of resources is denoted by R = {r 1 , . . . , r m }. So, |R| = m and |A| = n. An allocation of resources is a function F : R -→ A. For each agent i, F -1 (i) = {r ∈ R : F (r) = i} is the set of resources (or bundle) assigned to i. The set of all possible allocations is denoted by A R . The number of possible allocations depends on n and m, given that |A R | = |A| |R| = n m . The set of all subsets of R is denoted by P(R). We consider two kinds of resources: goods and chores. Goods are resources that agents are supposed to accept and chores are resources that agents are supposed to reject. We will assume that either all resources are goods or all resources are chores.

The preference of agents over resources is established through utility functions which are additive, that is, functions of the type u : P(R) → R which satisfy:

• u(∅) = 0; • ∀S ∈ P(R) with S = ∅, u(S) = s∈S u({s}).
When the resources are goods, we always have ∀S ∈ P(R), u(S) ≥ 0. When the resources are chores, we always have ∀S ∈ P(R), u(S) ≤ 0. For each i ∈ A, u i denotes the additive utility function associated to i. For simplicity, u({s}) will be denoted by u(s). If every agent establishes an additive utility function in a problem of indivisible resource allocation, we say that it is an additive scenario. Definition 1. Assume that for each r k ∈ R we have a mapping r k → p k where p k is a real number different from 0. Let u be a function u : P(R) → R. We say that u is a generalized binary (g-binary for short) utility function if:

• u is an additive utility function;

• for every r k ∈ R, u(r k ) ∈ {0, p k }.
We say that we are in a goods (chores) g-binary scenario when all the resources are goods (chores) and every agent of the resource allocation problem has a utility function which is g-binary for the same mapping r k → p k .

Note that in case of goods (chores) p k can be viewed as the market-price (rejection intensity) of the resource r k . The value 0 does not change an agent's utility; in case of goods, this value can be interpreted as a reject, whereas in chores, it can be interpreted as a preference.

Clearly, if u is an additive utility function such that for each r k ∈ R, u(r k ) ∈ {0, 1}, then u is a g-binary utility function. This type of function is known as binary utility function, see [START_REF] Amanatidis | Maximum nash welfare and other stories about efx[END_REF]. Thus, the goods g-binary scenarios are a generalization of binary scenarios.

We assume that in goods and chores scenarios there is not a resource r such that for every agent i ∈ A, u i (r) = 0. Therefore, in a goods g-binary scenario, ∀r j ∈ R, max{u i (r j ) : i ∈ A} = p rj > 0 and min{u i (r) : i ∈ A} = 0.

While, in a chores g-binary scenario, ∀r j ∈ R, max{u i (r j ) : i ∈ A} = 0 and min{u i (r) : i ∈ A} = p rj < 0.

A goods g-binary scenario in which the value 0 is not taken by the utility functions is called a scenario of identical utility functions. These scenarios were considered by Barman et al. [START_REF] Barman | Greedy algorithms for maximizing nash social welfare[END_REF]. There are examples where imposing a scenario of identical utilities is not very adequate to find an allocation that best satisfies the agents. The following example shows such a situation. Example 1. Suppose there are two goods r 1 , r 2 and two agents 1, 2. Agent 1 wants r 1 and his utility for this good is p 1 , that is u 1 (r 1 ) = p 1 . Agent 1 does not want r 2 and his utility for this good is null, that is u 1 (r 2 ) = 0. For agent 2, it is all the contrary, more precisely: 2 wants r 2 and his utility for this good is p 2 , that is u 2 (r 2 ) = p 2 but 2 does not want r 1 and his utility for this good is null, that is u 2 (r 1 ) = 0. In such a g-binary scenario, it is clear that the best allocation corresponds to allocating r 1 to 1 and r 2 to 2. In a scenario with identical utilities the agents can't express that they are not interested in a good (utility 0). Thus the allocation which gives r 1 to 2 and r 2 to 1, in a scenario of identical utilities produces the same social utilitarian welfare but this allocation is far from satisfying the agents.

Note that the goods g-binary scenarios are a simplification of the Fisher market model in economy [START_REF] Brainard | How to compute equilibrium prices in 1891[END_REF].

Fairness, efficiency, and social welfare

An attractive fairness criterion in additive scenarios is the absence of envy. If no agent strictly prefers the bundle assigned to another agent instead of its own bundle, the allocation is envy-free. More precisely, an allocation F is envy-free (EF) if ∀i, j ∈ A, u i (F -1 (i)) ≥ u i (F -1 (j)). If there exists an agent i ∈ A such that u i (F -1 (i)) < u i (F -1 (j)) for some j ∈ A, then the agent i envies the agent j. The property EF is the most desirable property, but in a simple example of an indivisible resource with two agents it is impossible to find an allocation without envy. In the literature [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF][START_REF] Caragiannis | The unreasonable fairness of maximum nash welfare[END_REF][START_REF] Amanatidis | Maximum nash welfare and other stories about efx[END_REF][START_REF] Ebadian | How to fairly allocate easy and difficult chores[END_REF][START_REF] Ebadian | How to fairly allocate easy and difficult chores[END_REF], weaker versions of the envy free property can be found. The weakest among these is envy free up to one good. The following definition establishes the main weak envy free notions for goods and chores.

1 Definition 2. Let F be in A R , 1.
F is an envy-free up to one resource (EF1) allocation for goods if ∀i, j ∈ A, ∃g ∈ F -1 (j) such that

u i (F -1 (i)) ≥ u i (F -1 (j) \ {g}) (1)
2. F is an envy-free up to one resource (EF1) allocation for chores if ∀i, j ∈ A, ∃g ∈ F -1 (i) such that

u i (F -1 (i) \ {g}) ≥ u i (F -1 (j)) (2)
3. F is an envy-free up to any non zero valued resource (EFX) allocation for goods if ∀i, j ∈ A,

∀g ∈ F -1 (j) with u i (g) > 0, u i (F -1 (i)) ≥ u i (F -1 (j) \ {g}) (3)

F is an envy-free up to any non zero valued resource (EFX) allocation for chores

if ∀i, j ∈ A, ∀g ∈ F -1 (i) with u i (g) < 0, u i (F -1 (i) \ {g}) ≥ u i (F -1 (j)) (4)

5.

F is an envy-free up to any valued resource (EFX 0 ) allocation for

goods if ∀i, j ∈ A, ∀g ∈ F -1 (j), u i (F -1 (i)) ≥ u i (F -1 (j) \ {g}) (5)
6. F is an envy-free up to any valued resource (EFX 0 ) allocation for

chores if ∀i, j ∈ A, ∀g ∈ F -1 (i), u i (F -1 (i) \ {g}) ≥ u i (F -1 (j)) (6)
It is clear that in the case of additive utilities for goods or for chores we have:

EF ⇒ EF X 0 ⇒ EF X ⇒ EF 1
The efficiency, also known as Pareto efficiency or Pareto optimality, aims at characterizing when the allocation best satisfies the group. Remember that if F and G are allocations in A R , we say that F is Pareto dominated by G, when:

• ∀i ∈ A, u i (F -1 (i)) ≤ u i (G -1 (i)) and • ∃j ∈ A such that u j (F -1 (j)) < u j (G -1 (j))
We say that G is Pareto optimal (PO), if it is not Pareto dominated by another allocation.

One way to measure the social satisfaction of the agents is through the Nash and utilitarian social welfare functions. Let us recall their precise definitions. The utilitarian social welfare of F , denoted by SW u (F ), is defined by

SW u (F ) = i∈A u i (F -1 (i)) (7) we put M SW u = {F : SW u (F ) ≥ SW u (G), ∀G ∈ A R }.
The Nash social welfare, denoted by SW N ash (F ), is defined by

SW N ash (F ) = i∈A u i (F -1 (i)) (8)
we put M SW N ash = {F : SW N ash (F ) ≥ SW N ash (G), ∀G ∈ A R }.

A well-known result is that any allocation that maximizes utilitarian social welfare is PO:

Theorem 1. Under an additive scenario, let F be in A R , if F ∈ M SW u , then F is PO.
Although in general it is not always possible to find EF allocations, fortunately, Caragiannis and colleagues [START_REF] Caragiannis | The unreasonable fairness of maximum nash welfare[END_REF] showed that under an additive scenario for goods it is possible to find EF1 and PO resource allocations. Actually, they prove the following theorem: Theorem 2. [Caragianis et al. [START_REF] Caragiannis | The unreasonable fairness of maximum nash welfare[END_REF]] Under an additive scenario for goods, every allocation2 that maximizes Nash social welfare is EF1 and PO.

Note that, with the help of Theorem 2, it is easy to see that the converse of Theorem 1 is false. The following example shows this.

Example 2. Let R = {r 1 , r 2 } be the set of resources and A = {1, 2} the set of agents where each agent i establishes its utility function u i over every resource, according to Table 1. Let F and G be the allocations defined by Table 2.

r 1 r 2 F 1 1 G 2 1
The utility by bundle received by each agent and social welfare are showed in Table 3.

1 2 SW u SW N ash u i (F -1 (i)) 20 0 20 0 u i (G -1 (i)) 10 3 13 30
It is easy to see that F is the only allocation which maximizes utilitarian social welfare. However, F is not EF 1 because agent 2 envies agent 1, u 2 (F -1 (2)) = 0 < 5 = u 2 (F -1 (1)), but even after removing r 1 or r 2 from (F -1 (1)), envy does not disappear:

u 2 (F -1 (2)) = 0 < 2 = u 2 (F -1 (1)\{r 1 }) and u 2 (F -1 (2)) = 0 < 3 = u 2 (F -1 (1)\{r 2 })
The maximum Nash social welfare is reached at 30, so G maximizes the Nash social welfare. By Theorem 2 G is EF 1, but it does not maximize the utilitarian social welfare. In the following table, we identify the properties that satisfy F and G; if an allocation satisfies a property we use and otherwise.

PO EF1 M SW u M SW N ash F G

A characterization of Pareto Optimality

The following theorem shows that under g-binary scenarios, the converse of Theorem 1 is satisfied; i.e., having the property PO and belonging to M SW u are equivalent.

Theorem 3. Assume a goods (chores) g-binary scenario and let F be an allocation in

A R . Then, F is PO if, and only if, F ∈ M SW u .
Note that, in general additive scenarios, Theorem 3 does not hold as Example 2 reveals.

We have seen in Example 2 that M SW N ash ⊆ M SW u . However, under goods g-binary scenarios, Theorems 2 and 3 together, tell us that M SW N ash ⊆ M SW u . This is important and will be stated in the following result. Theorem 4. Under a goods g-binary scenario, each allocation that maximizes Nash social welfare also maximizes utilitarian social welfare.

A straightforward corollary of Theorem 4 and Theorem 2, is the existence, under goods g-binary scenarios, of allocations maximizing the utilitarian social welfare and satisfying the EF1 property. The existence is based in finding an allocation producing a maximum Nash welfare, a hard problem from a computational point of view. In the next section we will see that in g-binary scenarios it is easy to compute allocations EF1 producing a maximal utilitarian welfare.

A simple Algorithm and its behavior in some additive scenarios

In this section, we propose a very natural and simple algorithm and we analyze its behavior in additive scenarios, in particular in g-binary scenarios.

Let us start with a key result in the conception of the algorithm. It establishes that an allocation distributes resources to the agents that maximize them if, and only if, this allocation maximizes the utilitarian social welfare. One can find a straightforward proof of this result3 , using a matrix approach, in [START_REF] Camacho | Asignación de recursos con eficiencia y justicia débil en el bienestar social utilitario[END_REF].

Theorem 5. Under an additive scenario, F ∈ M SW u if, and only if, ∀i ∈ A, ∀r ∈ F -1 (i) we have that u i (r) = max{u j (r) : j ∈ A}.

Suppose that in an additive scenario, R = {r 1 , . . . , r m } (all the resources are goods or all the resources are chores) and A = {1, . . . , n}. Let α 1 , . . . , α m be the real numbers defined in the following way: for each r k ∈ R, α k = max{u j (r k ) : j ∈ A}. Then, by the previous theorem the following simple algorithm defines an allocation, Γ, having a maximal utilitarian welfare, that is, Γ ∈ M SW u .

Algorithm 1: An allocation for maximal utilitarian welfare

Input: Two finite sets, R = {r 1 , . . . , r m } for the resources, A = {1, . . . , n} for the agents, and their respective utilities u i Output: The allocation Γ

1 v 0 ← (0, . . . , 0) 2 for k ← 1 to m do 3 α k ← max{u j (r k ) : j ∈ A} 4 P k ← {j ∈ A : u j (r k ) = α k } 5 l k ← min {|[v k-1 ] j | : j ∈ P k } 6 M k ← {i ∈ P k : |[v k-1 ] i | = l k } 7 j k ← min{M k } 8 Γ(r k ) ← j k 9 [v k ] i ← [v k-1 ] i + u j k (r k ), if i = j k [v k-1 ] i , if i = j k . for all i ∈ A 10 return Γ
The idea of Algorithm 1 is very simple: the resource r k is allocated to an agent who maximizes its utility and such that before this step, that is until the partial allocation of resources {r 1 , . . . , r k-1 } is done, he has the minimal utility in case of goods and the maximal utility in the case of chores. A detailed description of the behavior of this algorithm appears in the Appendix.

From Theorem 1 we have the following result:

Corollary 1. Under an additive scenario, Γ is P O.

We saw in Example 2 that the allocation F , the unique allocation that maximizes the utilitarian social welfare is not EF1 (see Table 4). But this allocation is indeed the allocation Γ, thus in general, Algorithm 1 does not produce an allocation EF1.

The following observation summarizes some facts in g-binary scenarios. This will be proved throughout Example 5 in Appendix A.

Remark 1.

It is important to note that in g-binary scenarios there are allocations EF1 which are not in M SW u . In those scenarios there are allocations which are P O and M SW u but they are neither EF1 nor belong to M SW N ash . Also in those scenarios Γ is EF1, PO, it is in M SW u but, in general, it is not in M SW N ash . It can happen that there exist allocations that are EF1, PO, and they are in both M SW u and in M SW N ash .

We have already said that Algorithm 1 produces a maximal utilitarian welfare. This occurs in case of additive scenarios and due to Theorem 5 and the definition of Algorithm 1. The next result summarizes this and gives the complexity of the algorithm.

Theorem 6. Under a goods (chores) additive scenario, Γ ∈ M SW u and it is obtained in O(nm) operations.

In addition to this, we will show next that in g-binary scenarios for goods and chores, the allocation Γ, given by Algorithm 1 is also envy-free up to one resource (good or chore).

Theorem 7. Under a g-binary scenario for goods or chores, the allocation Γ given by Algorithm 1 produces a maximal utilitarian welfare, is EF1 and PO. Its run time is O(mn).

As a matter of fact, in a g-binary scenario for chores, if for any resource r, max i∈A {u i (r)} = min i∈A {u i (r)} we have that Γ is EF. That is because, in such a case, Γ is an allocation in which all the agents give utility 0 to their bundles.

Moreover, with a very slight modification of Algorithm 1, we will obtain another allocation, Γ * , which is EFX. This modification consists in taking one more step: reordering the resources. In the case of goods we order the resources in decreasing order and in the case of chores we order the resources in increasing order according to the maximal absolute value of utilities given to resources. More precisely, a resource r precedes another resource r if max i∈A {|u i (r)|} ≥ max i∈A {|u i (r )|}. For this Γ * we have the following result.

Theorem 8. Under a g-binary scenario for goods or chores, the allocation Γ * given by Algorithm 1 modified as previously indicated maximizes the utilitarian social welfare, is EFX and PO. Moreover, its run time is O(m log m + mn).

It is interesting to observe that the algorithm producing Γ * is quite similar to Barman et al. algorithm [START_REF] Barman | Greedy algorithms for maximizing nash social welfare[END_REF] producing an allocation EFX, in the case of identical scenarios for goods. In fact, in identical scenarios, the notions EFX and EFX 0 coincide. This is not the case in g-binary scenarios. This can be viewed by building a g-binary scenario, in which Γ * , the allocation given by the modified Algorithm 1, which is EFX, is not EFX 0 (see Example 6 in Appendix A).

Note that if F is an allocation EF X for goods (for chores) such that for all i, j ∈ A such that u i (F -1 (i)) < u i (F -1 (j)) we have that F -1 (j) ⊆ {r ∈ R : u i (r) > 0} (F -1 (i) ⊆ {r ∈ R : u i (r) < 0}), then F is EF X 0 for goods (for chores).

Some limits of Algorithm 1

It is natural to ask if Algorithm 1 has other interesting properties. For instance, does it compute a maximal egalitarian welfare4 allocation? We will see in Example 3 that it is not the case even when we work in g-binary scenarios.

Another question concerns the properties of Algorithm 1 in a slight modification of g-binary scenarios. Remember that in g-binary scenarios, every Pareto efficient allocation indeed maximizes utilitarian social welfare (see Theorem 3), and as a consequence, in the case of goods, every assignment that maximizes Nash's social welfare also maximizes the utilitarian one (see Theorem 5). Thus, natural questions are: in these modified scenarios, is it possible to preserve these properties? Furthermore, does Algorithm 1 achieve fair allocations?

The following example shows that neither Γ nor Γ * maximize the egalitarian social welfare.

Example 3. There are three agents and three resources. The utilities are given in Table 5. In Table 6 are the allocations. In Table 7 appear the utilities of each agent for every allocation and the egalitarian social welfare denoted by SW e .

r 1 r 2 r 3 u 1 4 1 2 u 2 4 0 2 u 3 4 0 0 Table 6: Allocations. r 1 r 2 r 3 Γ 1 1 2 Γ * 1 1 2 A 3 1 2
are shown in table 9. This table shows also another allocation, namely the allocation G that assigns the resource r 3 to agent 3, who gives it a utility of .

r 1 r 2 r 3 F 1 1 1 1 F 2 2 1 1 F 3 3 1 1 G 2 1 3
Table 10 describes the valuations that the agents give to the received bundle in the different allocations of Table 9; also, it shows the Utilitarian and Nash social welfare of the allocations.

1 2 3 SW u SW N ash u i (F 1 -1 (i)) 2a + b 0 0 2a + b 0 u i (F 2 -1 (i)) 2a b 0 2a + b 0 u i (F 3 -1 (i)) 2a 0 b 2a + b 0 u i (G -1 (i)) a b a + b + ab
Note that allocation G has better Nash social welfare than F 1 , F 2 and F 3 . This is because the Nash social welfare of F 1 , F 2 and F 3 is 0 and the Nash social welfare of G is strictly positive. Then M SW u ∩ M SW N ash = ∅. Consequently, there are PO allocations that are not contained in M SW u ; and therefore, Theorem 3, instantiated in these scenarios, does not hold. Note that in this example Γ = Γ * = F 1 . But, regarding fairness, in allocations F 1 , F 2 , and F 3 , at least one agent does not receive any good, and at the same time, this agent values positively the two resources received by another agent. Then, it is not possible to eliminate the envy removing only one resource. Thus, in this scenario, the allocations which maximize utilitarian social welfare do not necessarily satisfy fairness. In particular, Algorithm 1 does not attain success in finding an allocation EF 1.

Related work

Due to the fact that allocations producing a maximal utilitarian welfare are, in additives scenarios, Pareto optimal, in order to assure the Pareto optimality and EF1, it is natural to look for allocations which are in M SW u and are simultaneously EF1. However, in general additive scenarios, the problem of finding allocations producing a maximal utilitarian social welfare being simultaneously EF1 is NP-hard [START_REF] Aziz | Computing welfare-maximizing fair allocations of indivisible goods[END_REF]. Thus, several works adopt the strategy of working in scenarios in which the utility functions are restricted. Next, we resume the main proposals studied in the literature, their results and the connections with our framework.

Actually, the work of Caragiannis et al. [START_REF] Caragiannis | The unreasonable fairness of maximum nash welfare[END_REF], under general goods additive scenarios shows that some special allocations producing maximum Nash social welfare are EF1 and PO. However, finding this kind of allocations is in general an NP-complete problem. Moreover, this does not solve the problem of finding an allocation that produces a maximal utilitarian social welfare and that is also EF1, because the allocations in M SW N ash are not necessarily in M SW u . However, in g-binary scenarios, we have M SW N ash ⊆ M SW u , because in these scenarios being Pareto optimal is equivalent to producing a maximal utilitarian welfare.

In the same vein, Amanatidis et al. [START_REF] Amanatidis | Maximum nash welfare and other stories about efx[END_REF] connect the maximum of Nash and EFX. They consider k-valued scenarios, that is, scenarios where there is a set of k distinct possible values, all real numbers, that agents can assign to their utilities. For 2-valued scenarios they prove that the allocations maximizing the Nash social welfare are EFX 0 . They also prove that for k-valuated scenarios, with k ≥ 3, it is not true that the allocations maximizing the Nash social welfare are EFX 0 . To the best of our knowledge, there is no known simultaneous existence of EFX and PO allocations under k-valued scenarios. Note that these scenarios are a generalization of -g-binary scenarios.

Actually, the 2-valued scenarios, called also bivaluated, are deeply studied by Ebadian et al. [START_REF] Ebadian | How to fairly allocate easy and difficult chores[END_REF]. They prove that for the case of chores, in that scenario, there exist polynomial time algorithms for calculating allocations which are simultaneously EF1 and PO. They studied also other fairness properties and other scenarios for which they prove the existence of allocations in polynomial time which are fair and PO. Note that the bivaluated scenario and the g-binary are independent.

A particular case of a bivaluated scenario is a binary scenario, where the utility functions can take only the values zero or one. In those scenarios, Barman et al. [START_REF] Barman | Greedy algorithms for maximizing nash social welfare[END_REF] proposed an algorithm to find an allocation that satisfies EFX and PO constraints and runs in polynomial time. Actually, they propose an algorithm that finds an allocation maximizing the Nash social welfare in polynomial time in the case of binary utilities. In the case of identical utilities, they propose also an algorithm in polynomial time to compute an allocation EFX which maximizes the utilitarian social welfare. They show also that this allocation is a good approximation of a maximum of Nash social welfare.

In Figure 1, we summarize the results of this discussion. The left branch in the figure goes from the most specialized scenario, the binary scenario, to the most general additive scenario passing through the bivaluated an k-valuated scenarios. The right branch goes from identical scenario, the most specialized in this branch, to additive scenarios (the most general) passing through the new scenarios we study in this work: g-binary and -g-binary scenarios.

We have noted that g-binary scenarios generalize simultaneously binary and identical scenarios and it is easy to see that -g-binary scenarios generalize bivaluated scenarios.

Concluding remarks

In this work, we have studied fair and efficient allocations for indivisible resources (goods and chores) when the valuations are defined through g-binary utility functions. We showed that there exists an allocation that is envy-free up to one item (EF1) (for goods and chores) and maximizes utilitarian social welfare (M SW u ) using g-binary utility functions. This result can be slightly modified to produce an allocation that is envy-free up to any item valuated different from zero (EFX) (for goods and chores). In this framework a characterization of Pareto optimality is given.

Actually, we build algorithms for finding allocations which are EF1, EFX and simultaneously M SW u (for goods and chores). They run in polynomial-time. However, the algorithm finding an allocation EF1 is computationally slightly better than the algorithm finding an allocation EFX.

The results of Section 5 show, in some way, that the g-binary scenarios are a sort of limiting scenario in which it is easy to provide EF1 and PO properties related to utilitarian social welfare. This is achieved by considering when a resource is indifferent to an agent. However, a little bit beyond that, the results do not hold.

It is known that finding allocations producing a maximum of Nash is NPhard even in identical scenarios (see [START_REF] Barman | Greedy algorithms for maximizing nash social welfare[END_REF]). Thus, in g-binary scenarios this problem will necessarily be NP-hard. Then, the natural question is if we can adapt the techniques of Barman et al. [START_REF] Barman | Greedy algorithms for maximizing nash social welfare[END_REF] in order to prove that Algorithm 1 produces a good approximation of a maximum of Nash social welfare in the case of g-binary scenarios.

initializing the vector of partial utilities v 0 with zeros, which has one position by each one of the n agents. This step demands O(n) operations. Step-2 allocates the m resources finding the agent with minimum partial utility in each iteration, following (A.2). Allocating m resources, finding the minimum of n agents demands O(nm) operations. In the next steps, the agent receives the resource in (A.3); for all the resources, this step and the updating of the vector of partial utilities runs in O(m). Building the resource allocation runs in O(max(n, nm, m)), thus, we have that the proposed algorithm is in O(nm).

In order to prove Theorem 7, we establish a technical lemma for goods or chores g-binary scenario. To establish this lemma we need the following definitions: Note that for every i, j we have

A ij = {r | u i (r) =
R = A ij ∪ B ij ∪ C ij ∪ D ij (A.4)
and this is a partition of R.

Lemma 1. Under a g-binary scenario for goods or chores, if Γ is computed via Algorithm 1, then for all i, j ∈ A we have that

u i Γ -1 (i) = u i Γ -1 (i) ∩ A ij + u i Γ -1 (i) ∩ C ij in goods g-binary scenario u i Γ -1 (i) ∩ R *
in chores g-binary scenario (A.5) and, Claim 1. For all i, j ∈ A,

u i Γ -1 (j) = u i Γ -1 (j) ∩ C ij in goods g-binary scenario u i Γ -1 (j) ∩ B ij + u i Γ -1 (j) ∩ R * in
1. A ij ∩ Γ -1 (j) = ∅ = B ij ∩ Γ -1 (i).
In fact, if r ∈ A ij ∩ Γ -1 (j), then Γ(r) = j ∈ M r and j ∈ m r which is a contradiction. So, A ij ∩ Γ -1 (j) = ∅. As B ij = A ji , then B ij ∩ Γ -1 (i) = ∅. Then, in Table A. [START_REF] Steinhaus | Sur la division pragmatique[END_REF] we show the utility assigned by each agent to its received bundle, and the social welfare in each allocation. which means that u 3 ({r 2 , r 5 , r 6 }) < u 3 ({r 5 , r 6 }).

Since Γ * was obtained using the modified Algorithm 1, we obtain that Γ * is EF X. Now we check that Γ * does not satisfy EF X 0 . Observe that Thus, property EF X 0 is not satisfied.

r 1 r 2 u 1 10 10 u 2 3 2

 2

Figure 1 :

 1 Figure 1: The boxes having a bold face framework represent the classes and results proposed in this work. The arrows show strict inclusion. Check marks ( ) denote the existence of fairness (EFX) and efficiency (PO) properties, while (?) denotes an open question.

  max{0, p r } ∧ u j (r) = min{0, p r }},B ij = {r | u i (r) = min{0, p r } ∧ u j (r) = max{0, p r }}, C ij = {r | u i (r) = max{0, p r } = u j (r)}, D ij = {r | u i (r) = min{0, p r } = u j (r)}, R * = {r | u i (r) = min{0, p r }, ∀i ∈ A}.

chores g-binary scenario (A. 6 )

 6 Proof: For each r ∈ R, we consider M r = {k ∈ A : u k (r) = max{0, p r }} and m r = {k ∈ A : u k (r) = min{0, p r }}. Note that, M r ∩ m r = ∅ and M r ∪ m r = A.Moreover, by definition of Γ, if M r = ∅, then Γ(r) ∈ M r .

1 2 3

 3 SW U SW N ash u i (Γ * -1 (i)) 30 30 15 75 13500 Notice that agent 3 envies agent 2 because u 3 ({r 2 , r 5 , r 6 }) = 15 u 3 ({r 5 , r 6 }) = 19

u 3 (

 3 {r 5 , r 6 }\{r 5 }) = 19 given that u 3 ({r 5 }) = 0 so, it follows that u 3 ({r 2 , r 5 , r 6 }) = 15 < 19 = u 3 ({r 5 , r 6 }\{r 5 }) (A.21)

Table 1 :

 1 Utility functions.

Table 2 :

 2 Allocations.

Table 3 :

 3 Utility by bundle received and social welfare.

Table 4 :

 4 Identification of properties (within a non g-binary scenario).

Table 5 :

 5 Utility functions.

Table 9 :

 9 Definition of allocations.

Table 10 :

 10 Utility by received bundle and social welfare.

Table A .

 A 17: Allocation Γ * r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8

	Γ * 1	3	1	3	2	2	3	3

Table A .

 A 18: Utility by received bundle and social welfare.

Actually, one can give a unified and more compact definition but it is clearer if we split it into two cases: goods and chores.

Actually, the Theorem as stated is true when the maximum Nash social welfare is strictly positive. When it is zero, it is necessary to impose that the set of agents having a good is a maximal set (see[START_REF] Caragiannis | The unreasonable fairness of maximum nash welfare[END_REF]).

Actually, in[START_REF] Camacho | Asignación de recursos con eficiencia y justicia débil en el bienestar social utilitario[END_REF] the if is proved. The only if is obvious.

The egalitarian social welfare of an allocation F , denoted by SWe(F ) is defined by SWe(F ) = min{u i (F -1 (i)) : i ∈ A}.

Note that if rs = r 1 , then {r 1 , . . . , r s-1 } = ∅

Acknowledgements

The first, second and fourth authors thank the Vice Chancellery of Research and Innovation of Yachay Tech University which has partially funded this work through the Social Welfare and Justice in Decision Making project code MATH22-08.

The third author has benefited from the support of the AI Chair BE4musIA of the French National Research Agency (ANR-20-CHIA-0028) and has also been partially funded by the program PAUSE of Collège de France.

Thanks to the referees whose observations have greatly helped to improve the results of this work and its presentation. We also thank Professor Olga Porras for her careful proof reading.

1 2 3 SW e u i (Γ -1 (i)) 5 2 0 0 u i (Γ * -1 (i)) 5 2 0 0 u i (A -1 (i)) 1 2 [START_REF] Aziz | Computing welfare-maximizing fair allocations of indivisible goods[END_REF] 1

Table 7 shows that Γ and Γ * do not maximize the egalitarian social welfare because the allocation A has egalitarian social welfare which is better than the egalitarian social welfare of Γ and Γ * . Now, we propose a scenario called -g-binary, which slightly changes the range of the utilities of each agent, generalizing the notion of g-binary scenarios. Let us see the definition below. Definition 3. Assume that for each r k ∈ R we have a mapping r k → p k where p k is a real number. Let u be a function u : P(R) → R. We say that u is an -g-binary utility function for goods (chores) if:

• u is an additive utility function;

• for every r k ∈ R, p k > (p k < ) and u(r k ) ∈ { , p k }.

When every agent has an -g-binary utility function for goods (chores) with the same mapping r k → p k , we say that the scenario is goods (chores) -g-binary.

The above definition generalizes Definition 1; in the case goods (chores), is the minimum (maximum) value for the scenario. It means that the minimum (maximum) value could be equal to zero or greater than (less than) zero. When is equal to 0, we get exactly the goods (chores) g-binary scenario.

In the following example, we give an -g-binary scenario, with > 0, for which there exists an allocation G / ∈ M SW u having a greater Nash social welfare than all the allocations that maximize the utilitarian social welfare.

Example 4.

We consider n = m = 3. Table 8 defines our -g-binary scenario with b > a > > 0.

Note that any allocation that maximizes the utilitarian social welfare assigns the resources r 2 and r 3 to agent 1 (see Theorem 5). Thus, there are only three allocations, F 1 , F 2 and F 3 , which maximize the utilitarian social welfare. They

Appendix A. Algorithm, proofs and examples

A more detailed explanation of Algorithm 1 is as follows:

1. Let v 0 = (0, . . . , 0) be the initial vector of partial valuations, with size n.

For

(c) Let P k and M k be the sets given by:

and

where

(f) Updating the vector v k of partial utilities, for all i ∈ A:

Notice that P k = ∅. Therefore, M k = ∅ and M k ⊆ N; so, there exists a minimum for M k . On the other hand, ∀i ∈ A, u i is an additive utility function, so each position i of v k , [v k ] i , is the partial valuation given by agent i to its assigned bundle up to step k. Theorem 3. Assume a goods (chores) g-binary scenario and let F be an allocation in A R . Then, F is PO if, and only if, F ∈ M SW u .

Proof: (only if part) Let F ∈ A R , and we suppose that F does not maximize utilitarian social welfare. We want to show that F is not Pareto optimal.

Since all agents consider g-binary utility functions and F does not maximize utilitarian social welfare, by Theorem 5, there exist r * ∈ R and j ∈ A such that u j (r * ) = max{0, p * } and u i (r * ) = min{0, p * } with i = F (r * ) and p * = 0. Let G ∈ A R be given by

, and for all k ∈ A with k / ∈ {i, j}, F -1 (k) = G -1 (k). In a good g-binary scenario, u j (r * ) = p * > 0 and u i (r * ) = 0. So, u j (F -1 (j)) < u j (G -1 (j)) and

Now, in a chore g-binary scenario, u j (r * ) = 0 and u i (r * ) = p * < 0. Thus,

In both cases F is not PO. (if part) Follows from Theorem 1.

The following observation is very useful in the proofs. Its proof is obvious by equations (A.3), (A.1) and (A.2).

Remark 2.

We assume an additive scenario. Let Γ be the allocation of Algorithm 1. For every r k ∈ R and every j ∈ A such that Γ(r k ) = j, we have

Proof:

Let Γ be the allocation of Algorithm 1. By Remark 2, part 2, and Theorem 5, we have that Γ ∈ M SW u . The proposed algorithm starts

This is due to parts 1 and 2 of Claim1 and Equation A. [START_REF] Aziz | Computing welfare-maximizing fair allocations of indivisible goods[END_REF].

Now we prove the lemma. By Claim1 part 3 and the fact that

If the scenario is a chore g-binary scenario, then

Thus, the equations (A.5) and (A.6) are true.

Theorem 7. Under a g-binary scenario for goods or chores, the allocation Γ given by Algorithm 1 produces a maximal utilitarian welfare, is EF1 and PO. Its run time is O(mn).

Proof:

We prove first the case of goods. We suppose that ∀i ∈ A, u i is a g-binary utility function. We consider the allocation Γ of Algorithm 1. By Theorem 6, Γ maximizes utilitarian social welfare in O(mn) operations, and by Theorem 3, Γ is PO. We want to show that Γ is EF1. Suppose that there exists i ∈ A such that

for some agent j. As u i is a g-binary utility, by Lemma 1, it is enough to show that there exists r ∈ Γ

Otherwise, by (A.6) and (A.7), we have

where r s k is the last resource assigned to j and it is preferred by i and j. Since Γ(r s k ) = j and i ∈ P s k , by Remark 2, part 1,

By additivity of u j ,

Using the transitivity of ≥, we have

As u i and u j are utility functions in a g-binary scenario, then the utility that agents i and j assign to each resource in C ij is equal, so

By equations (A.8) and (A.9),

Now, by equation (A.6) and additivity of u i ,

and, by equation (A.10),

), and using transitivity,

Therefore, Γ is EF1. Now we give the proof in the case of chores. By Lemma 1, for all i, j ∈ A,

Suppose that R * = ∅ and that there exist i, j ∈ A such that

We want to show that there is r ∈ Γ -1 (i) such that

By equation (A.14), u i (Γ -1 (i)) < 0; and by equation (A.12), Γ -1 (i)∩R * = ∅. Using additivity of u i and equations (A.12) and (A.13), to show that (A. [START_REF] Nash | The bargaining problem[END_REF]) is true, it is enough to find r ∈ Γ -1 (i) ∩ R * such that

Let r s ∈ Γ -1 (i) ∩ R * such that r s is the last chore allocated to i and it is minimized for all l ∈ A. Consider {r 1 , . . . , r s-1 } 5 the set of all chores allocated before r s . As

On the other hand, as r s is the last chore assigned to i and r s ∈ R * , then

and by Lemma 1,

then, by transitivity,

In order to complete the proof, we only have to show that

because if in (A.17), we take l = j and use transitivity between (A.18) , (A.19) and (A.17), the expression (A.16) is true.

As Γ(r s ) = i, by the way the Γ is defined, then ∀l ∈ A

But, for all l ∈ A,

and

Using transitivity, we get (A.19).

Theorem 8. Under a g-binary scenario for goods or chores, the allocation Γ * given by Algorithm 1 modified as previously indicated maximizes the utilitarian social welfare, is EFX and PO. Moreover, its run time is O(m log m + mn).

Proof:

The argument of the proof is similar to that in the proof of the Theorem 7. Let i, j be in A such that

First we consider the case of goods. By Lemma 1,

As R is sorted in descending order, then for all r ∈ Γ * -1 (j) with u i (r) > 0,

By equation (A.11)

So, for all r ∈ Γ * -1 (j) with u i (r) > 0,

Thus, Γ * is EF X. Now, we consider the case of chores. By Lemma 1,

where r s is the last chore in R * allocated to i. Note that, ∀r ∈ Γ * -1 (i) \ R * , u i (r) = 0. As R is sorted in increasing order then for all r ∈ Γ * -1 (i) with

Then

Since (A. [START_REF] Ramezani | Nash social welfare in multiagent resource allocation[END_REF]) is true for r s , using Transitivity, from (A.20) and (A.16), we have that ∀r ∈ Γ * -1 (i) with u i (r) < 0,

Thus, Γ * is EF X.

The following example shows the facts established in Remark 1 about the behavior of Γ and other allocations in a g-binary scenario.

Example 5. Suppose that R = {r 1 , r 2 , r 3 , r 4 , r 5 } and that each resource r k is valued as p k according to Table A.11. Let A = {1, 2, 3} be the set of agents; each agent i establishes its utility functions u i over each resource using Table A.12. Note that all agents prefer the resource r 1 and their utility is 500. The resource r 2 is required by agents 1 and 3, and their utility is 200; the agents 1 and 2 give to resource r 3 the utility of 50. Concerning the resource r 4 , agents 2 and 3 give it the utility of 100; whereas resource r 5 is only required by agent 2 with utility 250. If for i = 1, 2, 3, the function u i is extended additively over each subset S ⊆ R, that is, ∀i ∈ A, u i (S) = r∈S u i ({r}), then each u i is a g-binary utility function, i.e., it is a g-binary scenario.

In this scenario, we will consider four allocations in order to illustrate their behavior with respect to properties EF1, PO, M SW u and M SW N ash . Let F , G, Γ and J be the allocations defined by Table A. [START_REF] Ebadian | How to fairly allocate easy and difficult chores[END_REF], which shows the agent number who receives each resource.

In Table A.14, we show the utility assigned by each agent to its received bundle, and the social welfare in each allocation. SW u SW N ash u i (F -1 (i)) 500 250 300 1050 37500000 u i (G -1 (i)) 500 300 300 1100 45000000 u i (Γ -1 (i)) 500 400 200 1100 40000000 u i (J -1 (i)) 700 300 100 1100 21000000

The properties of each allocation are described in Table A. [START_REF] Nash | The bargaining problem[END_REF] and the detailed verification of these facts is given below.

PO EF1 M SW

Proof of Properties in Example 5:

We give details of the properties fulfilled by the allocations in Table A.15.

From Theorem 5 and Table A.11, it is easy to see that the maximum utilitarian welfare is reached in 1100. Moreover; G, Γ and J maximize SW u . By Theorem 1 and Table A.14, we have that G, Γ, and J are PO. On the other hand, from Table A.14, we can observe that agents 1 and 3 in the allocations F and G, have the same utility for the received bundle; but, in G, agent 2 improves its utility. Then, F is Pareto dominated by G. Therefore, F is not PO.

A search determined that the maximum Nash social welfare is reached at 45000000. Then G is a maximum Nash social welfare and, by Theorem 2, G is EF1. Moreover, allocations F and Γ are EF1. In fact, Γ is EF1 by Theorem 6.

For F , agents 2 and 3 envy agent 1, however, the envy disappears when eliminating r 1 . Finally, J is not EF1, because agent 3 envies agent 1, u 3 (J -1 (3)) < u 3 (J -1 (1)) and u 3 (J -1 (3) = 100 < 200 = u 3 (J -1 (1) \ {r 1 }) < 500 = u 3 (J -1 (1) \ {r 2 }).

The following example shows that Γ * is not EFX 0 . Example 6. Let's consider the following g-binary scenario where n = 3, m = 8. Table A. [START_REF] Ramezani | Nash social welfare in multiagent resource allocation[END_REF] shows the utility functions that each agent gives to each resource. Now, using the modified Algorithm 1, we get the following allocation Γ * .