| This dissertation investigates the technologies used to solve the problems of coordination under untrusted environment (CUT) and coordination under uncertainty (CUC), i.e., the mechanisms that encourage self-interested agents to cooperate and the algorithms that search optimal coordination strategies when individual agents have little information about environments and other agents. It strives to acquire general ideas and methods out of the interdisciplinary research on several apparently discrepant, though inherently correlated case problems: trust and reputation, safe exchange, denial-of-service attacks and multiagent learning.; Research on CUT problems explores the synergy between mechanism design theory and computer security. In the design of a coordination mechanism, security provides building blocks, such as cryptographic primitives, over which a mechanism designer enforces a game to inspire agents to follow the protocols. This treatment could tackle the CUT problems difficult to solve within a single discipline. Specifically, this dissertation research examines the design of an equilibrium reputation mechanism for discouraging merchants from cheating customers, the development of a general model for analyzing safe exchange mechanisms, and the creation and implementation of a puzzle auction primitive for countering denial-of-service attacks. Moreover, bridging the gap between mechanism design and security helps shed light on the limitations of current research on CUT problems, and suggests future research directions to individual disciplines. For example, this dissertation presents a possibility/impossibility theory for safe exchange mechanism design.; Research on CUT problems is closely related to learning. Mechanism design and game theory make strong assumptions about knowledge of environments and other agents' strategies, which is not readily available to individual agents or mechanism designers in many practical systems. Research on machine learning offers effective means of estimating such information from experience. This dissertation research investigates learning techniques that support mechanism design. It describes an algorithm for adjusting the parameters of an equilibrium reputation mechanism. More importantly, the dissertation research studies the optimal coordination strategy for individual agents. It proposes a new learning algorithm that guarantees to converge to an optimal coordination policy in any team Markov games, even when individual agents perceive independent noisy payoff signals and do not know game structures before play. |
