Coalition formation among rational agents in uncertain and untrustworthy environments

Abstract

Multiagent coalition formation based on cooperative game theory is a means to let rational software agents cooperate to increase their benefits. When applied in open environments, a number of problems arise that are not well coped with by existing approaches. Some specific problems are addressed: - Uncertainty: in open environments, agents often do not have complete knowledge. In this thesis, it is shown how to form coalitions efficiently by modeling uncertainty as fuzzy numbers. Simulation results are provided. Additionally, a method for coalition formation is proposed which is shown to form stable coalitions with guaranteed risk bounds. - Defrauding or unreliable agents: it might be expected in open environments that some agents try to unsolicitedly increase their own profits at the cost of others by deception, or are generally unreliable. In this thesis, we combine a trust measure based approach with cryptographic techniques to obtain payment and communication protocols that are shown to hamper successful deception. - Privacy preservation: most approaches require agents to reveal a considerable amount of information to each other, such as individual costs and valuations of certain outcomes. This might be unacceptable when personal, financial or other delicate data is concerned. To this end, the (to our best knowledge) first privacy preserving coalition formation algorithm is proposed.

Auf kooperativer Spieltheorie basierende Koalitionsbildung in Multiagentsystemen ermöglicht es rationalen Softwareagenten, zu kooperieren um ihren Nutzen zu erhöhen. Wenn dies in offenen Umgebungen stattfindet, ergeben sich einige Probleme. In dieser Arbeit geht es speziell um: - Unsicherheit: in offenen Umgebungen haben Agenten oft nur unvollständige Information. Gezeigt wird, wie sich mit unscharfen Koalitionswerten effizient Koalitionen bilden lassen, und es werden Simulationsergebnisse präsentiert. Weiter wird eine Methode vorgestellt, mir der sich stabile und garantiert risikobegrenzende Koalitionen bilden lassen. - Betrügerische und unverlässliche Agenten: in offenen Umgebungen ist zu erwarten, dass einige Agenten versuchen, ihren Profit auf Kosten anderer unberechtigterweise zu steigern. Andere könnten unzuverlässig sein. Es wird gezeigt, wie ein Vertrauensmodell mit kryptographischen Techniken verbunden werden kann, sodass ein erfolgreicher Betrug erschwert wird. - Wahrung der Privatsphäre: viele Koalitionsbildungsverfahren verlangen von den Agenten, umfangreiche Informationen auszutauschen, z.B. individuelle Kosten und Bewertungen von möglichen Ergebnissen. Es kann jedoch ein Problem sein, wenn persönliche, finanzielle oder andere heikle Daten verlangt werden. Für solche Situationen wird der (nach unserem besten Wissen) erste privatsphärensichernde Koalitionsbildungsalgorithmus vorgestellt.