Les Agents intelligents de négociation en Commerce

Les Agents intelligents de négociation en Commerce

Électronique

Abdeltouab Belbekkouche

Université de MontréalDépartement d’Informatique et de Recherche Opérationnelle

Cours: Traitement des Connaissances, IFT6261

Professeure: Esma Aïmeur

Le, 22 mars 2006

Les Agents intelligents de négociation en Commerce Électronique

2

PlanIntroduction

La négociation et le Commerce Électronique

Les Techniques de conception des agents de négociation

Le profil de l’agent de négociation

Conclusion


3

L’Agent Intelligent(1)Difficile à définir

Relatif au domaine d’utilisationAppellations commerciales qui ajoutent la confusion

Concept ancien mais domaine de recherche d’actualitéEliza: un agent de bavardage conçu en 1966 au MITAujourd’hui: dans le Commerce Électronique, la simulation, les réseaux de communication, etc.Demain: l’assistant qui remplace son utilisateur (peut être?)

DÉFINITION: Un agent électronique est une entité logicielle capable d’agir de manière autonome dans le but d’accomplir un certain nombre de tâches au nom de son utilisateur et en fonction de ses intérêts (Paraschiv 2004)


4

L’Agent Intelligent(2)Caractéristiques:

IntelligenceAutonomieRéactivitéPro-activitéContinuité dans le tempsInteractionAdaptabilitéEt d’autres (mobilité, anthropomorphisme, etc.)

Un système multi-agents : a network of multiple agents that interact with one another (Durfee 1989)


5

Le Commerce ÉlectroniqueToute forme de transactions commerciales ou administratives ou d’échange d’informations qui sont effectués en utilisant un moyen de la technologie d’information et de communication (He 2002)

Deux types essentiels:Business-to-Business (B2B): transactions électroniques entre organisationsBusiness-to-Consumer (B2C): achat sur Internet, par téléphone, etc.

La majorité du CÉ d’aujourd’hui est de type B2B

Mais le B2C se développe rapidement grâce à Internet


6

Les Agents Intelligents en CÉLe modèle du processus d’achat en ligne (Guttman 1998) :

Trois types d’agents sur le Marché:Agents de recommandation: recherche du produitAgents de recherche: recherche du vendeurAgents de négociation: négociation des termes de la transaction

Recherche du produit

Identification d’un besoin

Recherche du vendeur Négociation

Achat et livraison

Service après-vente

et évaluation


7

PlanIntroduction




Conclusion


8

La négociationLe processus par lequel les agents communiquent entres eux en essayant de parvenir à un accord mutuellement acceptable (Wooldrige 2003)

Les agents de négociation peuvent être:Coopératifs: but commun à satisfaire entre les agents

Égocentriques: but individuel à satisfaire


9

Espace de la négociation La négociation comme un problème de recherche distribuée (Jennings 2001)


10

Les composantes de la négociation Cardinalité des interactions:

Un-à-unUn-à-plusieursPlusieurs-à-plusieurs

Objet de la négociationÀ attribut unique (prix, garantie, date de livraison, etc.)Multi-attributsFixe ou changeant (ajouter un attribut intéressant à un négociateur ou supprimer un attribut qui empêche de parvenir à un accord)

Protocole: règles d’interaction entre les agents, les états et les actions de la négociation

Stratégie: modèle de prise de décision et de raisonnement propre à l’agent pour satisfaire ses objectifs


11

Le protocole de négociationLes règles d’interaction incluent:

Agents autorisés à participer: leur nombre et le rôle de chacunÉtats possibles: ouverture, accord, clôture, etc.Évènements de transition entre états: délai maximum écoulé, offre acceptée, etc.Actions valides des participants à un état donné: proposer une offre, accepter, rejeter, contre-proposer, etc.

Varier ces règles permet d’obtenir un nombre énorme de protocoles


12

Les protocoles des enchèresLes plus populaires et les plus étudiés parmi les protocoles de négociationOffrent un cadre simple, bien défini et utile pour la négociation entre agents égocentriquesExemples

Anglaisesous plis scellésVickreyHollandaiseL’enchère double continue: échange des offres entre plusieurs vendeurs et plusieurs acheteurs.


