Algorithms for recursive delegation

Article type: Research Article

Authors: Afanador, Juan^{a; *} | Baptista, Murilo S.^b | Oren, Nir^a

Affiliations: [a] Department of Computing Science, University of Aberdeen, Scotland, UK. E-mails: r01jca16@abdn.ac.uk, n.oren@abdn.ac.uk | [b] Department of Physics, University of Aberdeen, Scotland, UK. E-mail: murilo.baptista@abdn.ac.uk

Correspondence: [*] Corresponding author. E-mail: r01jca16@abdn.ac.uk.

Abstract: Task delegation is essential to many applications, ranging from outsourcing of work to the design of routing protocols. Much research in computational trust has been devoted to the generation of policies to determine which agent should the task be delegated to, given the agent’s past behaviour. Such work, however, does not consider the possibility of the agent delegating the task onwards, inducing a chain of delegation events before the task is finally executed. In this paper, we consider the process of delegation chain formation, introducing a new algorithm based on quitting games to cater for recursive scenarios. We evaluate our proposal under various network topologies, consistently demonstrating its superiority with respect to recursive adaptations of existing multi-armed bandit algorithms.

Keywords: Trust, delegation

DOI: 10.3233/AIC-190616

Journal: AI Communications, vol. 32, no. 4, pp. 303-317, 2019