Self Reordering for security in generalized english auctions (GEA)

Distributed approaches to negotiation have special privacy properties as main advantage over existing centralized/cryptographic techniques: The problem of an agent only has to be revealed according to the needs of the negotiation. After a negotiation has closed, the agents know how much they have communicated and therefore they know an acceptable upper-bound on their privacy loss due to the search.In this article we first introduce Generalized English Auctions, a large class of negotiations that can be addressed naturally by distributed algorithms. It is then shown how a security problem found in existing protocols can be solved by enabling a certain dynamic reordering schema. We have introduced a technique allowing to add dynamic reordering to existing asynchronous complete search algorithms that have polynomial space requirements. Several recent developments of this technique are shortly mentioned.