Baris Canbaz

Bernard Yannou

Pierre-Alain Yvars

Resolving design conflicts and evaluating solidarity in distributed design

published or not. The documents may come

Resolving design conflicts and evaluating solidarity in distributed design

Introduction

Engineering design processes of complex products and services require the collaboration of multiple design experts from different disciplines, and these can be located in different places. Since there are physical divisions between design experts and/or disciplinary boundaries within the multi-disciplinary design problem, a distributed design approach can be adopted [START_REF] Sobieszczanski-Sobieski | Aerospace engineering design by systematic decomposition and multilevel optimization[END_REF]. In distributed design, while the global design problem is decomposed into subproblems, design responsibility is decentralized and distributed to organizational subsystems composed of one or more design experts [START_REF] Papalambros | Distributed Cooperative Systems Design[END_REF]. Subsystems have limited control over the design variables because of their limited expertise and responsibility. The ultimate objective of collaborative distributed design is to resolve sub-problems concurrently, so that the global multi-objective design problem converges to a global optimum. However, as Lewis and Mistree [START_REF] Lewis | Collaborative, Sequential, and Isolated Decisions in Design[END_REF] point out, it is highly unlikely to obtain true concurrency in reality, because subsystems are not independent. They are related to each other through couplings between their sub-problems. Inconsistencies in the design system can result in design conflicts through couplings. Design conflicts arise during the design process when designers are not able to satisfy their own design objectives. Inconsistencies can be found at both problem level and process level. Problem level inconsistencies consist of non-uniform, in other words conflicting, local design objectives of subsystems. Favoring the design objective of a designer can be detrimental to the design objectives of the other designers. Process level inconsistencies consist of conflicting working procedures of subsystems [START_REF] Zhao | Work Structure Based Collaborative Engineering Design[END_REF]. For instance, a designer that influences the design model more frequently and restrictively can block the other designers which are trying to satisfy their own design objectives. Design conflicts are justified when the satisfaction levels of designers obtained from the global solution diverge, resulting in a situation where a designer is very satisfied and the rest are not satisfied or dissatisfied. This divergence represents the intensity of the design conflicts. Preventing, justifying and resolving design conflicts are indispensable concepts for obtaining globally satisfactory design solutions where satisfaction levels of subsystems are in equilibrium.

Many propositions have been made for design conflict resolution models. The most significant approaches are agent-based models. Klein [START_REF] Klein | Supporting conflict resolution in cooperative design systems[END_REF] proposes a heuristic-based computational model that produces advice for resolving conflicts between design agents. The model utilizes the knowledge about conflict resolution strategies obtained from empirical design expertise. Wong [START_REF] Wong | Coping with conflict in cooperative knowledge-based systems[END_REF] proposes a method of cooperative knowledge-based systems that includes a library of multi-agent design conflict resolution strategies. These strategies can be combined in an appropriate order for the situation, so that if one strategy fails the system tries the next one. Koulinitch and Sheremetov [START_REF] Koulinitch | Coordination and communication issues in multi-agent expert system: concurrent configuration design advisor[END_REF] define a constraint-based dynamic design system model that includes facilitator agents. They send messages to relax some constraints until a consistent solution is obtained. Li et al. [START_REF] Li | Conflict management in closely coupled collaborative design system[END_REF] propose an integration-based conflict resolution system that includes a hierarchical constraint network to detect design conflicts. A knowledge-based method, a constraint relaxation method, and a negotiation method are used to resolve various conflicts. Shin et al. [START_REF] Shin | Conflict detection and resolution for goal formation in the fractal manufacturing system[END_REF] propose a design conflict resolution model that employs agent-based negotiation techniques for facilitating a goal-formation process that generates fuzzy goals and modifies them by coordination between agents. The other significant conflict resolution approaches utilize mathematical optimization techniques and fuzzy logic models. Yin et al. [START_REF] Yin | A policy of conflict negotiation based on fuzzy matter element particle swarm optimization in distributed collaborative creative design[END_REF] propose a combinatorial heuristic algorithm for design conflict negotiation which is based on Fuzzy Matter Element Particle Swarm Optimization (FMEPSO). Jin et al. [START_REF] Jin | A conflict resolution algorithm considering design objective optimization in collaborative design[END_REF] propose a design conflict resolution algorithm that optimizes the design problem by considering the fuzziness of design variables and the additional cost of conflict resolution. Li et al. [START_REF] Li | Preference uncertainty in the graph model for conflict resolution[END_REF] propose a graph model for conflict resolution, not only for design problems, but for all types of conflicting decision making problems of multiple stakeholders. In this approach, the uncertainty of decision maker preferences is modeled, and four types of solution definitions are developed by modeling human behavior under conflict. The graph model is extended with fuzzy preferences by Bashar et al. [START_REF] Bashar | Fuzzy Preferences in the Graph Model for Conflict Resolution[END_REF].

Although these various efforts provide improvements to the design system, some important aspects for managing design conflicts are overlooked. Mathematical optimization models overlook the dynamic nature of the design problem that changes with the evolving intentions of designers, reflecting designer reactions to the uncertainty. Agent-based conflict resolution models consider the dynamic interactions of design agents. However, they do not consider modeling design attitudes that define reactions and interactions of various design agents. This is an important omission, because modeling design attitudes can help to explore design conflicts. In addition, with the exception of some models that represent design variables and decisions with fuzzy parameters, the imprecision caused by the lack of information about design consequences is largely overlooked. Imprecision is inherent to design problems, as it represents the epistemic uncertainty of what the results from the emerging design interactions might be [START_REF] Parry | The characterization of uncertainty in Probabilistic Risk Assessments of complex systems[END_REF]. According to Malak et al. [START_REF] Malak | Multi-attribute utility analysis in set-based conceptual design[END_REF], this issue requires representing the uncertainty with imprecise intervals/sets and delaying uncertain decisions to later process stages where the information about the related decision is available. Besides, the proposed conflict resolution methodologies do not discuss the adoption strategy of the conflict resolution system with regard to the solidarity architecture of the system participants. Centralized conflict resolution system strategies provoke or oblige solidarity between design agents to resolve design conflicts. In contrast, the decentralized conflict resolution system strategy considers an autonomous solidarity where agents are free to decide whether to help to resolve design conflicts. The question of which strategy should be adopted remains unanswered.

In our earlier research [START_REF] Canbaz | Expanding the bottom-up design approach through integrating design attitudes into set-based design[END_REF], we defined a novel bottom-up design approach that employs the concept of Set-based Design (SBD) for managing imprecision in design. Design agent attitudes were modeled for exploring design conflicts. It was demonstrated through Monte Carlo simulations that our agent-based SBD approach prevents design conflicts that arise from heterogeneous designer attitudes. In this paper, we extend this approach and integrate a conflict management model. In Section 2, we discuss the ability of SBD and constraint satisfaction problem (CSP) techniques to manage imprecision in design. Our conflict management model is introduced in Section 3, and the CSP simulation process of this model is presented in Section 4. Monte Carlo simulations of different conflict resolution systems and the non-cooperative design system are performed on a design problem of a multi-clutch system that involves variable agent characters. In Section 5, we present the simulation problem definitions and simulation results. Different system strategies are compared with regard to their gains and costs.

SBD and CSP Techniques

Variables of coupled and conflicting design problems cannot be crisply defined due to the lack of information about the consequences of design decisions [START_REF] Antonsson | Imprecision in Engineering Design[END_REF], [START_REF] Yannou | Managing uncertainty of product data. An enhancement on constraint programming techniques[END_REF]. The epistemic uncertainty due to this imprecision is very significant especially in preliminary design processes. Deterministic design methods cannot overcome this issue, because they require the restriction of the design problem by attributing crisp values to problem variables so that radical decisions are performed before the information about decisions is certain. Set-based design (SBD) is proposed as an distributed design. IEEE Transactions on Systems, Man and Cybernetics: Systems.

3

alternative concept which considers the design process as an ongoing evolution of non-crisp concurrent design decisions [START_REF] Ward | Set-based concurrent engineering and Toyota[END_REF], [START_REF] Sobek | Toyota's Principles of Set-Based Concurrent Engineering[END_REF]. Design problem variables are represented as imprecise values in their domains (intervals for real variables), so epistemic uncertainty can be propagated and evaluated. Design decisions related to certain information are performed as constraints on variable domains, so the epistemic uncertainty is reduced. If design decisions are related to uncertain information, they can be delayed to later process stages where more details about the information is gathered due to the reduction of epistemic uncertainty through previous decisions. This design approach provides flexibility of modifications and higher adaptability to changes [START_REF] Mckenney | Adapting to Changes in Design Requirements Using Set-Based Design[END_REF], as well as robustness to design [START_REF] Parsons | A hybrid agent approach for set-based conceptual ship design[END_REF]. Repetitive design activities and loopbacks are consequently avoided by disclaiming a trial and error approach, so design process time is reduced.

Although SBD originated as a management philosophy for concurrent engineering tasks, recent research has shown that SBD can be adopted at a technical solution level with constraint satisfaction problem (CSP) techniques e.g.

[23]- [START_REF] Yannou | Use of Constraint Programming for Design[END_REF]. A CSP is defined with three groups of sets P = (V,D,C), where V is the set of variables, D is the set of domains that contain the allowable values of variables, and C is the set of constraints that restrict the problem [START_REF] Montanari | Networks of constraints: Fundamental properties and applications to picture processing[END_REF]. A multidimensional space is defined by the Cartesian product of variable domains. It contains the consistent solutions that respect the problem constraints. A design sub-problem is defined by three main problem elements: design variables that can be controlled by the specific subsystem, design performances that are evaluated by the subsystem, and constraints that must be respected for making design decisions. Some of these constraints form the relation between variables and performances. These, or other, constraints can also form couplings between variables and between performances of other sub-problems. A decomposed design problem can be defined with three spaces through CSP definitions: the design space defined by design variables, the performance space defined by design performance variables, and the solution space that contains both design and performance spaces. Design decisions are represented as constraints restricting the solutions space. When the epistemic uncertainty is reduced through design decisions, the remaining solution space of complex problems can be determined precisely with domain reduction/filtering algorithms of constraint programming (CP) techniques [START_REF] Yannou | A Comparative Study of Constraint Programming Techniques Over Intervals in Preliminary Design[END_REF] Some derivatives of CSP are made in order to deal with various artificial intelligence platforms that employ a multiagent system (MAS). Dynamic CSP (DynCSP) allows constraints to be added to or removed from the problem model [START_REF] Dechter | Belief Maintenance in Dynamic Constraint Networks[END_REF]. The problem evolves over time with some agent actions which are related to the constraints performed through a process. The solution space is restricted with the addition of a constraint, or relaxed by the removal of a constraint. The problem at time stage t is , ∆ where is the problem defined at the previous stage and ∆:

is a function that maps the previous problem to the problem at stage t. DynCSP is adequate for MASs that require dynamic negotiation and conflict resolution of interacting agents. Distributed CSP (DisCSP) is proposed to divide the CSP into n sub-CSPs shared to n automated agents ! " : [START_REF] Yokoo | The distributed constraint satisfaction problem: formalization and algorithms[END_REF]. Agents resolve their own sub-CSPs concurrently, and then their solutions are unified. In DisCSP, an agent shares information only for loose couplings. This reduces the cost of knowledge transfer and avoids privacy/security problems among agents that may be caused by sharing all the information [START_REF] Faltings | Introduction: Special Issue on Distributed Constraint Satisfaction[END_REF]. This can be an advantage for large but not very densely coupled problems. However, as Salido and Barber [START_REF] Salido | Distributed CSPs by graph partitioning[END_REF] highlight, DisCSP is not suitable when the problem is densely coupled or the number of variables is very high. Dense couplings among design agents can cause conflicts in the problem solving stage which require a large number of message and information transfers. This issue renders DisCSP non-effective for conflicting distributed design problems. Cooperative CSP (CoCSP) is the problem technique defined by Yvars [START_REF] Yvars | A CSP approach for the network of product lifecycle constraints consistency in a collaborative design context[END_REF], [START_REF] Yvars | A Constraint Based Decision Support System for Deadlocks Resolution in Collaborative New Product Design[END_REF] for obtaining cooperative solutions in MASs. In CoCSP, if a design agent cannot perform its design activities, the other agents can help this agent by compromising their constraints. The CoCSP definition is suitable for dealing with conflicting distributed design problems, because it enables negotiations and conflict resolutions among design agents dynamically during the design process. CoCSP algorithms surveyed in the literature minimize the number of decision constraints rejected at any stage of the design process. This approach considers only the number of decision constraints, but it does not take into account the amount of the restriction and the satisfaction obtained by constraints. When design conflicts emerge from the interactions of heterogeneous designer characters, this approach is inadequate. Since design agents are heterogeneous, they define heterogeneous constraints, so that one constraint of a particular agent can be more restricting than two constraints of another agent. Thus, the conflict resolution objective of heterogeneous MAS should not compromise the quantity of constraints; it should instead compromise the restriction of constraints. In order to satisfy these requirements, we define our model as an agent-based SBD model that explores designer attitudes for detecting and justifying design conflicts. A novel CoCSP model is developed for resolving design conflicts through compromising the restriction of constraints.

# $ % & ' & $ ( )

Conflict Management Model

In SBD, design variables are represented with imprecise domains/intervals. The analysis of the design space emerging from allowable design variable solutions stimulates design agents to react so as to satisfy their design objectives. Design agents react through defining decision constraints in the design model. The reaction of agents to uncertainties of complex dynamic domains is defined by agent attitudes [START_REF] Goyal | Attitude based teams in a hostile dynamic world[END_REF]. The most widely deployed architecture of an agent is the Belief-Desire-Intention (BDI) paradigm developed by Bratman et al. [START_REF] Bratman | Plans and resource-bounded practical reasoning[END_REF]. The character of an agent is the combination of its various autonomous attitudes, and different strategies can be developed through exploring agent characters in order to obtain optimal interactions between heterogeneous agents [START_REF] Castelfranchi | Personality Traits and Social Attitudes in Multiagent Cooperation[END_REF]. We use CSP definitions and the BDI paradigm to manage design conflicts of autonomous agents. Fig. 1 shows our adaptation of the BDI mechanism for a design agent.

Fig. 1. BDI Mechanism of Design Agents

Desires: Preferences

We define an agent k, ! + , as an entity with five different attitudes: ! + / + , 0 + , -+ , . + , * + . Analysis of the design space stimulates the design agent, and this triggers its BDI mechanism. The design space is transformed through CSP definitions into the performance space where design agents define their design objectives. Upper and lower bounds of the design performance intervals represent the possible worst cases and the possible best cases. These cases reflect the beliefs of the design agent about the convergence of its design performance variables towards its design objectives. The converging intervals of possible worst and possible best cases propagate some uncertainty for the design agent. Reactions of design agents are bound through couplings, because the solution space is shared. If an agent modifies the design model for its own benefits, it can decrease the best case of another agent with a conflicting objective. Thus, the performance intervals of an agent depend on the unpredictable reactions of the other design agents. In order to adopt design performance values, the design agent defines preferences about its design performances and the emerging satisfaction values from these performances. Preferences reflect the agent's desires towards its uncertain design performances. / + is the set of preferences of the agent on the performance values. It reflects the agent's attitudes for satisfaction obtained from alternative solutions. In a coupled design system, it is highly unlikely to fully satisfy all the design agents. Therefore, design agents are forced to compromise at a certain level on their satisfaction interval. 0 + is the compromise threshold value of the agent. It represents the preference of the agent on the satisfaction values for compromise.

Beliefs and desires lead the design agent to state intentions for increasing its satisfaction from the dynamic design model. The design agent reacts by defining decision constraints that restrict the solution space, with the aim of improving its worst cases. Intentions are reflected with how frequently and how restrictively the decision constraints are defined. -+ is the average frequency attitude of the agent for defining constraints in the model. . + is the coefficient of restriction of constraints defined by the agent. It reflects the restrictiveness attitude of decision constraints defined by the agent. When a decision constraint is defined, the design model's feasibility is evaluated through testing the consistency of the decision constraint with CP techniques. After the definition of the constraint, the design model is feasible if there is at least one solution remaining in the solution space. Therefore, the decision constraint emerging from the agent's BDI mechanism is accepted, and a new design space is synthesized in the dynamic process. The decision constraint is rejected if it yields an empty solution space. When a decision constraint is rejected, it means the design agent could not perform its modifications, so a potential design conflict is detected. The conflict is justified only if the rejection of a decision constraint means an under-satisfied design agent caused potentially by over-satisfaction of another design agent or design agents. This justification process requires CoCSP definitions where all the information about the agents' states and their decision constraints are shared among design agents. If a conflict is justified, the other design agents can help this agent to incorporate its constraint into the design model. * + is the helping attitude of ! + . If ! + needs help, the other design agents' helping attitudes * +, determine the approval of the conflict resolution process. Conflict justification and resolution models are defined in the following sub-sections.

In our BDI adaptation, beliefs and intentions are dynamic, while desires are static. Preferences do not change during the design process, because we assume that they are defined at the initial process stage. With the increasing number of decision constraints introduced to the problem, the sub-problem of an agent is dynamic through the design process stages. The aggregated sub-problems propagate the dynamic design model that converges to a narrower space continuously. Therefore, beliefs evolve while the design uncertainty is reduced progressively. Further decisions are made when more detailed design information is available. Consequently, intentions change during the design process. Since design agents are related through couplings, their interactions are dynamic. The consistency of a decision constraint defined by an agent depends on the solution space which is also restricted by the other agents. A potential design conflict caused by an inconsistent constraint, either resolved or unresolved, will alter the intentions of agents at subsequent process stages.

Conflict Justification

In order to justify conflicts, we evaluate design agents' states during the design process with control indicators called wellbeing indicators. The wellbeing indicators are derived from the desires and the beliefs of the agents. First we model design performances with satisfaction functions defined by piecewise constraints. Satisfaction functions are scaled between 0 and 1. For example, one objective of agent k is to maximize a performance i. The agent is fully satisfied by a performance value above or equal to and fully dissatisfied by a performance value below or equal to 1 . It is assumed that there is a linear transition between these two preference values. 2 +" is the satisfaction value of the agent k obtained by the performance i. 3 " is the performance value of the performance i. Then the piecewise constraints are as follows:

