Performance of Software Agents in Non-Transferable Payoff Group Buying

Abstract

Les agents logiciels peuvent être utiles pour la formation de groupes d'acheteurs puisque les humains ont beaucoup de difficultés à trouver des transactions Pareto-optimales (aucun acheteur ne peut être mieux sans qu'un autre soit pire) dans les situations de négociation. Alors, quelles sont les performances informatiques et économiques des agents logiciels pour un problème de négociation particulier? Nous donnons une première réponse à cette question pour un problème de groupement d'acheteurs. Du point de vue de la théorie des jeux, ce problème est équivalent à la formation de coalitions avec gain non-transférable (le cas général). La recherche antérieure sur la formation de coalitions permettait le transfert de gain entre agents ce qui est un cas spécial. Nous argumentons que la Pareto-optimalité est un bon concept de solution pour ce problème. La formation de coalitions peut être décomposée en deux parties ayant une grande complexité de calcul : déterminer l'ordre de préférence parmi tous les groupes d'acheteurs possibles de chaque agent et trouver la meilleure structure de coalitions. Pour la première partie, nous avons trouvé une restriction raisonnable au problème permettant une réduction du nombre de groupes d'acheteurs à ordonner d'un facteur exponentiel à un facteur linéaire en fonction du nombre d'acheteurs. Pour la deuxième partie, nous cherchons à savoir par une évaluation empirique si les incitatifs à se regrouper (un gros groupe obtient un prix unitaire inférieur à un petit groupe) créent une structure spéciale rendant possiblement le problème plus facile sur le plan calculatoire. Nous évaluons un protocole de négociation pour agents logiciels que nous avons développé pour voir si le problème est difficile en moyenne et pourquoi. Ce protocole trouve assurément une solution Pareto-optimale qui minimise la pire distance à l'idéal parmi tous les agents étant donné des listes de préférences sans égalité. Notre évaluation démontre que la consommation de l'espace en mémoire et non le temps d'exécution limite les performances des agents logiciels dans ce problème de groupement d'acheteurs. De plus, nous cherchons à savoir si les agents logiciels suivant ce protocole ont le même comportement d'acheteurs que des humains dans la même situation. Les résultats démontrent que les agents logiciels ont un comportement plus différent (et meilleur car ils peuvent toujours simuler le comportement habituel des humains qui est d'acheter seul leur produit préféré) lorsqu'ils ont des préférences similaires dans l'espace des produits disponibles. Nous discutons également du type de la différence de comportement et de sa fréquence en fonction de la situation.

Software agents (SA) could be useful in forming buyers' groups since humans have considerable difficulty in finding Pareto-optimal deals (no buyer can be better without another being worse) in negotiation situations. Then what are the computational and economical performances of SA for a particular negotiation problem? In this article, we try to give a first answer to this question for a group buying problem. From the game theory point of view, the problem is equivalent to coalition formation (CF) with non-transferable payoff (the general case). Prior research in CF has allowed payoff to be transferred between agents, which is a special case. We argue that Pareto-optimality is a good solution concept to this problem. CF can be decomposed into two computationally difficult components : determining a preference ordering among all possible buying groups for each SA and finding the best coalition structure. For the first component, we have found a reasonable restriction to the group buying problem allowing the reduction of the number of possible buying groups to be ordered from a exponential to a linear factor in function of the number of buyers. For the second component, we try to investigate by an empirical evaluation if incentives to regroup (a bigger group pays less than a smaller one) create a special structure which possibly makes the problem computationally easier. We evaluate a negotiation protocol for SA that we developed to see if the problem is difficult on the average and why. This protocol provably finds a Pareto-optimal solution and furthermore, minimizes the worst distance to ideal among all SA given preference ordering without equality. This evaluation demonstrates that memory requirements and not execution time complexity limit the performance of SA in this group buying problem. Furthermore, we investigated if SA following the developed protocol had a different buying behaviour than the customer they represented would have had in the same situation. Results show that SA have a greater difference of behaviour (and a better behaviour since they can always simulate the obvious customer behaviour of buying alone their preferred product) when they have similar preferences over the space of available products. We also discuss the type of behaviour changes and their frequencies based on the situation.