13

La stratégie de négociationPlan d’actions qu’un agent doit suivre pour atteindre son objectif (maximiser son gain)

Plusieurs stratégies peuvent être compatibles avec un protocole donné (la stratégie dépend du protocole).

Dépend des caractéristiques des agents (rôles, connaissances, rationalité) et de l’environnement (statique ou dynamique)

Plusieurs stratégies peuvent être utilisées dans une seule négociation (dynamiquement ou statiquement)


14

Le mécanisme de négociationUn protocole + une stratégie = Un mécanisme

Il doit (tant que possible) vérifier les caractéristiques suivantes (Wooldrige 2003) :

L’efficacité de calculL’efficacité de communicationLa rationalité IndividuelleLa distribution du calculL’efficacité Pareto


15

Exemple

Interactions: Un-à-unL’objet: un seul attribut (le prix) au départ mais l’agent vendeur

lui ajoute une dimension (2 nuits d’hôtel)

Agent A (vendeur)

Agent B

(Acheteur)

Négociation sur le prix d’un billet d’avion

600 $

700 $ + 2 nuits d’hôtel

OK


16

Les contratsAllocation des tâches, bande passante dans les réseaux de communication, ordonnancement du processus de fabrication, etc.Exemple: Le protocole Réseau Contractuel (Contract Net)

Source: [URL 1]


17

Les chaînes d’approvisionnementUn système auto-organisé constitué de membres géographiquement dispersés, indépendants et entre lesquels il existe une relation de confiance mutuelle (Xiaohong 2005)

Source: [URL 2]

Formation d’une chaîne optimale en terme de coût et de délaiUtilisation des agents de négociation (des systèmes multi-agents)


18

Exemple: Kasbah La première place de marché qui utilise des agents de négociation (1996)

Deux types d’agents: acheteurs et vendeurs

Un utilisateur doit définir:La durée maximale de négociationLe prix désiré d’achat ou de venteLe prix maximal/minimal d’achat ou de venteLa fonction définissant la stratégie de négociation

Stratégies fixes de négociation, pas d’apprentissage


19

Exemple: Tête-à-TêteObjet de négociation multi-attributs : Prix + valeurs ajoutéesNégociation entre plusieurs agentsÉchanges d’offres, contre-offres et d’arguments entre l’agent acheteur et les agents vendeurs

Actuellement, utilisé dans Frictionless Commerce:

Source: [URL 3]


20

Exemple: ADEPT (1)Développé pour British Telecom pour fournir des devis de conception de réseaux pour les clients (Jennings 2000)

Négociation orientée services avec plusieurs agents

Négociation d’un contrat et des pénalités de sa violation

Une stratégie d’un agent est constituée de trois familles de tactiques:

Dépendantes du tempsDépendantes des ressourcesImitatives


21

Exemple: ADEPT (2)


22

PlanIntroduction




Conclusion


23

La théorie des jeux Modèles économiques utilisés pour formaliser et analyser l’interaction entres des agents rationnels

Portent sur les concepts de stabilité:Stratégie dominanteÉquilibre de NashLe bien être social

Suppose la rationalité parfaite des agents et que cette rationalitésoit connue par tous les autres agents

Nécessitent une grande puissance de calcul pour trouver la stratégie optimale

Exemple: La stratégie Zeuthen


24

Exemple: MCP et ZeuthenMCP: Monotonic Concession Protocol

La négociation se déroule sur des étapesÀ une étape, un agent ne peut que proposer la même offre ou une offre meilleure pour son opposant

Zeuthen: porte sur le concept du risque calculé par l’agent i àl’étape t de la façon suivante:

Cette stratégie n’est pas en équilibre Nash: un agent peut se reposer sur l’autre agent pour faire la concession à la dernière étape

⎪⎩

⎪⎨

⎧

−

=

=Sinon

utilityutilityutility

utilitySirisk

tii

tji

tii

tii

