Combinatorial Auctions are an attractive application of intelligent agents; their applications are countless and are shown to provide good revenues. In a combinatorial auction, bidders can bid not only on single items, but also on sets of items; in this way, bidders can express complementarity of the goods offered in the auction. On the other hand, the computational complexity of the solving process (the Winner Determination Problem, WDP) is NP-hard; this delayed their practical use. Recently, efficient solvers have been applied to the WDP, so the framework starts to be viable. A second issue, common also to many other 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: malicious agents must be found, and their violations discovered. The SOCS project addresses such issues, and provided a language, the social integrity constraints, for defining the allowed interaction moves, together with a proof-procedure (called SCIFF) able to detect violations. In this paper we show how to write a protocol for the combinatorial auctions by using social integrity constraints. In the devised protocol, the auctioneer interacts with an external solver that finds a solution to the winner determination problem. In an extension of this scenario, the auctioneer may not embed a solver certified by the society, but use an internal, undisclosed one. In such a case, checking that the allocation provided by the auctioneer is indeed optimal is a $NP$-hard task, and cannot be addressed efficiently by a general purpose solver as the one embedded in the SCIFF proof-procedure. We propose some architectures and protocols that, again interacting with an external auction solver, can be used to check that the auctioneer provides indeed optimal allocations.

Applicazione dei vincoli di integrità sociali come strumento di specifica delle interazioni in aste combinatorie

ALBERTI, Marco;GAVANELLI, Marco;LAMMA, Evelina;
2005

Abstract

Combinatorial Auctions are an attractive application of intelligent agents; their applications are countless and are shown to provide good revenues. In a combinatorial auction, bidders can bid not only on single items, but also on sets of items; in this way, bidders can express complementarity of the goods offered in the auction. On the other hand, the computational complexity of the solving process (the Winner Determination Problem, WDP) is NP-hard; this delayed their practical use. Recently, efficient solvers have been applied to the WDP, so the framework starts to be viable. A second issue, common also to many other 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: malicious agents must be found, and their violations discovered. The SOCS project addresses such issues, and provided a language, the social integrity constraints, for defining the allowed interaction moves, together with a proof-procedure (called SCIFF) able to detect violations. In this paper we show how to write a protocol for the combinatorial auctions by using social integrity constraints. In the devised protocol, the auctioneer interacts with an external solver that finds a solution to the winner determination problem. In an extension of this scenario, the auctioneer may not embed a solver certified by the society, but use an internal, undisclosed one. In such a case, checking that the allocation provided by the auctioneer is indeed optimal is a $NP$-hard task, and cannot be addressed efficiently by a general purpose solver as the one embedded in the SCIFF proof-procedure. We propose some architectures and protocols that, again interacting with an external auction solver, can be used to check that the auctioneer provides indeed optimal allocations.
2005
Alberti, Marco; Chesani, F; Gavanelli, Marco; Guerri, A; Lamma, Evelina; Mello, P; Torroni, P.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11392/1204286
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact