Trust oriented decision making via POMDPs

Trust has been recognized as a vital concept in open MultiAgent Systems (MASs), where autonomous agents interact with each other in order to fulfil their designed objectives. In MASs, agents often need to rely on the abilities, competencies or knowledge of other agents (whose intentions are often unknown) for the fulfilment of their own goals. By relying on others, agents place their own interests at risk, as the other agents may be self-interested, diverse or deceptive, thus introducing the need for trust. In these scenarios, agents can evaluate the trustworthiness of potential interaction partners, using which they can make decisions about whom to interact with. While we see that it is necessary for agents to decide whose trustworthiness should be evaluated, which agent should be chosen as an interaction partner, etc., it is also vital to make these decisions in an optimal manner, as every agent strives towards maximizing its utility in the system. In this thesis, we address the problem of optimal decision making in MASs which are based on trust relationships. Specifically, we formulate solutions for multiagent e-marketplaces and Wireless Sensor Networks (WSNs), which are uncertain environments, where agents need to make decisions with partial or limited information about others. For example, in e-markets, buying agents need to decide which seller to buy from with limited information about the sellers and advisors (to whom the buyers can ask for opinions about the sellers). Similarly, in WSNs, sensor nodes need to select a good quality next-hop neighbor in order to successfully deliver packets to the destination. We use Partially Observable Markov Decision Processes (POMDPs) to model these problems as they provide a framework for sequential decision making under uncertainty. Also, POMDPs can effectively balance the trade-off between exploration actions (to determine the trustworthiness of agents) and exploitation actions (to decide interaction partners), providing optimal solutions which maximize the utility of the agents. This thesis is mainly comprised of three studies: (1) we propose a POMDP based approach, referred to as the Seller & Advisor seLEction (SALE) POMDP, to optimally select sellers by selectively querying advisors in e-marketplaces. SALE POMDP enables optimal trade-offs of the expected benefit and cost of obtaining more information (about the sellers and advisors), aiming to maximize the total utility of the buying agent. Extensive evaluation on the ART testbed demonstrates that SALE POMDP balances the cost of obtaining and benefit of more information more effectively, leading to more earnings, than the other state-of-the-art approaches; (2) we propose a hierarchical POMDP approach, called the Secure Routing POMDP (SRP), for nodes in WSNs that need to choose a suitable next-hop neighbor to route packets. SRP can effectively balance the trade-off between gathering more information about the sensor nodes to address the security issues in WSNs, and deciding the next-hop neighbor with available information. Evaluation in a simulated as well as a real testbed shows that SRP can successfully route packets (even in the presence of various attacks), in an energy-efficient manner than other trust-based routing schemes; (3) we formulate the Mixture of POMDP Experts (MOPE) technique to improve the scalability of POMDPs when applied to trust-based domains. The MOPE approach divides the large decision making problem modelled as a POMDP into a multitude of computationally tractable smaller (sub)-POMDPs, each containing a subset of agents. The actions of the sub-POMDPs are then aggregated, to find the best action in the process of selecting a good interaction partner. Experiments show that MOPE can improve the scalability of the SALE POMDP up to a hundred agents in the e-marketplace domain as well as that of SRP up to forty agents in the WSN domain. In summary, we propose mechanisms to solve optimal decision making problems using POMDPs in trust-based domains, i.e., SALE POMDP for the e-marketplace domain and Secure Routing POMDP for the sensor network domain. We have also proposed the Mixture of POMDP Experts technique to address the scalability issue in solving POMDPs, especially when they are applied to domains which have a similar trust propagation structure as multiagent e-marketplaces and wireless sensor networks.Doctor of Philosophy (SCE