We consider semi-decentralised fair divisions in the context of emerging VRPs, where not just the preferences of drivers play a crucial role, but also the feasibilities of their vehicles. For such settings, we propose three new fairness notions: responsive FEF1, responsive FEQX, and responsive FEFX, which capture the responsiveness of drivers for requests. For such settings, we also give two new algorithms. Our first algorithm returns responsive FEF1 assignments. Our second algorithm returns responsive FEQX assignments, as well as responsive FEFX assignments in a practical case.

Realistic features such as feasibilities and responsiveness require that we modify centralised fairness notions and centralised fairness algorithms so that they reflect the nature of our model. We do such modifications in our work. Our model can thus be simulated in centralised, decentralised, as well as on various Internet and mobile settings, where some request information is known and some missing information is revealed as drivers are prompted for responses. If drivers respond, then they are online. Otherwise, they are offline until the next time they are prompted for responses. For example, the dispatchers of Bonds Express often communicate for work with drivers via SMS messages (Aleksandrov et al. 2013). We next give an outline of our paper.

Outline: We explain our contributions in Section 2 and review related literature in Section 3. We define formally our model in Section 4. For this model, in Sections 5, 6, and 7, we show that existing fairness notions such as EF1, EQX, and EFX need to be modified. In response, we propose three new notions: responsive FEF1, responsive FEQX, and responsive FEFX. With driver-dependent costs, we prove in Section 8 that a responsive FEF1 assignment can be computed in polynomial time and in Section 9 that a responsive FEQX assignment can also be computed in polynomial time. With driver-independent costs, we give in Section 10 a similar tractability result for a responsive FEFX assignment. Finally, we draw our conclusions in Section 11.