A family of strategyproof mechanisms for activity scheduling
Recent years have seen various designs of strategyproof mechanisms in the facility location game and the obnoxious facility game, by considering the facility’s geo-location as a point in the spatial domain. In this paper, we extend this point to be a continuous interval, and study a novel activity s...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/173340 |
| _version_ | 1811693296218537984 |
|---|---|
| author | Xu, Xinping Zhang, Jingwen Li, Minming Duan, Lingjie Xie, Lihua |
| author2 | School of Electrical and Electronic Engineering |
| author_facet | School of Electrical and Electronic Engineering Xu, Xinping Zhang, Jingwen Li, Minming Duan, Lingjie Xie, Lihua |
| author_sort | Xu, Xinping |
| collection | NTU |
| description | Recent years have seen various designs of strategyproof mechanisms in the facility location game and the obnoxious facility game, by considering the facility’s geo-location as a point in the spatial domain. In this paper, we extend this point to be a continuous interval, and study a novel activity scheduling game to schedule an activity in the normalized time domain [0, 1] based on all agents’ time reports for preferences/conflicts. The activity starts at time point y and lasts for a fixed time period of d with 0 ≤ d≤ 1 . Each agent i∈ N= { 1 , ⋯ , n} wants his preferred time interval [ti, ti+ li] to be close to or overlap with the activity interval [y, y+ d] . Since agents are heterogeneous, we consider each agent i has weight αi or βi when the activity is scheduled after or before his time interval, respectively. Thus each agent i’s cost is his weight (αi or βi) multiplied by the time difference between his time interval [ti, ti+ li] and the activity interval [y, y+ d]. The social cost is the summation of all agents’ costs. In this game, agents’ preferred time intervals [ti, ti+ li] ’s are private information and they may misreport such information to the social planner. Our objective is to choose the activity starting time y so that the mechanisms are strategyproof (i.e., all agents should be truthful to report ti ’s and li ’s) and perform well with respect to minimizing the social cost. We design a mechanism outputting an optimal solution and prove that it is group strategyproof. For the objective of minimizing the maximum cost among agents, we design another strategyproof mechanism with the approximation ratio 1 + min { α/ β, β/ α} when αi= α, βi= β for i∈ N, and prove it is the best strategyproof mechanism. In the obnoxious activity scheduling game, each agent prefers his conflicting time interval [ti, ti+ li] to be far away from the activity interval [y, y+ d] . We design deterministic and randomized group strategyproof mechanisms, and compare their provable approximation ratios to the lower bounds. Finally, we consider the cost/utility of each agent as a 0-1 indicator function and find group strategyproof mechanisms for minimizing the social cost and maximizing the social utility. |
| first_indexed | 2024-10-01T06:49:25Z |
| format | Journal Article |
| id | ntu-10356/173340 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:49:25Z |
| publishDate | 2024 |
| record_format | dspace |
| spelling | ntu-10356/1733402024-01-29T02:03:37Z A family of strategyproof mechanisms for activity scheduling Xu, Xinping Zhang, Jingwen Li, Minming Duan, Lingjie Xie, Lihua School of Electrical and Electronic Engineering Engineering::Electrical and electronic engineering Activity Scheduling Strategyproof Mechanism Recent years have seen various designs of strategyproof mechanisms in the facility location game and the obnoxious facility game, by considering the facility’s geo-location as a point in the spatial domain. In this paper, we extend this point to be a continuous interval, and study a novel activity scheduling game to schedule an activity in the normalized time domain [0, 1] based on all agents’ time reports for preferences/conflicts. The activity starts at time point y and lasts for a fixed time period of d with 0 ≤ d≤ 1 . Each agent i∈ N= { 1 , ⋯ , n} wants his preferred time interval [ti, ti+ li] to be close to or overlap with the activity interval [y, y+ d] . Since agents are heterogeneous, we consider each agent i has weight αi or βi when the activity is scheduled after or before his time interval, respectively. Thus each agent i’s cost is his weight (αi or βi) multiplied by the time difference between his time interval [ti, ti+ li] and the activity interval [y, y+ d]. The social cost is the summation of all agents’ costs. In this game, agents’ preferred time intervals [ti, ti+ li] ’s are private information and they may misreport such information to the social planner. Our objective is to choose the activity starting time y so that the mechanisms are strategyproof (i.e., all agents should be truthful to report ti ’s and li ’s) and perform well with respect to minimizing the social cost. We design a mechanism outputting an optimal solution and prove that it is group strategyproof. For the objective of minimizing the maximum cost among agents, we design another strategyproof mechanism with the approximation ratio 1 + min { α/ β, β/ α} when αi= α, βi= β for i∈ N, and prove it is the best strategyproof mechanism. In the obnoxious activity scheduling game, each agent prefers his conflicting time interval [ti, ti+ li] to be far away from the activity interval [y, y+ d] . We design deterministic and randomized group strategyproof mechanisms, and compare their provable approximation ratios to the lower bounds. Finally, we consider the cost/utility of each agent as a 0-1 indicator function and find group strategyproof mechanisms for minimizing the social cost and maximizing the social utility. 2024-01-29T02:03:36Z 2024-01-29T02:03:36Z 2023 Journal Article Xu, X., Zhang, J., Li, M., Duan, L. & Xie, L. (2023). A family of strategyproof mechanisms for activity scheduling. Autonomous Agents and Multi-Agent Systems, 37(2). https://dx.doi.org/10.1007/s10458-023-09624-7 1387-2532 https://hdl.handle.net/10356/173340 10.1007/s10458-023-09624-7 2-s2.0-85174499223 2 37 en Autonomous Agents and Multi-Agent Systems © 2023 Springer Science+Business Media, LLC, part of Springer Nature. All rights reserved. |
| spellingShingle | Engineering::Electrical and electronic engineering Activity Scheduling Strategyproof Mechanism Xu, Xinping Zhang, Jingwen Li, Minming Duan, Lingjie Xie, Lihua A family of strategyproof mechanisms for activity scheduling |
| title | A family of strategyproof mechanisms for activity scheduling |
| title_full | A family of strategyproof mechanisms for activity scheduling |
| title_fullStr | A family of strategyproof mechanisms for activity scheduling |
| title_full_unstemmed | A family of strategyproof mechanisms for activity scheduling |
| title_short | A family of strategyproof mechanisms for activity scheduling |
| title_sort | family of strategyproof mechanisms for activity scheduling |
| topic | Engineering::Electrical and electronic engineering Activity Scheduling Strategyproof Mechanism |
| url | https://hdl.handle.net/10356/173340 |
| work_keys_str_mv | AT xuxinping afamilyofstrategyproofmechanismsforactivityscheduling AT zhangjingwen afamilyofstrategyproofmechanismsforactivityscheduling AT liminming afamilyofstrategyproofmechanismsforactivityscheduling AT duanlingjie afamilyofstrategyproofmechanismsforactivityscheduling AT xielihua afamilyofstrategyproofmechanismsforactivityscheduling AT xuxinping familyofstrategyproofmechanismsforactivityscheduling AT zhangjingwen familyofstrategyproofmechanismsforactivityscheduling AT liminming familyofstrategyproofmechanismsforactivityscheduling AT duanlingjie familyofstrategyproofmechanismsforactivityscheduling AT xielihua familyofstrategyproofmechanismsforactivityscheduling |