If 3 " 4 , 2 +" 1 (1) If 3 " 1 , 2 +" 0 (2) If 5 3 " 5 1 , 1 5 2 +" 5 0 ( 3
)
SBD process is an ongoing evaluation of intervals, so the design process is divided into stages where design agents make reactions. At process stage t, performance i is defined with an interval, 6 " , 7 " , where 6 " is the minimum value, and 7 " is the maximum value. An interval for the satisfaction of agent k is obtained from performance i at stage t: 2 +" 89:2 +" , 8;62 +" where 89:2 +" is the minimum satisfaction and 8;62 +" is the maximum satisfaction obtained within the interval 6 " , 7 " . Fig. 2 demonstrates an example with the piecewise constraints given above. Minimum satisfaction is obtained at point B, and maximum satisfaction is obtained between P1 and point A.

Fig. 2. Intervals of satisfaction function

A design agent may evaluate several design performances. The most widely employed decision making model in MAS for evaluating multiple performances is the multiple attribute utility theory (MAUT). In order to elicit the aggregate utility, weights of multiple attributes are estimated methodologically [START_REF] Guo | Learning User Preferences for Multi-attribute Negotiation: An Evolutionary Approach[END_REF], [START_REF] Jonker | An agent architecture for multi-attribute negotiation using incomplete preference information[END_REF]. The weights for design performances can be estimated if the sub-problem of the agent is scalable. Otherwise, the sub-problem should further be decomposed. In this paper, we assume that the design problem is correctly decomposed, so that an agent is able to assign weights to its design performances by comparing their relative importance for its job. < +" is the weight assigned to the performance i by the design actor k. I is the total number of the performances considered by design actor k. General satisfaction of an agent k is an interval 2 + 89:2 + , 8;62 + . Its bounds are calculated with the following equations:

89:2 + = < +" 89:2 +" > "? (4)
8;62 + = < +" 8;62 +" > "?

(5) 1 @A (6)

1 0 2 +"

Fig. 3. Bilateral convergence

Design agents define decision constraints in order to improve their minimum satisfaction values during process stages. However, the convergence of their satisfaction intervals is bilateral because of conflicting couplings. Fig. 3 shows an example where the constraints of Agent 1 are represented with dashed arrows, and the constraints of Agent 2 are represented with solid arrows. When a constraint is defined by an agent, it increases the minimum satisfaction value of this agent. However, this decreases the maximum satisfaction of the other agent with a conflicting objective. Therefore, at the end of the design process, satisfaction intervals converge to a compromised point solution where minimum and maximum satisfaction values are approximately equal. This solution is uncertain during the design process until it is obtained. Design agents can reflect an attitude of desiring a satisfaction value in which they may compromise. The preference of agent k about this satisfaction value is called compromise threshold 0 + . This is the compromise attitude of agent k. The objective of a design agent is to guarantee that its satisfaction interval will converge to a value at least as good as its compromise threshold value. If the minimum satisfaction of an agent reaches its 0 + value or passes beyond, then the agent passes to the compromise state. In the compromise state, the agent stops adding decision constraints to the model, so this leaves space to the other agents in the solution space. The larger the 0 + value, the more restrictive agent k is. 0 + is defined empirically by considering both technical and arbitrary factors: solution space, uncertainty, and the other agents' design freedom. It should be noted that, if agent k is very egoistic, it will not consider the other agents' design freedom. It can thus define a large 0 + value.

Satisfaction values are normalized by dividing them by the compromise threshold value, and this provides wellbeing states Eq. [START_REF] Koulinitch | Coordination and communication issues in multi-agent expert system: concurrent configuration design advisor[END_REF][START_REF] Li | Conflict management in closely coupled collaborative design system[END_REF]. Wellbeing is defined for each agent k with an interval <B + 89:<B + , 8;6<B + where minimum value is the minimum wellbeing indicator, and maximum value is the maximum wellbeing indicator at stage t. As described in our earlier work [START_REF] Canbaz | Expanding the bottom-up design approach through integrating design attitudes into set-based design[END_REF], these indicators represent how agents' design targets are likely to be met at a given moment of the design process. Global states of design agents are thus observed. This is the reason why the "wellbeing" term is chosen to name these indicators. Since the convergence is bilateral, the likelihood to meet the design targets of an agent can be different than another one. Minimum wellbeing indicators of agents are compared to justify a potential conflict. If an agent suffers because of design conflicts, it will thus be detected immediately.

Agent k defines decision constraints when it is not in the compromise state. The decision constraint of agent k is rejected if it does not provide any consistent solution. This represents a potential design conflict. If there is at least one agent k' in a better wellbeing state with a higher 89:<B +, then the design conflict is justified. This is because it is considered that the shared solution space is not restricted in equilibrium. At least one agent has restricted the solution space for its benefits more than the suffering agent that cannot get its decision constraint accepted. The

8

suffering agent can therefore ask help to the other agents in better wellbeing states in order to resolve the justified design conflict. If the conflict is not justified, then the agent does not deserve the conflict resolution. This agent must reduce its . + value in order to define a less restrictive constraint at the following design process stage.

Conflict Resolution

Design agents intend to improve their minimum wellbeing states. Intentions are represented with how frequently and how restrictively their constraints are defined. -+ is the average frequency of agent k to define its decision constraints in the model. E + is the phase of the decision frequency of ! + . In internationally distributed design systems, agents are available in different time zones, so phases of frequencies can be different from one agent to another. Agent k defines decision constraints at each process stage t where F G E + value is an integer multiple of 1/-+ . We consider that 1/-+ is an integer number, because process stages are represented with integer values. . + is the coefficient of restriction for the constraints defined by agent k in order to improve its wellbeing state. SBD is an on-going restriction of the solution space, so we assume that agents restrict their wellbeing intervals by defining increasingly restrictive constraints. The constraint defined by agent k at process stage t is I + : <B + 4 89:<B + 1 & . + where 89:<B + value and . + value are larger than 0. We assume that -+ is a fixed value during the process, because it represents the average. However . + value can change during the process depending on how restrictively the agent intends to define its constraint at the process stage.

Both -+ and . + define the working procedures of agent k. Since design agents are autonomous, their design attitudes reflected during the design process can be heterogeneous. Inconsistencies can arise among heterogeneous working procedures through design couplings. We explore design agents' working procedures to resolve design conflicts. When a decision constraint of an agent k is accepted, it is put on a list of accepted constraints J + . When a constraint defined by an agent is not consistent, then the constraint is refused, because it causes an unfeasible solution space. Other agents can help to enable this constraint by removing some of their constraints from their list of accepted constraints. In our CoCSP, we assume that only one agent can offer to cooperate at any one time: multiple agents do not cooperate. Our conflict resolution model can detect which agent can help, and how it can help optimally. The model is composed of three phases. The first phase is the negotiation phase where we detect all the help possibilities. The second phase is the testing phase where the feasibilities of different help possibilities are tested with CP techniques, and the optimal help among the feasible help solutions is detected. The third phase is the approval phase where we detect if the help is approved or not by the helping agent.

Negotiation Phase

When agents are asked to help, they negotiate the results of the help through comparing their states in order to decide whether they are able to help or not. We assume that agents that are asked to help would want to keep their wellbeing states at least as good as the other agent that needs help after the help is performed. If the wellbeing state of the agent which is asked to help were to go below the wellbeing state of the agent that needs help, then the help is refused. This refusal is reasonable, because otherwise the wellbeing state of the helping agent would become inferior after the help, thus generating another conflict. Fig. 4 shows an example representing this phenomenon. Here, agents' constraints defined during process stages 0 to 2 and their wellbeing states emerging from these constraints are shown. While all the constraints defined by Agent 2, Agent 3, Agent 4, and Agent 5 are accepted, the constraint I 1 of Agent 1 defined at process stage 2 is inconsistent, so it is refused. Agent 1 needs help in order to enable its constraint. The dashed line compares agents' states. Agent 5 is not able to help, because even without removing any constraint, its wellbeing state would be inferior to the wellbeing state of Agent 1. Agent 2 is not able to help, because in the case of help, it would remove I 1 1 and its wellbeing state would go below the wellbeing state of Agent 1. Agent 3 is able to help through removing I C 1 or both I C and I C 1 without making its wellbeing state inferior to the wellbeing state of Agent 1. Agent 4 is able to help through removing only I K 1 . All the help possibilities are detected through the negotiation phase following this procedure.

Fig. 4. Negotiation phase of design agents

Testing Phase

If help is possible, its feasibility is tested. Help is feasible if it enables the constraint of the agent that asks for help. This test is performed with CP techniques. The help is feasible if the solution space contains at least one consistent solution after the definition of the conflicting constraint and the removal of the constraint or constraints of the agent that is able to help. Fig. 5 shows a numerical example where there are three design agents with heterogeneous design attitudes: Agent 1: 0 0.9 , -0.5 , . 0.5 , * 0,75 , Agent 2: 0 1 0,9 , -1 1 , . 1 0.2 , * 1 0.7 , and Agent 3: 0 C 0.8 , -C 0.5 , . C 0.4 , * C 0.8 . Agent 2 and Agent 3 start at stage 0, while E 1. The constraints defined by agents at process stages, as well as agents' minimum wellbeing values emerging from these constraints are shown. At stage 5, minimum wellbeing values of Agent 1 and Agent 2 are both equal to 1. These agents compromise, so they will not define a constraint during subsequent process stages.

All the constraints defined by agents till stage 6 are accepted, so J : I , I C , I N , J 1 :

