IDEAS home Printed from
MyIDEAS: Log in (now much improved!) to save this paper

Performance of Software Agents in Non-Transferable Payoff Group Buying

Listed author(s):
  • Frederick Asselin
  • Brahim Chaib-draa
Registered author(s):

    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. 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.

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

    File URL:
    Download Restriction: no

    Paper provided by CIRANO in its series CIRANO Working Papers with number 2003s-40.

    in new window

    Length: 36 pages
    Date of creation: 01 Jun 2003
    Handle: RePEc:cir:cirwor:2003s-40
    Contact details of provider: Postal:
    1130 rue Sherbrooke Ouest, suite 1400, Montréal, Quéc, H3A 2M8

    Phone: (514) 985-4000
    Fax: (514) 985-4039
    Web page:

    More information through EDIRC

    References listed on IDEAS
    Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:

    in new window

    1. Arvind Rangaswamy & G. Richard Shell, 1997. "Using Computers to Realize Joint Gains in Negotiations: Toward an "Electronic Bargaining Table"," Management Science, INFORMS, vol. 43(8), pages 1147-1163, August.
    2. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, July.
    Full references (including those not matched with items on IDEAS)

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    When requesting a correction, please mention this item's handle: RePEc:cir:cirwor:2003s-40. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Webmaster)

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    This information is provided to you by IDEAS at the Research Division of the Federal Reserve Bank of St. Louis using RePEc data.