Incentive Engineering through Subgraph Matching – with Application to Task Allocation

This work was presented at HAIDM 2015. The 2015 workshop on Human-Agent Interaction Design and Models was co-organised by SmartSociety.

Abstract: We use provenance graphs to solve a problem within incentive engineering: motivating humans to accept proposals generated by agents. Across several provenance graphs created within the HAC-ER disaster-management system, we ran retrospectively a bespoke algorithm for subgraph matching in order to extract narrative information from the provenance data. The output of the algorithm comprised a series of text messages which, had they been generated at the time of the disaster trial, would have been transmissable with the specific intention of encouraging participants not to reject certain tasks.

The algorithm found all expected subgraphs within the provenance graphs, on an any-time basis and in a time linearly proportional to the number of nodes. Our algorithm is extendable to other situations in which agents present tasks to humans.

Keywords: Incentive engineering, subgraph matching, task allocation, human-agent collectives, provenance graphs, disaster management.

Citation: Mark Ebden, Trung Dong Huynh, Luc Moreau and Stephen Roberts. Incentive Engineering through Subgraph Matching – with Application to Task Allocation.


About P. Andreadis

Pre-Doctoral Research Assistant in AI and Social Computation @ University of Edinburgh.

Leave a Reply