I 1 O , I 1 , I 1 1 , I 1 C , I 1 K , I 1 N and J C : I C O , I C 1 , I C K .
However, the constraint defined by Agent 3 at stage 6 is refused because it is inconsistent, so it returns an unfeasible solution space. The design conflict is justified, because at stage 5, the wellbeing states of Agent 1 and Agent 2 are better than the wellbeing state of Agent 3. In order to resolve this justified conflict, we detect all the help possibilities that can be provided from Agent 1 and Agent 2. Agent 1 can remove only I N , and Agent 2 can remove only I 1 N or both I 1 K and I 1 N . However, Agent 1 refuses to remove constraint combinations that include the I C , I N set, and Agent 2 refuses to remove constraint combinations that include the I 1 C , I 1 K , I

Approval Phase

When the optimal help is detected, our model sends a message to the agent that needs help about who can help. It sends another message to the agent that can help about exactly how the agent can help. If the conflict resolution system is decentralized, then helping is under the responsibility of agents. Design agents are autonomous when deciding whether to cooperate by approving the help, or not cooperate by rejecting the help. This is defined by agents' helping attitude * + . * + is the probability of agent k to approve help. For the example defined in Fig. 5, the probability of Agent 1 to approve help is 0.75, and the probability of Agent 2 to approve help is 0.7. If the help is approved and performed, then the compromised constraints of the helping agent are removed from the design model and from its list of accepted constraints J + . The helping agent returns to its wellbeing value and . + value of the process stage where the remaining most restrictive constraint is defined after the constraint removal. If help is approved by an agent that is in the compromise state, then the agent leaves the compromise state after the help is performed, because its minimum wellbeing value goes below 1. If the help is not approved, the conflict resolution process is unfruitful. Then the agent k that asked for help reduces its . + value in order to define a less restrictive constraint at the following process stage.

When the conflict resolution system is decentralized, agents can seek revenge. For instance, suppose agent k needs help, and agent k' does not approve the help. If at a following process stage agent k' needs help, and agent k can help, then agent k seeks revenge by not approving the help to agent k' regardless of its * + . In addition, different control strategies can be defined to encourage design agents to approve the help, or penalize design agents that do not approve the help. Alternatively, a completely centralized conflict resolution system can be adopted where design agents are obliged to approve the help regardless of their helping attitudes.

CSP Simulation Process

In this section, we present an automatic constraint propagating simulation where the solution space is reduced iteratively considering design agents' BDI mechanism. The objective of our simulation is to evaluate gains and costs of our cooperative conflict resolution model whether the conflict resolution system is centralized or decentralized. Four different system strategies are defined considering the extent of promotion of solidarity.

Strategy 1: Non-cooperative design system. Agents do not share information about their wellbeing states and constraints, so the design system does not include the conflict management system. If a design conflict arises, it remains unresolved.

Strategy 2: Decentralized conflict resolution system. Agents share all the information. If a design conflict arises, agents are free to decide whether to cooperate by approving the help, or not cooperate by rejecting the help. Therefore, agents can seek revenge if the help is not approved.

Strategy 3: Controlled conflict resolution system. Agents share all the information. If a design conflict arises, agents are free to decide whether to cooperate by approving the help, or not cooperate by rejecting the help. However, if an agent does not approve the help, it is by a control agent. A penalized agent cannot define a decision constraint at the next process stage where it is available to define a constraint. After the penalized process stage, it can continue to define decision constraints. Agents do not intend to seek revenge, because uncooperative agents have already been penalized. For the simulation, we consider process stages as iterations. In the CSP simulation process, we use a split mechanism similar to the round-robin strategy that loops on all the variables at process iteration [START_REF] Granvilliers | Adaptive Bisection of Numerical CSPs[END_REF]. The objective of this mechanism is to obtain upper and lower values which are as close as possible for each interval. Wellbeing intervals are restricted until a good degree of precision is obtained. The simulation algorithm is shown in Fig. 6. We make the following assumptions when defining the simulation process:

• The attitudes of agents are defined at the initial state of the process. / + , 0 + , and -+ attitudes do not change during the simulation process, because / + and 0 + represent fixed desires whereas -+ represents an average value. However, . + attitude value can change during the process depending on the restrictiveness intentions.

• If F G E + -+ S Z and 89:<B + 1, each agent k can define a decision constraint only once at any iteration, and constraints are defined sequentially. If 89:<B + 4 1, then the compromising agent is extracted from the splitting loop with . + 0. If all the agents are processed in iteration, then the process passes to the next iteration: t++.

• Initial worst cases are larger than 0: 89:<B + O 5 0 @A. Decision constraints are defined for improving the worst case scenarios with a coefficient of restriction . + 5 0 @A. The constraint defined at process stage t by agent k is I + : <B + 4 89:<B + 1 & . + . We assume that design agents do not restrict their wellbeing intervals so that minimum wellbeing value surpasses 1. If 89:<B + 1 & . + 5 1, then 1 & . + 1/89:<B + .

• If a constraint is rejected and the conflict is not resolved, its related coefficient of restriction value is reduced by half: . + . + 0.5. Thus a less restrictive constraint can be defined at the next iteration. If the coefficient of restriction value of an agent reaches a precision value (P), then the splitting is stopped for this agent, because the upper and lower bounds of its wellbeing variable are as close as possible considering the precision value. If all the coefficient of restriction values reach P, then the simulation process stops.

• If help is approved, the helping agent returns to the . + value of the process iteration where the most restrictive constraint is defined after the constraint removal.

The simulation process evaluates the strategies by three process performances: number of iterations, total wellbeing and divergence of individual solutions. A smaller number of iterations means a faster convergence of intervals and a rapid design process. In addition, the global objective of the design system is to maximize the wellbeing values of agents while minimizing their divergence. This divergence is defined as the difference between agents' individual wellbeing states. It represents the degree of intensity of the unresolved design conflicts. In the ideal case, agents should obtain the same wellbeing values and each one should be equal to 1. Absolute differences of the wellbeing values of each two element combination represent a vector U , … , U W . The Euclidian distance of this vector solution to the ideal case solution gives the divergence of the individual solutions:

