Sequential Online Chore Division for Autonomous Vehicle Convoy Formation
This addresses fair task allocation in dynamic systems like autonomous vehicle convoys, but it is an incremental extension of chore division to online settings.
The paper tackles the problem of fairly dividing an undesirable task among participants who arrive and depart online, proposing three mechanisms for sequential online chore division. Results show that the mechanisms achieve load balancing with reduced switching costs in autonomous vehicle convoy scenarios.
Chore division is a class of fair division problems in which some undesirable "resource" must be shared among a set of participants, with each participant wanting to get as little as possible. Typically the set of participants is fixed and known at the outset. This paper introduces a novel variant, called sequential online chore division (SOCD), in which participants arrive and depart online, while the chore is being performed: both the total number of participants and their arrival/departure times are initially unknown. In SOCD, exactly one agent must be performing the chore at any give time (e.g. keeping lookout), and switching the performer incurs a cost. In this paper, we propose and analyze three mechanisms for SOCD: one centralized mechanism using side payments, and two distributed ones that seek to balance the participants' loads. Analysis and results are presented in a domain motivated by autonomous vehicle convoy formation, where the chore is leading the convoy so that all followers can enjoy reduced wind resistance.