Computer programs an aid in making complex bids

Algorithm design creates new negotiating techniques

In electronic commerce it is important to deal with bids like: “If I am awarded contracts 2 and 9 I will give a 5 percent discount.” These so-called combinatorial bids lead to optimization problems that are difficult to solve. But, with the aid of theoretical algorithmic research and knowledge of real-life negotiation situations, it is possible to develop mechanisms that allow a controlled type of combinatorial bidding.

Algorithm design is about constructing computer programs solve problems and carry out tasks rapidly and efficiently. In many cases huge amounts of data and complex issues are involved, where the human brain wouldn’t stand the slightest chance of figuring out the solution.

A clear example can be found in advanced electronic commerce. In a negotiation where a few suppliers are competing for a number of contracts, there are often great advantages in allowing combinatorial bids like: “I want to compete for all ten contracts, but I can only shoulder four of them at most.” If we have a hundred contracts and ten suppliers, the number of possible combinations of suppliers and contracts amounts to 10²⁰.

Combinatorial bidding belongs to a class of problems in which it is extremely difficult to guarantee that you will find a solution in a short time. Generally speaking you cannot even be certain that you will find a good approximate solution. Most researchers believe that sometime in the future it will be possible to prove that no general and rapid algorithm can exist.

Nevertheless, to be able to deal with situations involving these complicated calculation problems, a number of successful approaches can be brought to bear:

• By combining algorithmic methods with knowledge of real-life negotiation situations, it is possible to develop methods that can deal with many types of negotiations in practice.
• Based on research in a number of disciplines, like microeconomics, game theory, and algorithm design, it is possible to develop specially adapted market mechanisms that allow a controlled type of combinatorial bidding. At the same time necessary optimization can be efficiently achieved.

The research being pursued at the Department of Information Technology is not only intellectually stimulating but moreover results in industrial spin-off activities, where methods and techniques have become advanced IT products.

Arne Andersson