93X/YX:ZX [ U 1 & … & U W 1 .
More divergent solutions lead to more intense conflicts, because the divergence is caused by agents with a relatively low wellbeing value. However, the divergence cannot be evaluated alone. It should be evaluated with the total wellbeing value because a zero divergence is not desirable if total wellbeing is zero.

Monte Carlo Simulation

Design agents can reflect different characters emerging from their BDI mechanism, and this defines an uncertain design system composed of either heterogeneous or homogeneous design agents. Agents' characters can be classed in two extreme groups, namely egoistic characters and altruistic characters [START_REF] Pita | Simulations of egoistic and altruistic behaviors using the vidya multiagent system platform[END_REF]. Egoistic agents are motivated by self-interested gains, while altruistic agents are motivated by the benefit of the group that it belongs to. According to our BDI definition, a design agent ! + / + , 0 + , -+ , . + , * + is relatively egoistic if its 0 + , -+ , and . + attitude values are relatively larger, because it desires to compromise at a higher wellbeing state and it intends to define more restrictive constraints more frequently. Its * + attitude value is also smaller, because it does not intend to help easily. In contrast, an altruistic agent has relatively smaller 0 + , -+ , . + attitude values and a larger * + value. The stochastic nature of the system is considered with a Monte Carlo simulation approach. Three different agent characters are defined as shown in Table 1: Egoistic, Moderate, and Altruistic. We consider that there are no phase differences of frequencies. Each of the four system strategies is repeated 1000 times with randomly generated agent characters.

The same series of random seed numbers is utilized for each strategy, so the simulation results of four strategies are comparable. Also design agents are randomly processed in iterations, so the process sequence is completely independent from agent characters. The precision value is defined as 0.01. This means that if the interval of <B + does not contain 89:<B + 1.01, it is extracted from the loop at iteration t. CSP is defined in C++ computer language and a CP solver library called IBM ILOG CP V1.6 [START_REF] Ibm | IBM ILOG CPLEX CP Optimizer for Constraint Programs -Features and benefits[END_REF] is used to detect consistent solutions precisely through its domain reduction and constraint propagation algorithms. The solve function of IBM ILOG CP is performed to examine the feasibility of the model. The simulation problem is derived from the example studied in work [START_REF] Yannou | Parameterization and Dimensioning of the Multi-Disc Clutch in the CO4 Environment[END_REF]. As shown in Fig. 7 it is a design problem of a multi-clutch system that connects a weight lifter with an engine, followed by a gearbox. This is a complex and a realistic design problem which contains 81 variables and 64 initial constraints. The problem nomenclature is given in Table 2. The problem is distributed to four design agents. The design objectives are shown in Table 3. The piecewise constraints representing the preferences of the design agents are shown in Table 4. All the transitions between the preferences are considered linear as shown in Fig. 2. Agent 4 evaluates four design performances, the same weight being attributed to these performances: 2 K ∑ 2 K" 0.25 K "?

. The average results of the Monte Carlo simulation are shown in Fig. 8. In order to analyze the statistical significance of the results, we performed two tailed t-tests for each pair of strategies. The resulting p-values are shown in Table 5. If the significance level is considered as 0.05, the results of the strategies are significantly different (very low pvalues), except Strategies 2 and 3 (p-values larger than 0.05). In the ideal case, all four agents would obtain a final wellbeing value which is equal to 1. The total wellbeing would be equal to 4, and the divergence would be equal to 0. This ideal solution represents that all the desires of agents are fulfilled. However, this is a utopia solution, because the convergence of the wellbeing is typically bilateral. Since the desires of design agents reflect customer preferences, approaching the ideal solution along both the total wellbeing and divergence axes will improve the designed product. This will increase the overall utility of the product while

Divergence

providing more balance between the satisfactions of different design objectives. Thus, the design process results in a balanced and optimal solution that best meets all relative customer preferences. As seen in Fig. 8, the conflict resolution systems, regardless of their adoption strategy, result in a larger total wellbeing value and a smaller divergence than the non-cooperative design system. This shows that the conflict resolution systems approach the ideal solution more closely than the non-cooperative design system. However, this is obtained at a cost of longer process time. The most rapid system strategy is the non-cooperative design system strategy, because there is no conflict resolution that can cause loopbacks to the helping agents. In contrast, the centralized conflict resolution system resolves more design conflicts than the other strategies. This causes more loopbacks, which explains why this strategy generates the longest process time.

The results prove that the divergence is reduced, and the total wellbeing is increased with the number of design conflicts resolved or prevented. The least divergence and the greatest total wellbeing values are obtained by the centralized conflict resolution system. These results (total wb = 3.29 and divergence = 0.55) are the closest to the ideal solution (total wb = 4 and divergence = 0). Although the average results of Strategy 3 (total wb = 3.27 and divergence = 0.60) are slightly better than Strategy 2 (total wb = 3.26 and divergence = 0.62), it is not statistically significant that the controlled conflict resolution system outperforms the decentralized conflict resolution system.

Conclusions

In this paper, we explored design conflicts with a BDI model and CSP definitions, so that design conflicts can be justified. We defined a CoCSP which is able to manage conflicts by allowing design agents to help others through compromising the restrictiveness of their decision constraints. The degree of this helping attitude represents the solidarity of agents. We defined three different conflict resolution system strategies by considering the solidarity architecture of the agents. We compared these strategies with the non-cooperative design system that does not include any conflict resolution. Monte Carlo simulation results show that, regardless of the conflict resolution system strategy adopted, our conflict management model represents a significant improvement over the noncooperative design system. The divergence of individual wellbeing solutions is lowered and the total wellbeing is increased. Thus, through our conflict management model, the design solution tends towards the ideal solution where design agents are completely and equally satisfied in equilibrium. However, this gain is obtained at the cost of the increase of design process time, because conflict resolution causes loopbacks. In addition, it should be noted that the proposed conflict management model can be applied on only measurable design systems where all the design aspects can be quantified. Another limitation is that the feasibility of the conflict resolution is not guaranteed. During a design process, the model may not detect a feasible help although design agents would help. This feasibility behavior depends on the previous accepted constraints.

Other conclusions are deduced by comparing different adoption strategies of the conflict resolution system. A centralized conflict resolution system strategy can be adopted if the process time is not an important issue, and if the main objective is the highest possible degree of conflict resolution. With the lowest divergence and the highest total wellbeing, this system converges to the ideal solution closer than any other system. This system thus produces a better final product which has a higher overall utility and a balanced satisfaction among different attributes. In addition, it is shown that the penalization of uncooperative agents do not significantly improve the solution in a conflict resolution system where the solidarity is autonomous. We conclude that the centralization of the conflict resolution system (solidarity obligation) is more fruitful and should be preferred to the decentralization (autonomous solidarity). Consequently, informing design agents of their respective situation in terms of their wellbeing -the information transparency value -and encouraging or forcing them to help each other -the solidarity value -are two values we believe efficient for the quality of the resulting design, albeit sometimes to the detriment of design process time.

7 =

 7 , Yannou B., Yvars P.-A., (2013), Resolving design conflicts and promoting solidarity in distributed design. IEEE Transactions on Systems, Man and Cybernetics: Systems.

Fig. 5 .

 5 Fig. 5. Numerical example of conflict management

  , Yannou B., Yvars P.-A., (2013), Resolving design conflicts and promoting solidarity in distributed design. IEEE Transactions on Systems, Man and Cybernetics: Systems. 11

Strategy 4 :

 4 Centralized conflict resolution. If a design conflict arises, agents are obliged to cooperate by the help.

Fig. 6 .

 6 Fig. 6. Simulation algorithm

15 Fig. 8 .

 158 Fig. 8. Simulation Results

C

  Canbaz B., Yannou B., Yvars P.-A., (2013), Resolving design conflicts and promoting solidarity in distributed design. IEEE Transactions on Systems, Man and Cybernetics: Systems.

	2	8;62 89:2	8;62 1 89:2 1	8;62 C D 89:2 C
	2 1	8;62 1 89:2 1	8;62 1 1 89:2 1 1	C 8;62 1 D 89:2 1
		Stage 1	Stage 2	Stage 3

  1 N set, because the emerging wellbeing states would fall below the wellbeing state of Agent 3. Next, feasibilities of all the possible helps are tested. If the removal of a constraint combination enables the acceptance of I C Canbaz B., Yannou B., Yvars P.-A., (2013), Resolving design conflicts and promoting solidarity in distributed design. IEEE Transactions on Systems, Man and Cybernetics: Systems.10 define a less restrictive constraint at the following process stage. If there is more than one feasible help, then we detect the optimal help. We choose the feasible help that gives the maximal ∑

	the constraint or constraints.			R +?O	89:<B +	value after the removal of
		Agent 1			Agent 2	Agent 3
	Initial 89:<B	0.31 89:<B 1 0.34 89:<B C 0.17
	t=0 t=1 t=2 t=3 t=4	WELLBEING STATES I : <B 4 0.47 I C : <B 4 0.7	I 1 O : <B 1 4 0.41 I C O : <B C 4 0.24 I 1 I 1 1 I 1 O I 1 : <B 1 4 0.49 I 1 1 : <B 1 4 0.59 I C 1 : <B C 4 0.33 I 1 C : <B 1 4 0.71 I 1 K : <B 1 4 0.85 I C K : <B C 4 47	I C I C O I C 1	I K 1 I K O	I N 1 I N O
	t=5	Agent 1 I N : <B 4 1	Agent 2 N : <B 1 4 1 I 1	Agent 3	Agent 4	Agent 5
	t=6					I C P : <B C 4 0.65

P , then its help is feasible.

Conflict resolution process is unfruitful if there is no feasible help solution. Then, Agent 3 reduces . C in order to

Table 1 .

 1 Definitions of random characters

	0 + :	Egoistic (0.6, 0.65, 0.7, 0.75, 0.8, 0.85,	Moderate (0.45, 0.5, 0.55)	Altruistic (0.1, 0.15, 0.2, 0.25, 0.3, 0.35, 0.4)
	0.9, 0.95, 1) (0.5, 1) . + : (5, 6, 7, 8, 9) -+ : * + 0.2	(1/3, 0.5, 1) (3, 4, 5, 6, 7) 0.5	(1/3, 0.5) (1, 2, 3, 4, 5) 0.8

Table 2 .

 2 Problem nomenclature

	8 \]^_ Weight of mass to be lifted, kg. 8 ` Weight of whole system (clutch + engine), kg. 0 Final temperature of the clutch, °C. a Safety against stress at position 1 a 1 Safety against stress at position 2 a C Safety against stress at position 3 a b Safety of discs material against pressure 2 + Satisfaction of aent k 2 K" Satisfaction of Agent 4 from performance i

Table 3 .

 3 Problem objectives

	Agent 1 Agent 2 Agent 3	Agent 4
	Objectives

Table 4 .

 4 Clutch preferences

	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then
	If	then

Table 5 .

 5 p-values

		Strategies 1-4	Strategies 2-4	Strategies 3-4	Strategies 1-3 Strategies 2-3	Strategies 1-2
	Iterations	1.15E-15	0.000855	0.026087	4.08E-17	0.186749	5.21E-17
	Resolved Conflicts	5.59E-40	4.06E-18	7.29E-18	3.75E-87	0.488849	1.3E-91
	Total wb	1.74E-06	0.000391	0.036001	0.001059	0.193819	0.0491
	Divergence	6.25E-38	4.15E-15	2.96E-10	2.24E-16	0.180018	1E-12


Vineeth S Varma

Irinel-Constantin Morȃrescu

Samson Lasaulce

Samuel Martin

I-C Morȃrescu

Marketing resource allocation in duopolies over social networks

Keywords: Game theory, Network analysis and control, Agents-based systems

One of the key features of this paper is that the agents' opinion of a social network is assumed to be not only influenced by the other agents but also by two marketers in competition. One of our contributions is to propose a pragmatic game-theoretical formulation of the problem and to conduct the complete corresponding equilibrium analysis (existence, uniqueness, dynamic characterization, and determination). Our analysis provides practical insights to know how a marketer should exploit its knowledge about the social network to allocate its marketing or advertising budget among the agents (who are the consumers). By providing relevant definitions for the agent influence power (AIP) and the gain of targeting (GoT), the benefit of using a smart budget allocation policy instead of a uniform one is assessed and operating conditions under which it is potentially high are identified.

I. INTRODUCTION

D UOPOLY is a standard scenario in economics, poli- tics, and marketing that considers the competition between two (dominant) players over a market, for example, see [START_REF] Singh | Price and quantity competition in a differentiated duopoly[END_REF]. Illustrative examples of real-life duopolies are Airbus/Boeing in the market of large commercial airplanes, Republican/Democratic parties in the American politics.

Traditional research on competitive games between marketers assumes a homogeneous population of consumers [START_REF] Friedman | Game-theory models in the allocation of advertising expenditures[END_REF], [START_REF] Esmaeili | A game theory approach in seller-buyer supply chain[END_REF]. Unlike these works, we propose a marketing resource allocation based on the influence power that each individual has over the (physical or digital) social network. Basically, we consider that the advertising is done in two steps: the first is done by the marketer that allocate her resources to sway some individuals/agents on her opinion and the second is done by the agents of the social network who influence each other. Consequently, each marketer has to target appropriate influential agents in the network in order to optimize her revenue. Since the focus of the paper is on the resource allocation of the marketer, the second step is modeled by a simple opinion dynamics model introduced in [START_REF] Degroot | Reaching a consensus[END_REF].

There is an obvious gap between the literature of economics and the literature on formal opinion dynamics seen from the control community perspective. On one hand, the literature of economics on the considered problems contains many ideas, concepts, approaches but is not very formal, see [START_REF] Tsang | Consumer attitudes toward mobile advertising: An empirical study[END_REF], [START_REF] Woerndl | Internet-induced marketing techniques: Critical factors in viral marketing campaigns[END_REF] which illustrate this point. On the other hand, the control literature is formal but does not address aspects such as the problem of competition over social networks as we do in the manuscript. Therefore, our approach can be seen as a contribution to bridging this gap and the model we propose can be seen as the first step in this direction. Although some recent studies propose the control of one or few agents (see [START_REF] Caponigro | Sparse feedback stabilization of multi-agent dynamics[END_REF], [START_REF] Dietrich | Control via leadership of opinion dynamics with state and time-dependent interactions[END_REF]) in order to enforce consensus, there are very few that deal with the control of opinion dynamics. Besides these methods of controlling opinion dynamics towards consensus, we also find recent attempts to control the discrete-time dynamics of opinions such that as many agents as possible reach a certain set after a finite number of influences [START_REF] Hegselmann | Optimal opinion control : The campaign problem[END_REF]. In the literature on viral marketing, the idea that members of a social network influence each others purchasing decisions have been studied, with the goal being to select the best set of people, such that marketing to this set would maximize the overall profit by propagation of influence through the network [START_REF] Domingos | Mining the network value of customers[END_REF]. This problem has since received much attention, including both empirical and theoretical results [START_REF] Arthur | Pricing strategies for viral marketing on social networks[END_REF], but these results often consider a single entity influencing the network.

In this paper, we consider two competing marketers who want to use their marketing budget in order to sway on their side as many individuals of the network as possible. Thus, the natural framework to exploit is that of game theory and a reasonable solution concept (for arguments see e.g., [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks : Fundamentals and Applications[END_REF]) for analyzing such a competition situation is the Nash equilibrium (NE). In [START_REF] Masucci | Strategic resource allocation for competitive influence in social networks[END_REF], the authors consider multiple influential entities competing to control the opinion of consumers under a game theoretical setting. However, this work assumes an undirected graph and a voter model for opinion dynamics resulting in strategies that are independent of the node centrality (i.e., agent influence power). On the other hand, the recently published work [START_REF] Varma | Opinion dynamics aware marketing strategies in duopolies[END_REF] considers a similar competition with opinion dynamics over a directed graph but with no budget constraints and by considering the average agents' opinion instead of the final one; these two differences change the problem significantly.

The main contributions of this paper are the followings. We introduce and analyze a new generic model for marketing over social networks. We conduct a complete equilibrium analysis (existence, uniqueness, determination) for the corresponding model. We conduct a numerical performance analysis that allows one, in particular, to obtain very useful insights in terms of investment for the marketers.

Notation. Let R ≥0 := [0, ∞) denote the set of nonnegative real numbers. If f (t) is a lower semi-continuous function at t 0 , we use the notation f (t + 0 ) to imply f (t + 0 ) := lim t→t0,t>t0 f (t). Since we are concerned with a duopoly in this work, for ease of exposition, we will denote by -i when i ∈ {1, 2} is a player index, to refer to the index of the other player, i.e. -i := 1 + i(mod 2).

II. PROBLEM STATEMENT

We consider a market with Firms 1 and 2 that are interested in attracting consumers (referred to as agents) to their product. We consider a set of N agents that continuously interact over a fixed social network. In the sequel we denote by V = {1, 2, . . . , N } the set of agents and the social network is represented by a fixed weighted directed graph (V, E, Ω), with E and Ω respectively representing the set of edges of the graph and the matrix of corresponding weights. To agent n ∈ V we assign a normalized scalar opinion x n (t) ∈ (0, 1) which denotes the opinion in favor of the product or ideas of Firm 1. The revenue obtained by a firm is assumed to be proportional to its average market share. Thus, for agent n at time t ∈ R ≥0 , the revenue of Firm 1 is proportional to x n (t) and for Firm 2 the revenue is proportional to 1 -x n (t). We use x(t) = (x 1 (t), x 2 (t), . . . , x N (t)) to denote the state of the network at any time t, where x(t) ∈ X 0 and X 0 = (0, 1) N . We can define x n;i (t) as the opinion of agent n in favor of Firm i, with x n;1 (t) = x n (t) and x n;2 (t) = 1 -x n (t), i.e., the two firms have competing products.

A. External influence model (through marketing campaigns)

In order to obtain a larger market share, Firm i invests according to the investment or action vector which corresponds to the marketing campaign. Without loss of generality we can consider that the campaign is reduced to a time instant and it has an impulsive instantaneous effect on the opinion of the agents. At the campaign instant, Firm i invests according to the vector a i ∈ A i where the action space for Firm i is

A i := a i ∈ [0, b i ] N | N n=1 a i,n ≤ B i (1)
where b i ≤ B i ∈ R ≥0 for i ∈ {1, 2} represent the maximum influence/discount for one specific agent and the total budget, respectively. The vector a i , i ∈ {1, 2} is called the action of Firm i, with a i,n being the marketing expenditure targeted at agent n. The campaign modify the opinions of agents according to a function Φ(x 0 , a i , a -i ) : X 0 × A i × A -i → X 0 where x 0 = (x 0,1 , ..., x 0,N ) T ∈ X 0 is the vector collecting the initial opinions of the agents before the campaign in favour of Firm i, i.e. x 0 = x(0). Without any loss of generality, we consider that the campaign occurs at t = 0.

In the sequel we consider the function

Φ(x 0;i , a i , a -i ) = (φ(x 0,1;i , a i,1 , a -i,1 ), ..., φ(x 0,N ;i , a i,N , a -i,N )) T with φ(x 0,n;i , a i,n , a -i,n ) = x 0,n;i + a i,n 1 + a i,n + a -i,n
, ∀n ∈ {1, ..., N }.

(2) If x n (t) is seen as the probability of agent n picking the product of Firm 1, φ(•) corresponds to a Bayessian update rule on the opinion as used in [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF]. This probability is updated at the campaign instant t = 0, with a 1,n increasing the odds of choosing Firm 1, and a 2,n increasing the odds of choosing Firm 2. Note that

φ(x n;i (0), a i,n , a -i,n ) = 1 -φ(x n;-i (0), a -i,n , a i,n ),
and therefore, the opinion's change is symmetric w.r.t the two firms. This results in the campaign opinion's change

x n;i (0 + ) = φ(x n;i (0), a i,n , a -i,n ) (3)
for all n ∈ V. The proposed function also satisfies the following properties. If both firms spend very little on agent n, its opinion at 0 is preserved after the campaign as we have

lim ai,n→0,a-i,n→0 φ(x 0,n;i , a i,n , a -i,n ) = x 0,n;i . (4)
Additionally, when the resources allocated to agent n are large by both firms (provided that b i is large), the final opinion depends only on the ratio of investments and not on the initial opinion.

lim ai,n→∞,a-i,n→∞, a -i,n a i,n →c φ(x 0,n;i , a i,n , a -i,n ) = 1 1 + c (5)

B. Internal influence model (within the social network)

After the campaign, the consumer's opinion is only influenced by the other consumers of the networks. In this work we consider that opinion dynamics in the social network is characterized by a linear model described by the following differential equation:

ẋ(t) = -Lx(t) (6)
where L ∈ R N ×N is the Laplacian matrix associated with the graph (V, E, Ω), whose components are defined as:

L m,n =      N n=1 Ω m,n if m = n -Ω m,n if m = n . ( 7
)
As a result of the marketing campaigns, we have the following hybrid opinion dynamics model

ẋ(t) = -Lx(t) ∀t ∈ R ≥0 \ {0} x n (0 + ) = φ(x 0,n , a 1,n , a 2,n ) ∀n ∈ V . (8)

C. Revenue model

In this work, we assume that the profit is based only on the opinion the agents have after some time T > 0. Other profit models such as an integral over time for the opinion have been studied in [START_REF] Varma | Opinion dynamics aware marketing strategies in duopolies[END_REF]. In either case, we observe that the profit can be expressed as a linear combination of the opinions after the campaign. We define the agent influence power (AIP) of Agent n as follows.

Definition 1: The AIP of Agent n is given by ρ n > 0 where

ρ = 1 N exp(-LT ) (9)
where 1 N is a column vector of ones. The net revenue earned by Firm i can therefore be written as the difference between the profit and the marketing expenses resulting in

u 1 (x 0 , a 1 , a 2 ) := γ 1 ρx(0 + ) -λ 1 1 N a 1 , (10)
u 2 (x 0 , a 1 , a 2 ) := γ 2 ρ[1 N -x(0 + )] -λ 2 1 N a 2 . (11)
where x n (0 + ) = φ(x 0,n , a 1,n , a 2,n ), γ i ≥ 0 is the revenue generated per consumer for Firm i, and λ i ≥ 0 is the advertising efficiency or pricing factor for Firm i.

D. Game-theoretic formulation of the problem

The ingredients introduced in this section allow us to formulate the problem as a game under strategic form that is, a triplet which is defined as follows:

G = ({1, 2}, {A 1 , A 2 }, {u 1 , u 2 }) , (12)
where:

• {1, 2} is the set of players (i.e., Firms 1 and 2);

• A i defined in (1)
is the set of pure actions for Player i;

• u i as defined per (10) [START_REF] Arthur | Pricing strategies for viral marketing on social networks[END_REF] is the utility function for Firm i.

Throughout the paper we assume non-aligned utility functions and partial control for the players. In other words, in the game theoretical framework, the meaning of optimality is not clear and there is a need for defining a solution concept for the considered problem (see e.g., [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks : Fundamentals and Applications[END_REF] for further discussion). The solution retained here is the Nash equilibrium (NE) [START_REF] Nash | Non-cooperative games[END_REF], as commonly assumed for duopolies. The definition of a pure NE is as follows.

Definition 2 (Pure NE):

A strategy profile (a 1 , a 2 ) ∈ A 1 × A 2 is a pure NE for G for a given x 0 if ∀i ∈ {1, 2}, ∀a i ∈ A i , u i (x 0 , a i , a -i ) ≥ u i (x 0 , a i , a -i ). (13)

III. GAME-THEORETIC ANALYSIS

This section analyse whether the solution of the problem formulated above exists, is unique and how it can be attained.

A. Nash equilibrium analysis

We start by showing that the game G does have a pure and unique NE. First, we provide some auxiliary lemmas that will help us to characterize the utility function.

Lemma 1: The utility function

u i (x 0;i , a i , a -i ) is concave w.r.t a i .
Proof: Recall that x 0,n;i stands for the initial opinion of agent n w.r.t. Firm i and that x 0,n;i = 1-x 0,n;-i . We evaluate

∂ui ∂ai,n = γiρn 1+ai,n+a-i,n - γiρn(x0,n;i+ai,n) (1+ai,n+a-i,n) 2 -λ i (14)
Next, we evaluate

∂ 2 ui ∂a 2 i,n = - 2γiρn (1+ai,n+a-i,n) 2 + 2γiρn(x0,n;i+ai,n) (1+ai,n+a-i,n) 3 = - 2γiρn(1-x0,n;i+a-i,n) (1+ai,n+a-i,n) 3 (15)
Note that a i,n , a -i,n ≥ 0 and 0 < x 0,n;i < 1 for all i ∈ {1, 2}, n ∈ {1, 2, . . . , N }. Therefore, we have

∂ 2 ui ∂a 2 i,n
< 0 for all n.

We can also easily see that

∂ 2 ui
∂ai,n∂ai,m = 0 for all m = n. The Hessian of the utility function is therefore a diagonal matrix with all entries negative. Therefore,

u i (•) is concave w.r.t. a i ∈ [0, b i ] N .
Next, consider the weighted sum of utilities for the game G for a given initial opinion x 0 defined as σ(a, r) := r 1 u 1 (x 0 , a 1 , a 2 ) + r 2 u 2 (x 0 , a 1 , a 2 ).

(

) 16
for some r 1 , r 2 > 0. We look at the pseudo-gradient of σ(a, r), used by Rosen in [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF], and defined as

g(a, r) = r 1 ∇ a1 u 1 (a), r 2 ∇ a2 u 2 (a) . ( 17
)
This allows us to look at the generalized diagonally strict concavity (DSC) condition [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF], which can be exploited to prove the uniqueness of the NE. Definition 3: A function σ(a, r) is said to satisfy the DSC for a given r > 0 if for every distinct pairs of action profiles a, a , i.e., with (a 1 , a 2 ) = (a 1 , a 2 ), x 0 = x 0 , we have

(a -a ) T (g(a, r) -g(a , r)) < 0. ( 18
)
Lemma 2: The function σ(a, r) satisfies the DSC property w.r.t (a 1 , a 2 ).

Proof: When the utility functions are twice differentiable, a sufficient condition for DSC (see [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF]Th.6]) is that

G(a, r) + G(a, r) T < 0 ( 19
)
where G(a, r) is the Jacobian of g(a, r) w.r.t. (a 1 , a 2 ) and ( 19) means that G(a, r) + G(a, r) T is negative definite. We choose r = 1 γ1 , 1 γ2

and we look at the elements of G(a, r). The diagonal elements are r i

∂ 2 ui ∂a 2 i,n
which are negative as we have already shown in Lemma 1. The off-diagonal elements are in general given by r i ∂ 2 ui ∂ai,n∂aj,m . If m = n, we notice from (14) that ∂ 2 ui ∂ai,n∂aj,m = 0 for any j = i. However, if m = n, then the off-diagonal terms of G at positions (n, N + n) and (N + n, n) for 1 ≤ i ≤ N are non zero and can be evaluated as

1 γ i ∂ 2 u i ∂a i,n ∂a -i,n = ρ n -1 -a -i,n + 2x 0,n;i + a i,n (1 + a i,n + a -i,n ) 3 (20)
Note that

-1 + 2x 0,n;i = 2 -2x 0,n;-i -1 = -(-1 + 2x 0,n;-i ).
Therefore, the term at (n, N + n) of G(a, r) is opposite to the term at (N + n, n). As a result, G(a, r) + G(a, r) T becomes a diagonal matrix with all diagonal entries negative, which is therefore a negative definite matrix. Theorem 1: The game G has a pure and unique NE.

Proof: Notice that the action space A i defined as

a i,n ∈ [0, b i ] with N n=1 a i,n ≤ B i is a convex and compact subset of R N ≥0 .
The utility function is therefore concave w.r.t a i ∈ A i from Lemma 1, with A i being a compact and convex set and is also (jointly) continuous in a. This allows us to use the result in [17, Th.1] and prove that the game G has at least one pure Nash equilibrium. We can use the result in [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF]Th.2] to prove that the NE is unique since the DSC condition shown in Lemma 2 is met if the NE exists.

B. Dynamic characterization of the NE

We have shown that G has a unique pure NE. To evaluate the performance of the two firms at equilibrium it is necessary to determine the NE. While it is not always possible to express the equilibrium actions, it is possible to fully characterize the equilibrium through a set of dynamic equations, which is given next. The corresponding system of equations can either be seen as a way of numerically determining the NE or as a way of modeling the firms economical behavior. Indeed, we propose to exploit the smooth or continuous time bestresponse dynamics introduced in [START_REF] Gilboa | Social stability and equilibrium[END_REF] and used more recently e.g., in [START_REF] Matsui | Best response dynamics and socially stable strategies[END_REF], [START_REF] Hofbauer | Best response dynamics for continuous zerosum games[END_REF]. A continuous-time best-response dynamics is a set of differential equations which allows one to generate a trajectory converging to the NE. It is given by

ȧi,n = β i,n (x 0;i , a -i ) -a i,n (21)
for all i ∈ {1, 2} and n ∈ V. The quantity β i,n (x 0;i , a -i ) corresponds to the best-response, which is defined by: β i (x 0;i , a i ) := arg max ai {u i (x 0;i , a i , a -i )}. We note that ( 21) should be a differential inclusion since the best-response function is in general a set-valued function. However, the argmax operation returns singleton sets (due to strict concavity). By definition, if (a 1 , a 2 ) is a NE of G at x 0;i then

a 1 = β 1 (x 0;1 , a 2 ) , a 2 = β 2 (x 0;1 , a 1 ) (22)
and can be found by computing the unique point in A 1 × A 2 where β i,n (x 0;i , a -i ) -a i,n = 0 holds for all i, n.

Given an action profile a -i , the best-response by Firm i can be evaluated by optimizing u i w.r.t. a i while respecting the budget constraint. Our next proposition gives a method of evaluating β i . Denote β i,n (x 0;i , a -i ) as the n-th component of β i . Then, we have

Proposition 1: The best-response functions are given by

β i,n (x 0;i , a -i ) = min{b i , max{0, α i,n (x 0;i , a -i )}} (23)
where

α i,n (x 0;i , a -i ) = γ i ρ n (x 0,n;-i + a -i,n ) µ 0;i + λ i -1 -a -i,n (24)
for all n ∈ V, and µ 0 ∈ R ≥0 is such that

N n=1 β i,n (x 0;i , a -i ) ≤ B i , µ 0;i ( n β i,n (x 0;i , a -i ) -B i ) = 0
Proof: The optimization problem to be solved in order to evaluate β i can be written as

Maximize ai u i (a i , a -i ) subject to N n=1 a i,n ≤ B i & 0 ≤ a i,n ≤ b i ∀n (25)
Problem (25) necessarily has an optimal solution as u i is continuous and the optimization space is a compact set. Since all the constraint functions are linear, Karush-Kuhn-Tucker (KKT) conditions [START_REF] Boyd | Convex optimization[END_REF] can be applied. Additionally, the problem being convex, KKT conditions are not only necessary but also sufficient conditions for optimality. For all n ∈ {-N, . . . , N } let µ n ≥ 0 be the KKT multipliers. We use µ n for the constraint a i,n ≥ 0, µ -n for the constraint a i,-n ≤ b i for all n ∈ V and µ 0 ≥ 0 as the multiplier for the total budget constraint in (25). Then, the KKT conditions can be written as

                 ∇ ai u i (a i ) = N n=1 -µ n ∇ ai a i,n + µ 0 ∇ ai N n=1 a i,n +µ -n ∇ ai a i,n ≥ 0, a i,n ≤ b i , N n=1 a i,n -B i ≤ 0, µ n , µ -n ≥ 0, ∀n ∈ {-N, . . . , N }, µ n (a i,n -b i ) = 0, µ -n a i,n = 0 ∀n ∈ {1, . . . , N }, µ 0 ( N n=1 a i,n -B i ) = 0.
In order to evaluate ∇ ai u i (a i , a -i ), we have ∂ui(ai,a-i) ∂ai,n

= γ i ρ n x0,n;i+ai,n 1+ai,n+a-i,n -λ i = γ i ρ n x0,n;-i+a-i,n (1+ai,n+a-i,n) 2 -λ i . (26)
As x 0,n;-i and a -i,n are constants, we define d i,n := ρ n (x 0,n;-i + a -i,n ). Thus, the first KKT condition can be now written as

d i,n (1 + a i,n + a -i,n ) 2 = λ 1 + µ 0 + µ n -µ -n (27)
which must be satisfied for all n ∈ V. Let W 0 ⊆ V be the set of agents for which a i,n = 0 which leaves µ -n ≥ 0 free in order to satisfy the KKT condition for n ∈ W 0 . Similarly, let

W 1 ⊂ V such that a i,n = b i for all n ∈ W 1 . Finally, let W 3 := V \ W 1 \ W 0 . Then, we have β i,n (x 0;i , a -i ) =      di,n µ0+λi -1 -a -i,n ∀n ∈ W 2 0 ∀n ∈ W 0 b i ∀n ∈ W 1 (28)
which must be positive. We can use the final complementary slackness condition to solve for µ 0 and get

µ 0 = n∈W2 d i,n B i -b i |W 1 | + |W 2 | + n∈W2 a -i,n 2 -λ i . (29)
Therefore W 2 must be chosen such that 0 ≤ β i,n (a -i ) ≤ b i for all n ∈ V. This gives us (23). We write µ 0;i in the BR function as this parameter is player dependent. Finally, since the problem is concave as shown in Lemma 1, we know that any point in which the KKT conditions are satisfied must also be the global maximum.

Practically, the water level µ 0;i can be found with a lower complexity by first sorting all the agents based on

1+a-i,n √ di,n
. This is because for a given a -i , the agent with a lower value of

1+a-i,n √ di,n
will necessarily have a larger β i,n . This lets us enforce that any agent with 0 resource allocation to have a lower sorting index than the ones based on (24), which in turn will have a lower sorting index than the ones with allocation b i .

C. Expressing the NE

Although we have provided a dynamical characterization of the NE from which a discrete-time iterative algorithm that converges to the NE, we have no insights on how this NE depends on the various key parameters of the problem. In particular, we would like to determine the relationship between the structure of the resource allocation policy at NE, the AIP parameter ρ n , and the initial opinion x 0,n;i . The following proposition shows that the amount of budget allocated to Agent n at NE increases proportionally with ρ n , and will decrease if the initial opinion of Agent n is already in favor of Firm i. The allocation also depends on budget constraints, the profit multiplier γ i , and the advertising efficiency λ i .

Proposition 2: For each n ∈ V, the NE (a 1,n , a 2,n ) is given by

• (y, 0) (or (0, y)) if ∃y ∈ [0, b 1 ] (or [0, b 2 ] respectively)
such that ( 22) is satisfied by one of these pairs, 22) is satisfied by one of these pairs, • or (a 1,n , a 2,n ) ∈ (0, b 1 ) × (0, b 2 ) and is given by

• or (y, b 2 ) (or (b 1 , y)) if ∃y ∈ [0, b 1 ] (or [0, b 2 ] respec- tively) such that (
a i,n = k i k i + k -i 2 k -i ρ n -x 0,n;i , (30)
where k i = γi λi+µ0;i and µ 0;i is a common constant for all n ∈ V given by [START_REF] Singh | Price and quantity competition in a differentiated duopoly[END_REF]. Proof: We observe from ( 22) and ( 23) that if a i,n for some i ∈ {1, 2}, n ∈ V is in the interval (0, b i ), then, it must be equal to (24). Looking at (24), we observe that at NE, we have

a 1,n = k 1 ρ n (1 -x 0,n + a 2,n ) -1 -a 2,n a 2,n = k 2 ρ n (x 0,n + a 1,n ) -1 -a 1,n ⇒ k 1 (1 -x 0,n + a 2,n ) = k 2 (x 0,n + a 1,n ) ⇒ a 2,n = k2 k1 (x 0,n + a 1,n ) -1 + x 0,n (31)
for all n ∈ V such that a i,n ∈ [0, b i ],

where k i = γi λi+µ0;i . Substituting back, we get

k2 k1 (x 0,n + a 1,n ) + x 0,n + a 1,n 2 = k 1 ρ n (x 0,n + a 1,n ) ⇒ (x 0,n + a 1,n ) (k 2 + k 1 ) 2 = k 2 1 k 2 ρ n ⇒ a 1,n = k1 k1+k2 2 k 2 ρ n -x 0,n a 2,n = k2 k1+k2 2 k 1 ρ n -(1 -x 0,n ).
(32) If the resulting x 0,i / ∈ (0, b i ) from (32) for some i, then we have the other two cases of the proposition.

IV. NUMERICAL PERFORMANCE ANALYSIS

For all simulations we fix γ 1 = γ 2 = 1, B 1 = B 2 = 10 and λ 1 = λ 2 = 0.1 implying symmetry between the two firms in advertising efficiency and profit ratios.

A. Network aware marketing versus broadcasting

For a comparison of the proposed graph aware marketing policy with classical policies, we define the uniform budget allocation (UBA) policy, i.e., a broadcast strategy as

a UBA i := B i N . ( 33
)
This strategy is of particular interest as a broadcast strategy is traditionally used by firms to advertise over media such as television or radio, while social media marketing is targeted to particular users but requires some investment in order to learn the initial opinion of users as well as the network structure.

In Fig. 1, we study the gain a player can make by implementing the best-response strategy (23) instead of a UBA strategy with uniform resource allocation. For this simulation, we consider N = 100 with ρ n ∈ {1, C}. This can be interpreted as the AIP of a collection of disconnected star graphs with the internal nodes being the leaders and C representing the influence the leaders have on the rest. If n is a "leader", he will have ρ n = C, and 1 otherwise. We directly consider this configuration for ρ instead of looking at the exact graph structure in order to highlight the message of this numerical example. The resulting difference in utility between the two strategies is referred to as the gain of targeting (GoT), and is measured as

GoT := u 1 (x 0 , β 1 (a UBA 2 ), a UBA 2 ) -u 1 (x 0 , a UBA 1 , a UBA 2 ) u 1 (x 0 , a UBA 1 , a UBA 2 )
.

(34) We take x n (0) = 0.5 for all n ∈ V to remove any bias due to initial opinions. As expected, we observe that a larger disparity in the AIP (C) leads to a larger gain by allocating more resources to the leaders. If there are too few leaders, and C is not large enough (as in C ∈ {5, 10}), this profit saturates resulting in a lower gain.

B. Influence of the initial opinions and graph structure

For our next numerical analysis, we use the graph structure shown in Fig. 2 In Fig. 3, we compare the allocation of budget by the two players at the NE. We observe that if x n (0) is closer to 1, i.e., initially biased towards Firm 1, Firm 2 will invest more to bring it closer to 0 while a starting opinion close to 0 makes Firm 1 invest more. Both firms invest more on agents with a larger AIP ρ n . This allocation corresponds to the inference from Proposition 2.

V. CONCLUSION

In this paper, we introduce a novel static game model which studies the competition between firms trying to capture a market share by advertising over social media. The consumers of the social network are therefore not only under influence of the other consumers of the network but also of the firms. We conduct a complete equilibrium analysis for the proposed game. Our analysis provides concrete insight into how firms should allocate their budget. In particular, the amount of budget a firm should invest is shown under typical conditions to be proportional to a quantity which we define as the agent influence power (AIP). Interestingly, our analysis allows one to quantify the gain of targeting (GoT) i.e., the benefit of implementing a smart allocation policy (based on bestresponse) instead of allocating the available budget uniformly over the consumers. The corresponding gain is clearly shown to be related to the fraction of dominant consumers and the value of their agent influence power. All these encouraging results show the strong interest in developing the proposed framework. One very relevant extension might be given by a stochastic formulation of the problem.

Fig. 1 :

 1 Fig. 1: Gain by implementing the best response strategy over the uniform budget allocation strategy (34) based on the fraction of leaders.

Fig. 2 : 2 Fig. 3 :

 223 Fig. 2: The size of the nodes are scaled based on the AIP ρ n .

  with 15 agents which results in

	ρ = (0.27, 0.37, 0.98, 0.48, 0.59, 1.58, 0.81, 2.30, 1.09, 1.40
	, 0.59, 0.81, 0.81, 1.46, 1.46)

by taking the duration T = 10 and calculating the AIP as ρ = 1 N exp(-10L). We initialize the starting opinions to a random opinion given by x(0) = (0.26, 0.76, 0.82, 0.10, 0.18, 0.26, 0.6, 0.52, 0.34 , 0.18, 0.21, 0.61, 0.68, 0.47, 0.31) T .