Abstract. Combinatorial auctions are an interesting application of intelligent agents. They let the user express complementarity relations
among the items for sale, and let the seller obtain higher revenues. On
the other hand, the solving process, the so-called Winner Determination Problem (WDP) is NP-hard. This restricted the practical use of the framework, because of the fear to be, in some WDP instances, unable to
meet reasonable deadlines. Recently, however, efficient solvers have been
proposed, so the framework starts to be viable.
A second issue, common to many agent systems, is trust: in order for an
agent system to be used, the users must trust both their representative
and the other agents inhabiting the society. The SOCS project addresses
such issues, and provided a language, the social integrity constraints, for
defining the allowed interaction moves, and a proof-procedure able to
In this paper we show how to write a protocol for combinatorial auctions by using social integrity constraints. In the devised protocol, the
auctioneer interacts with an external solver for the winner determination
problem. We also suggest extensions of the scenario, with more auctions
in a same society, and suggest to verify whether two auctions interact.
We also apply the NetBill protocol for the payment and delivery scheme.