ti

)()()(

0)(1

δδδ

δ

L’agent qui a le plus de risque de ne pas atteindre un accord doit faire la concession minimale qui change l’équilibre


25

Les heuristiquesModèles informatiques qui cherchent à trouver une bonne solution plutôt que la solution optimale

Les agents ont une rationalité limitée et ne cherchent pas àexplorer l’espace complet des stratégies

Deux types:Approximations des modèles de la théorie des jeuxUtilisations de règles simples inspirées du comportement humain

Exemple: les agents de Kasbah et ADEPT


26

Le Raisonnement à Base de Cas (1)

Nouveau cas

Nouveau cas

Nouveau cas

Nouveau cas

Cas le plus

Similaire

Cas le plus

Similaire

CasPrécédentsCas

PrécédentsCasPrécédents

Connaissance générale

CasRésolue

CasRésolue

Solution obtenue

Problème

Vérification, Correction du

Cas

Vérification, Correction du

Cas

Cas ApprisCas Appris

Solution confirmée

Source: (Plaza 1994)


27

Le Raisonnement à Base de Cas (2)Utilisation des cas de négociation similaires pour déterminer la stratégie à suivre à l’étape suivanteExemple d’un cas (Wong2000):

But: générer la meilleure concession dans l’étape suivante de la négociation

Profil de l’acheteur Profil du vendeur Profil de la voiture d’occasion

Épisode Offre du vendeur Concession du vendeur

Contre-offre de l’acheteur

Concession de l’acheteur

1 O1 Co1

2 O2 V%1 Co2 A%1

3 O3 V%2 Co3 A%2

4 O4 V%3 Co4 A%3

… … … … …

Informations sur le résultat


28

Le Raisonnement à Base de Cas (3)D’autres travaux plus récents proposent un cycle du RBC plus adapté au commerce électronique (Sun 2005):

Aucune application à un domaine concret.


29

Les réseaux bayésiens (1)Se basent sur le théorème de bayes:

Supposent l’existence de liens de causalité entre des évènements interdépendants

Bien adaptés à des situations de négociation où les informations sur l’opposé sont incomplètes ou incertaines

Efforts de calcul relativement modestes

)()|()()|()|(

1 nn n

KKk APABP

APABPBAP∑ ≥

=


30

Les réseaux bayésiens (2)Exemple: le système Bazaar (Sycara 98)

Prédire la valeur de réservation de l’agent vendeur notée V

Hypothèses: H1: V=100$ et H2: V=90$

P(H1)=0.5 et P(H2)=0.5

Connaissance sur le domaine : le vendeur donne un prix supérieur à V de 17%

e1: L’agent acheteur demande 117$ P(e1|H1)= 0.30 et P(e1|H2)=0.05

Supposant que le vendeur demande effectivement 117$ : en utilisant la règle de Bayes P(H1|e1)= 0.85 et P(H2|e1)= 0.14


31

Les algorithmes génétiques (1)Abstraction de l’évolution biologique qui offre l’adaptation en faisant évoluer une population de chromosomes par des opérations de sélection naturelle, de croisement et de mutation.

Croisement

Source: [URL4]


32

Les algorithmes génétiques (2)Exemple (Lau 2006):

Un chromosome est une offre potentielle

Les meilleurs chromosomes par rapport à l’agent lui-même et à son opposant seront regénérés dans la prochaine population

Gènes

Id. offre Fitness 2000-4000 1000-2000 10-30

Prix Quantité Livraison


33

Évaluation des différentes techniques (1)Technique Points forts Points faibles

Théorie des jeux - Cadre formel- Conception facile

- Complexité de calcul- Manque d’adaptation

et d’apprentissage- Difficilement adaptable au cas d’un objet multi-attributs

Heuristiques - Mécanisme simple- Proches du comportement humain

- Peu d’adaptation et d’apprentissage


34


Raisonnement àBase de Cas

- Utilisation des expériences passées

- Représentation des cas- Initialisation de la base de cas

Réseaux bayésiens

- Cas des informations incertaines et incomplètes

- Nécessite des connaissances sur le domaine- Problème de la construction des dépendances conditionnelles


35


Algorithmes génétiques

- Efficacité de calcul- Objet de négociation complexe

- La population initiale- Choix des fonctions de fitness et d’utilité


36

PlanIntroduction




Conclusion


37

Le profil de l’agent de négociation (1)Le profil de l’agent est souvent constitué du profil de son utilisateur et de la valeur de réserve.

Il existe aussi des agents comportementauxComportement conciliantComportement boulwareComportement imitatif

Le comportement des agents actuels se résume dans leur tendance à faire des concessions.

Or, le processus de négociation est plus complexe que ça


38

Le profil de l’agent de négociation (2)Le processus de négociation est constitué de (Bourque2002):

Un diagnostic de la situation et la décision d’engager une négociationLa négociation d’une formuleLa négociation des détails

Les agents de négociation de demain doivent être capables de traiter ces étapes (pour former une chaîne d’approvisionnement optimale par exemple)

Prédire le comportement d’un agent à partir de son profil sera très intéressant pour la négociation


39

PlanIntroduction




Conclusion


40

Conclusion Les agents intelligents vont jouer un rôle important dans le commerce électronique de la deuxième génération

Les agents de négociation vont permettre la détermination des prix des produits suivant la règle de l’offre et la demande

Les agents de négociations vont permettre de former des chaînes d’approvisionnement optimales

Les agents qui offrent l’apprentissage et l’adaptation sont meilleurs dans le contexte des places de marchés ouverts


41

Tendances futuresAméliorer les modèles de la théorie des jeux et leurs approximations

Étudier les performances des algorithmes génétiques

Utiliser le RBC dans tout le processus d’achat en ligne avec des agents intelligents

L’acquisition des préférences de l’utilisateur par l’agent de négociation

L’utilisation des ontologies pour la communication entre les agents de négociation


42

RéférencesBourque, R. and C. Thuderoz (2002). Sociologie de la négociation, LA DECOUVERTE.Durfee E, Lesser V (1989) Negotiating task decomposition and allocation using partial global planning.

Distributed Articial Intelligence 2: 229-244He, M. and H.-f. Leung (2002). "Agents in E-Commerce : State of the Art " Knowledge and Information

Systems 4: 257-282.Guttman, R., A. Moukas, et al. (1998). "Agent-mediated Electronic Commerce: A Survey." Knowledge

Enginneering Review 13(2): 147-160Lomuscio, A. R., M. Wooldrige, et al. (2003). "A classification scheme for negotiation in electronic

commerce." Int Journal of Group Decision and Negotiation 12(1): 31-56.Paraschiv, C. (2004). Les agents intelligents pour un nouveau commerce électronique, Hermès.Zeng, D. and K. Sycara (1998). "Bayesian Learning in Negotiation." Int. J. Human- Computer Studies

48: 125-141.Wong, W. Y., D. M. Zhang, et al. (2000). Negotiating with Experience. KBEM''00, Austin, TX.Xiaohong, L., Y. Danjie, et al. (2005). Design and Implementation of Negotiation Agent of Dynamic

Supply Chain. Proceedings of The Third International Conference on Information Technology and Applications.

N. R. Jennings, P. Faratin, T. J. Norman, P. O'Brien, B. Odgers and J. L. Alty (2000) "Implementing a Business Process Management System using ADEPT: A Real-World Case Study" Int. Journal of Applied Artificial Intelligence 14 (5) 421-465.

Aamodt, A. and E. Plaza (1994). "Case-Based Reasoning: Foundational Issues, Methodological Variations, and System Approaches." AICom - Artificial Intelligence Communications 7(1): 39-59.

[URL 1] http://turing.cs.pub.ro/auf2/html/chapters/chapter5[URL 2] http://www.theprogressgroup.com/[URL 3] www.frictionless.com[URL 4] http://www.chez.com/produ/badro/

http://turing.cs.pub.ro/auf2/html/chapters/chapter5

http://www.theprogressgroup.com/

http://www.frictionless.com/

http://www.chez.com/produ/badro/


43

Ressources bibliographiques International Journal of Electronic Commerce International Journal of Intelligent Systems ACM Trans on Internet Technology

International Journal of Human Computer Studies

AAMAS: conference on Autonomous Agents and Multi-Agent Systems IEEE/WIC/ACM International Conference on Intelligent Agent Technology Workshop on Agent Mediated Electronic Commerce Workshop on Game Theoretic and Decision Theoretic Agents

Documents

Les Agents intelligents de négociation en Commerce