Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2309.16914 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917761859452928 |
|---|---|
| author | Aarts, Sander Dentes, Jacob Wu, Manxi Shmoys, David |
| author_facet | Aarts, Sander Dentes, Jacob Wu, Manxi Shmoys, David |
| contents | We consider the problem of fairly allocating the cost of providing a service among a set of users, where the service cost is formulated by an NP-hard {\it covering integer program (CIP)}. The central issue is to determine a cost allocation to each user that, in total, recovers as much as possible of the actual cost while satisfying a stabilizing condition known as the {\it core property}. The ratio between the total service cost and the cost recovered from users has been studied previously, with seminal papers of Deng, Ibaraki, \& Nagomochi and Goemans \& Skutella linking this {\it price-of-fair-sharing} to the integrality gap of an associated LP relaxation. Motivated by an application of cost allocation for network design for LPWANs, an emerging IoT technology, we investigate a general class of CIPs and give the first non-trivial price-of-fair-sharing bounds by using the natural LP relaxation strengthened with knapsack-cover inequalities. Furthermore, we demonstrate that these LP-based methods outperform previously known methods on an LPWAN-derived CIP data set. We also obtain analogous results for a more general setting in which the service provider also gets to select the subset of users, and the mechanism to elicit users' private utilities should be group-strategyproof. The key to obtaining this result is a simplified and improved analysis for a cross-monotone cost-allocation mechanism. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_16914 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Bounding the Price-of-Fair-Sharing using Knapsack-Cover Constraints to guide Near-Optimal Cost-Recovery Algorithms Aarts, Sander Dentes, Jacob Wu, Manxi Shmoys, David Computer Science and Game Theory We consider the problem of fairly allocating the cost of providing a service among a set of users, where the service cost is formulated by an NP-hard {\it covering integer program (CIP)}. The central issue is to determine a cost allocation to each user that, in total, recovers as much as possible of the actual cost while satisfying a stabilizing condition known as the {\it core property}. The ratio between the total service cost and the cost recovered from users has been studied previously, with seminal papers of Deng, Ibaraki, \& Nagomochi and Goemans \& Skutella linking this {\it price-of-fair-sharing} to the integrality gap of an associated LP relaxation. Motivated by an application of cost allocation for network design for LPWANs, an emerging IoT technology, we investigate a general class of CIPs and give the first non-trivial price-of-fair-sharing bounds by using the natural LP relaxation strengthened with knapsack-cover inequalities. Furthermore, we demonstrate that these LP-based methods outperform previously known methods on an LPWAN-derived CIP data set. We also obtain analogous results for a more general setting in which the service provider also gets to select the subset of users, and the mechanism to elicit users' private utilities should be group-strategyproof. The key to obtaining this result is a simplified and improved analysis for a cross-monotone cost-allocation mechanism. |
| title | Bounding the Price-of-Fair-Sharing using Knapsack-Cover Constraints to guide Near-Optimal Cost-Recovery Algorithms |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2309.16914 |