(SEP 2020) Dr. Ken Chi Kit FONG, Assistant Professor of CS dept. has successfully got Research Funding from the Research Grant Committee (2020-21) for the following project. It is expected that the project will start in Jan 2019.
Truthful Mechanism Design for Facility Location Game with Agents’ Migration Scheme
*Dr. Ken Chi Kit FONG (PI) Jan 2021-Sep 2022, Assistant Professor, CS dept., CHCHE
*Prof. Wai Lun LO (PI) Sep 2022-Jun 2023, Head of CS dept., Associate Dean FSE, CHCHE
Dr Vincent Chau (Co-I), Assistant Professor, Shenzhen Institutes of Advanced Technology, Chinese Academy of Science
Dr Hau Chan (Co-I), Assistant Professor, University of Nebraska-Lincoln, Lincoln, NE
Research Grant Committee, Hong Kong, Faculty Development Scheme
30 months, HK$ 1,012,003, UGC/FDS13/E01/20
Project Summary – In the proposed research, we consider a general class of facility location problems (FLPs). In FLPs, we have a set of users residing within a set of countable locations (e.g., residential neighborhoods) and a set of public facilities (e.g., parks) that can be located to serve the users. The general aim of the FLPs is to design efficient mechanisms that elicit preferences from the users (e.g., users’ locations) and decide the optimal placement of the facilities to minimize some predetermined objectives (e.g., the transportation time among all users to the located facilities). Typically, the designed mechanism is known to all the users. As a result, all users understand how the mechanism operates, and the users can potentially benefit (i.e. minimize his transportation cost) by reporting false information (e.g., reporting location that is different from the resided location). Therefore, our aim is to design mechanisms to locate the facilities to prevent the users from misreporting their information as well as optimally place the facilities to minimize some objectives.
FLP has been well studied in social choice literature, and majority of the studies focus on the setting on single stage, where the mechanism only makes a single-period decision to place the facility according to the users’ preference. However, in many real-world scenarios, it is possible that the mechanism makes decisions in multiple rounds/periods such that the facilities may be relocated to some other locations over time. Let us consider one scenario where we have several ice-cream vendors from the same company located on the beach. Over time, the beach may be visited by a number of customers, and the customers’ locations may vary from time to time. Naturally, the customers would like to pick the closest vendor to buy ice-creams. If we only make a single decision to place the vendors in a fixed location, the vendors may lose their customers over time as their locations can be far away from the customers (who move over time) when time changes. Therefore, in this scenario, in order to maximize the profit throughout the day, multiple stages are required (e.g., the ice-cream vendors need to change their locations over time). In the example above, it is possible that not all of the customers will be served (e.g., due to limited supplies). In this project, we will consider an extra constraint of capacity and aim to model the scenario below.
Assume that we have a long and narrow street where several bus stops are located on the street in order to pick up the citizens to work. The demand of the usage of the bus may vary from time to time (e.g., there will be higher demand during the rush hour). Throughout the day, a bus may arrive in an interval of 15~30 minutes with limited seats. If the number of citizens is more than the number of the seats of the bus, then some of the citizens may need to wait for the bus in the next round. From the perspective of the citizens, they would like to have more buses in order to guarantee that they can get on the bus to work as soon as possible. From the perspective of the government, sending more buses may cause traffic jams on the road and wasting resources if the buses are not fully loaded. Therefore, the government wants to send the minimum number of buses in order to handle the demand.
The objective of this project is to develop new models by introducing capacity constraints in the FLPs with multiple stages. Our ultimate goal is to design truthful mechanisms that determine the optimal placement of facilities to minimize the total waiting time and walking distance in the bus stop scenario over time.
