Junior Management Science, Volume 4, Issue 1, March 2019, 1-34

Extending Kolkata Paise Restaurant Problem to Dynamic Matching in Mobility Markets

Layla Martin, Technische Universität München (Masterarbeit)

Abstract
In mobility markets – especially vehicle for hire markets – drivers offer individual transportation by car to customers. Drivers individually decide where to go to pick up customers to increase their own utilization (probability of carrying a customer) and utility (profit). The utility drivers retrieve from customers comprises both costs of driving to another location and the revenue from carrying a customer and is thus not shared between different drivers. In this thesis, I present the Vehicle for Hire Problem (VFHP) as a generalization of the Kolkata Paise Restaurant Problem (KPRP) to evaluate different strategies for drivers in vehicle for hire markets. The KPRP is a multi-round game model presented by Chakrabarti et al. (2009) in which daily laborers constitute agents and restaurants constitute resources. All agents decide simultaneously, but independently where to eat. Every restaurant can cater only one agent and agents cannot divert to other resources if their first choice is overcrowded. The number of agents equals the number of resources. Also, there is a ranking of restaurants all agents agree upon, and no two resources yield the same utility. The VFHP relaxes assumptions on capacity and utility: Resources (customers) are grouped in districts, agents (drivers) can redirect to other resources in the same district. As the distance between agent and resource reduces the agent’s utility and the location is not identical for all agents, the utility of a given resource is not identical for all agents. To study the impact of the different assumptions, I build four different model variants: Individual Preferences (IP) replaces the shared utility of the KPRP with uniformly distributed utilities per agent. The Mixed Preferences (MP) model variant uses the utility assumption of the VFHP, but the capacity of all districts remains 1. The Individual Preferences with Multiple Customers per District (IPMC) model variant groups customers in districts, and uses the uniform utilities introduced in the IP model variant. Mixed Preferences and Multiple Customers per District (MPMC) implements all assumptions of the VHFP. In this thesis, I study different strategies for the KPRP and all variants of the VFHP to build a foundation for an incentive scheme for dynamic matching in mobility markets. The strategies comprise history-dependent and utility-dependent strategies. In history-dependent strategies, agents incorporate their previous decisions and the utilization of resources in previous iterations in their decision. Agents adapting utility-dependent strategies choose the resource offering the highest utility with a given probability.

Keywords: vehicle for hire markets; distributed decision making; agent-based modelling; congestion game; limited rationality