Expressing interaction in combinatorial auction through social integrity constraints

Combinatorial auctions are an interesting application of in- telligent 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 Determina- tion 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 detect violations. In this paper we show how to write a protocol for combinatorial auc- tions 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.