995. Condorcet Stable Set: Optimizing Decision-making in Facility Location
Invited abstract in session HE-22: Combinatorial Optimization & Game Theory , cluster Game Theory and Operations Management.
Thursday, 16:15-17:45Room: FENH202
Authors (first author is the speaker)
| 1. | Xujin Chen
|
| Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences | |
| 2. | Changjun Wamg
|
| Academy of Mathematics and Systems Science, Chinese Academy of Sciences | |
| 3. | Chenhao Wang
|
| Advanced Institute of Natural Sciences, Beijing Normal University (Zhuhai) |
Abstract
In a facility location problem, k facilities are to be built to serve spatially distributed customers, but who decides the locations to choose for building the facilities? Different approaches place the decision in the hands of different groups or individuals. In a central planning approach, the central authority enforces a (near) optimal solution according to some system objective. In a market approach, the facilities (i.e., facility managers) play a game for selecting their own locations and return a Nash equilibrium. In a democratic approach, the customers collectively make the decision. We propose a novel solution concept for the democratic approach, called Condorcet stability. A solution, i.e., a set of selected locations, is Condorcet Stable (CS) if no unselected candidate location is more popular than any selected one. Focusing on the setting with customers continuously distributed on a network, we first give a string of existence results on CS solutions. Most notably, when the number k of facilities is large enough, we provide a characterization of CS solutions, leading to an efficient algorithm for finding the solution. We measure the efficiency of CS solutions w.r.t. the minimum total cost of all customers, using the standard terms of Price of Anarchy and Price of Stability, both upper bound with small constants.
Compared with the market approach, our democratic approach is more likely to achieve a desirable solution of higher efficiency. Compared with the central planning approach, CS solutions are naturally more stable and fair for the customers, and their efficiency is very close to the optimum, even in the worst case. Therefore, the customers in the scheme of Condorcet stability are better decision-makers for balancing the efficiency, stability, fairness, and tractability of facility locations.
Keywords
- Combinatorial Optimization
- Facilities Planning and Design
Status: accepted
Back to the list of papers