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.