11institutetext: Cornell University, Ithaca NY 14850, USA 11email:
<EMAIL_ADDRESS>

# Sharing the Cost of IoT Wireless Coverage with a Strengthened Linear
Programming Formulation††thanks: This material is based on work supported by
the NSF under Grant CNS-1952063.

Sander Aarts 11 Manxi Wu 11 David B. Shmoys 11

###### Abstract

Sharing infrastructure between many users is often advantageous, however
finding a fair and reasonable way to allocate its cost between its users can
be challenging. This is particularly true for LPWANs, a popular Internet of
Things solution for wirelessly connecting devices to the internet. We study
cost-allocation of LPWANS using a covering integer program. Standard cost-
allocation methods are inapplicable in this model, because the integrality gap
of its natural LP-relaxation is unbounded. We overcome this challenge by
strengthening the natural LP with knapsack-cover inequalities. Our main result
is proving that all dual-feasible solutions to the strengthened LP produce
cost-allocations that satisfy the core property. This reduces the problem of
finding a cost-allocation to that of finding a strengthened-LP-relative
approximation algorithm. Existing algorithms imply improved cost-recovery
ratios for families of sparse CIP instances. Finally, we show that the
strengthened formulation simplifies and improves the analysis of a cross-
monotone cost-allocation mechanism as well.

###### Keywords:

Cost sharing IoT Covering problems Computational social choice

##  1 Introduction

It is often beneficial for a group of users to share infrastructure. However,
finding a fair and reasonable way to allocate the costs of shared
infrastructure between users can be challenging. For instance, the last decade
has seen wireless communication networks for the Internet of Things (IoT)
proliferate, now connecting countless wireless devices to the internet. While
there are many heterogeneous IoT protocols, such as Low-Power Wide-Area
Networks (LPWANs) including LoRaWAN, Sigfox, and NB-IoT, most require
considerable investment in specialized wireless infrastructure, particularly
wireless receivers that demodulate radio transmissions from the Things and
pass them on as data to the Internet. Building and maintaining receivers is a
major cost-driver. Indeed, some LPWAN applications require coverage from
multiple receivers in order to ensure adequate robustness and reception rates.
Meanwhile, these wireless receivers can typically support large volumes of
traffic, far in excess of what a single user requires [11]. Therefore, sharing
the network among multiple users is among the most effective means to ensure
sufficient service quality and lower per-user costs, provided a mutually
beneficial cost-sharing scheme can be orchestrated.

The cost of IoT coverage is shared in drastically differnet ways by a diverse
cast of network operators. There are large shared IoT networks operated by
for-profit companies, non-profits, as well as municipal organizations, each
employing different cost-sharing structures. For LoRaWAN alone, operators
include private connectivity-as-a-service providers such as KPN that charge a
subscription, to municipal networks funded by taxpayers, to crowd-sourced
free-to-use sharing solutions such as The Things Network. Despite this
diversity, little research has been conducted cost-sharing in IoT networks,
and in particular the incentives and computational challenges underlying the
problem of IoT network design and cost-sharing. This paper formulates a model
for IoT wireless coverage provision, and studies the computational aspects of
cost-sharing in LPWANS.

We model the wireless coverage provision problem as a covering integer program
(CIP). The model contains a set of $m$ users, and a set of $n$ potential
wireless receivers, or facilities. Users have heterogeneous service
requirements $\mathbf{r}\in\mathbb{R}^{m}$; some user may need multiple one
receiver to satisfy their requirements. Facilities have costs
$\mathbf{c}\in\mathbb{R}^{n}$, and each facility-user pair has a contribution
$a_{ij}$ that specifies the amount of coverage facility $i$ provides user $j$
if opened. These are collected in the $n\times m$ matrix $\mathbf{A}$. The
objective is to minimize cost, subject to providing sufficient coverage.

$\displaystyle
c^{*}=\min\\{\mathbf{c}^{T}\mathbf{x}:\mathbf{A}\mathbf{x}\geq\mathbf{r},\
\mathbf{x}\in\\{0,1\\}^{n}\\}$ (1)

The binary decision variables $x_{i}\in\\{0,1\\}$ indicate whether facility
$i$ is opened or not111Some formulations of CIPs permit multiplicity
constraints $x_{i}\in\\{1,2,\dots,d_{i}\\}$ for any integers $d_{i}$,
including infinity. It is straightforward to extend our results this setting..
If inputs $\mathbf{A}$ and $\mathbf{r}$ are binary, the CIP reduces to the set
cover problem; if $\mathbf{A}$ and $\mathbf{r}$ are integral, they form a
multi-set multi-cover instance. Finding an optimal solution is computationally
hard [13, 12]. However, there are approximation algorithms that find near-
optimal solutions to the general problem [5, 7, 19].

The goal of this work is twofold: efficiently solve the above problem, and
allocate the cost of a solution to the served users in a fair and stable
manner. Our focus is on cost-allocations that satisfy the core property. These
are well-understood concepts in cost-sharing, with strong ties to
infrastructure economics [17, 28]. We say a cost-allocation satisfies the core
property if no group of served users is allocated more cost than what it would
minimally cost the group to provide coverage for themselves. This is a minimal
requirement to make users want the service. If the users’ valuations are
unknown, there is often interest in cross-monotone cost-allocations which can
be used to elicit them via a bidding mechanism [26]. A cost-allocation is
cross-monotone whenever no existing user is allocated more cost, upon an
additional user joining the network. An operator’s goal is to maximize the
cost recovered subject to satisfying the core property. A cost allocation is
$\alpha$-budget-balanced if the cost charged to the users add up to at least
an $\alpha$-fraction of the cost.

Cost allocation in CIPs is challenging due to the presence of multi-cover
constraints and variable contributions. Without multi-cover requirements, cost
allocation is well-understood via linear programming duality [9]. For
instance, for the set cover problem, the dual variables produce cost-shares
satisfying the core property that recover $1/\ln(n)$ of the cost. This bound
is tight; the duality gap for set cover is $\ln(n)$, and any cost-shares
satisfying the core property can be shown to be dual variables. Indeed, it is
considered folklore that one can recover at most a fraction $\alpha$ of the
cost whenever the integrality gap of the natural LP relaxation is $1/\alpha$.
The CIP is in direct contradiction with this understanding. On the one hand,
there is an algorithm that produces cost-allocations that recover at least
$1/(1+\ln(n+1))$ of the cost, without explicitly using duality [24]. On the
other hand, the integrality gap of CIP is unbounded [5]. This is at odds with
the folklore, and invites the question what of role, if any, duality has in
sharing the cost of CIP solution.

This paper develops a general method for finding provably optimal cost
allocations for the CIP via the dual of a strengthened linear programming
formulation. Key to our approach are knapsack-cover inequalities that
strengthen the linear programming formulation and its dual, shrinking the
integrality gap [5]. This LP formulation underlies many state-of-the-art
approximation algorithms for CIP [5, 6, 7, 19]. Our main result proves that
all dual-feasible solutions to the strengthened LP produce cost-allocations
that satisfy the core property. These cost-allocations are optimal, in that
they attain the maximum cost-recovery ratio on sub-problems an upper-bound is
know. Moreover, our framework reduces the problem of finding cost-allocations
to that of finding a strengthened-LP-relative approximation algorithm. By
invoking known results for CIP approximation algorithms, this immediately
implies improvements over the best existing cost-recovery ratio for families
sparse CIP instances. Finally, we also employ the strengthened LP formulation
to connect the analysis of Li et al.’s [24] algorithm for group strategyproof
cost-allocations to LP-duality, radically simplifying their proof, and
improving the cost-recovery ratio on instances with bounded coverage per
facility.

##  2 Background and model

This section covers, respectively, background on IoT networks and LPWANs, our
cost-sharing model in the context of LPWANs, background on cost-sharing in
covering problems, and knapsack-cover inequalities. The first subsection can
be skipped in case IoT is not of interest. The subsection on knapsack-cover
inequalities, however, is critical to understanding our results.

###  2.1 LoRaWAN particulars

Low-Power Wide-Area Networks (LPWANs) are a popular IoT solution for
connecting devices to the internet over long distances using little power.
LoRaWAN one of the most widely used LPWAN protocols; see e.g., Alumhaya et al.
[1] for an overview. LoRaWAN is designed for the transmission of small packets
of data from battery-driven sensors to wireless receivers called gateways.
These forward the data to the internet over a broadband backhaul [31]. LoRaWAN
applications include road-surface monitoring, sensing fill-levels of municipal
garbage containers, and tracking livestock locations, which are used to,
respectively, inform safe traffic routing, optimize garbage pickup, and reduce
costs of livestock monitoring, respectively. While LoRaWAN is the primary
motivating application of this work, the covering integer program we study is
quite general, and therefore applicable to other technologies, not to mention
problems entirely divorced form wireless networks and IoT.

A property of LoRaWAN that is particularly relevant to cost-sharing are its
low barriers to entry. Specifically, LoRaWAN uses the ISM band of the wireless
spectrum [31]. This is an unlicensed band; anyone can operate a gateway free
of charge, without a license or certification. Secondly, LoRaWAN gateways are
relatively inexpensive, with some models costing just a few hundred US
dollars. While the cost of carrier-grade gateways that support large volumes
of traffic can be higher, individuals or small groups of users can serve their
own needs at relatively low costs. Finally, organizations such as TTN provide
open-source software and free online support for managing the server and
software end of LoRaWAN networks, which further increases accessibility.
Altogether, these low barriers give users considerable leverage over the cost
of wireless coverage. This is in stark contrast with other wireless
technologies and natural monopolies, such as 5G, that require costly licenses
and hardware.

Another unique and critical feature of LoRaWAN is the use of redundant
gateways for improving the quality of coverage. LoRaWAN is association-free,
in that a single device does not transmit to any particular receiver [31].
Instead, transmissions are broadcast to all receivers, and demodulated by each
one that successfully receivers the packet. Duplicates are pruned in hindsight
by the network server. This feature is critical for achieving robustness
through redundancy; a transmitted packet is lost only if all receivers fail to
demodulate it. Studies on LoRaWAN connectivity find that transmissions often
fail at random, but the success rate varies predictably with distance,
terrain, and wireless parameters [2, 3, 29]. By being covered by multiple
gateways, the probability of packet loss can be kept minimal despite
individual connections frequently failing. The CIP model accommodates user
reception rate requirements, gateway redundancy, and heterogeneity in
connection qualities.

###  2.2 A covering integer program

We model the problem of LoRaWAN coverage provision as covering integer program
(CIP). The model is quite general, and captures many covering problems in
which there are additive multi-cover requirements. The main model components
are facilities, users, and the contributions of each facility to each user.
Let $\mathcal{F}$ denote a set of $n$ facilities; these are sites at which a
receiver can be installed. Each facility has a positive installation cost,
$\mathbf{c}=(c_{1},\dots,c_{n})$. Costs represent hardware and installation
costs, as well as amortized rents and expenses. Let $\mathcal{U}$ denote a set
of $m$ users. These can be viewed as individual devices, or as representative
points for small areas, that require service. The service requirements
$\mathbf{r}=(r_{1},\dots,r_{m})$ are positive real numbers that specify the
minimum quality of service at which each user $j$ is satisfied. Each facility
contributes specified amount of coverage, $a_{ij}\geq 0$ to each user. This
captures heterogeneous connection qualities typical to LoRaWAN. We denote by
$\mathbf{A}$ the $n\times m$ matrix of connectivities; $A_{i}$ denotes the
$i$th column, and $\mathbf{a}_{j}=(a_{1j},\dots,a_{nj})$ the $j$th row. The
tuple $(\mathbf{A},\mathbf{c},\mathbf{r})$ defines a CIP instance. Finally,
let $\Gamma$ denote the row-sparsity; the maximum number of non-zero entries
of any row of $\mathbf{A}$, and $\Delta$ the corresponding column-sparsity.

The objective in the covering integer program is to provide sufficient
coverage to all users at minimum cost. The linear programming (2.2) relaxation
of the problem is

$\displaystyle\min_{x}~{}\sum_{i\in F}c_{i}$ $\displaystyle x_{i}$
$\displaystyle\text{s.t. }\sum_{i\in F}a_{ij}$ $\displaystyle x_{i}\geq
r_{j},$ $\displaystyle\forall j\in U,;$ (LP) $\displaystyle 0\leq\ $
$\displaystyle x_{i}\leq 1,$ $\displaystyle\forall i\in\mathcal{F},$

where the variables $x_{i}$ indicate whether facility $i$ is purchased or not.
The model assumes that the cost, and the total contribution to each user, are
additive in the opened facilities. The constraints $x_{i}\leq 1$ are
multiplicity constraints; these prohibit the purchase of a facility multiple
times. Solving a CIP to optimality is computationally hard. Even when the
requirements are $1$ and contributions $a_{ij}$ are binary, the problem is a
set cover problem, which is NP-hard and inapproximable within a factor of
$c\ln(n)$ of the optimum, for any $c<1$, under standard complexity assumptions
[12, 13].

The additive coverage constraints in the CIP can capture requirements in terms
of packet reception probabilities via a simple reduction. Assume that the
successful reception from user $j$ to facility $i$ is a binary variable, with
given success, or reception, rate $\rho_{ij}$. In this case, one can view
coverage provision as a fuzzy set cover problem. Chian, Hwang, and Liu [8]
reduce fuzzy set covering to a CIP. Assume that failures of links are
independent, and let $\mathbf{x}=(x_{1},\dots,x_{n})$ be a binary vector
encoding a subset of built facilities $F\subseteq\mathcal{F}$. Then the
failure rate of a transmission from user $j$ is

$\Pr[\text{Failure}\mid F]=\prod_{i\in\mathcal{F}}(1-\rho_{ij})^{x_{i}}.$

Taking logarithms this yields an expression that is additive in the variables
$x_{i}$.

$\log\Pr[\text{Failure}\mid x]=\sum_{i\in\mathcal{F}}\log(1-\rho_{ij})x_{i}$

A constraint limiting the maximum packet error rate can therefore be expressed
as a covering constraint in the CIP. While independence is a strong
assumption, this reduction adds intuition to the CIP, and can be viewed as a
stylized approximation to a dependent system, e.g., by choosing more
“pessimistic” estimates for $\rho_{ij}$, or higher service requirements
$r_{j}$.

###  2.3 Cost-sharing, the core property, and budget-balance

Cost-allocation is the problem of allocating the cost of a solution to the
users in fair and reasonable way. This work focuses on the core: a set of
cost-allocations that are considered both fair and stable. We refer to Jain
and Mahdian [17] for further context. A cost allocation $\xi:\mathcal{U}\times
2^{\mathcal{U}}\rightarrow\mathbb{R}$ assigns, given a group
$U\subseteq\mathcal{U}$ of served users, each user $j\in\mathcal{U}$ a non-
negative cost to pay. If a user $j$ is not served, they are allocated zero
cost. A cost-allocation $\xi$ is in the core if it satisfies the core-property
and budget balance. The core property is said to hold for cost allocation
$\xi$ if, for all served groups $U\subseteq\mathcal{U}$, no sub-group
$J\subseteq U$ can profitably deviate and serve only themselves:

$\sum_{j\in J}\xi(j,U)\leq c(J)\quad\forall J\subseteq U,$ (2)

where $c(J)$ is the cost of serving group $J$. Meanwhile, a cost allocation is
budget-balanced whenever the total cost shares paid by the served users,
$\sum_{j\in U}\xi(j,U)$, covers the cost of serving them.

It is not always possible to both satisfy the core property and recover the
full cost. In particular, there are simple set cover instances that have no
cost-allocations in the core (see e.g. Li et al. [24]). Moreover, Deng,
Ibaraki, and Nagamochi [9] show that a general covering problem has a non-
empty core if and only if its natural LP-relaxation has no integrality gap
(i.e., if the LP is guaranteed to provide a tight bound on the optimum). If
the core is empty, it is common to maximize the cost recovered, subject to the
core core-property [14, 17]. To this end, we say cost-allocation $\xi$ is
$\alpha$-budget-balanced whenever it recovers a fraction $\alpha\in[0,1]$ of
the cost,

$\sum_{j\in U}\xi(j,U)\geq\alpha\cdot c(U).$ (3)

The parameter $\alpha$ is called the cost-recovery ratio. A good cost-
allocation is one that guarantees a high cost-recovery ratio.

The cost-recovery ratio is is well understood via linear programming duality.
On the one hand, dual feasible solutions yield cost shares satisfying the core
property with provably large cost-recovery ratios for a number of problems [9,
10, 14, 15, 21, 23, 25, 27]. On the other hand, seminal work by Deng, Ibaraki,
and Nagamochi [9], and Goemans and Skutella [14] show for the set cover and
facility location problems, respectively, that all cost-allocations satisfying
the core property are dual feasible solutions. Because the cost-allocation
mechanism purchases an integer solution, but only allocates costs as a
fractional solution, weak duality implies that the cost-recovery ratio is
bounded above by the reciprocal of the integrality gap of the problem; it is
folklore that one can recover at most a fraction $\alpha$ of the cost,
whenever the integrality gap of the natural LP relaxation is $1/\alpha$ [17,
25].

Covering Integer Program appears to be in direct contradiction with the
folklore on duality and cost-recover. Li and et al. [24] develop a greedy
algorithm for multi-set multi-cover that produces cost-allocations that
satisfy the core property and recover $\mathcal{O}\left(1/\ln\Delta\right)$ of
the cost. This is accomplished without explicitly using duality. Meanwhile,
the integrality gap of the natural linear programming relaxation of CIP is
known to be unbounded, even when all inputs are integral [5]. We show that the
folklore continues to apply, provided one uses the “right”, and not
necessarily natural, linear programming formulation (see Theorem 3.1). The
strengthened linear programming formulation we use is covered in Subsection
2.5.

###  2.4 Group strategyproofness and cross-monotonicity

So far it has been assumed that the group of users to be served is given;
sometimes this choice also falls on the service provider. In an extended
setting the goal of the service provider is to elicit private user preferences
and design a mechanism for choosing who to serve, in addition to allocating
costs to those served. See Jain and Mahdian [17] for more details on
definitions. Assume that each user $j\in\mathcal{U}$ has a private utility
$u_{j}$ for receiving service, and has the option of opting out for a utility
of $0$. When utilities are unknown, they must be elicited by a mechanism. This
creates a challenge, because users and groups of users may be able to
strategically misrepresent their utilities. A mechanism is said to be
strategyproof if individual users cannot benefit from misrepresenting their
utility, and group strategyproof if no group of users can benefit by colluding
to misrepresent their utilities. The goal of a mechanism in this setting is to
elicit preferences in a group strategyproof manner, decide who to serve, and
allocate-costs in a whay that maximizing the cost-recovery ratio.

To find a group strategyproof mechanism, Moulin and Shenker [26] prove that it
suffices to have cross-monotonic cost-allocation mechanism. Cost-shares
$\xi:\mathcal{U}\times 2^{\mathcal{U}}$ are cross-monotonic if the cost
allocated to user $j$ does not increase when more users are served:

$\xi(j,U)\leq\xi(j,J)\quad\forall j\in J\subseteq U\subseteq\mathcal{U}.$ (4)

Not all cost-shares that satisfy the core property are cross-monotonic. Pál
and Tardos [27] show a general approach for using primal-dual algorithms to
find cross-monotonic cost shares in the facility location and rent-or-buy
problems. This approach has been used for many other problems as well [18, 20,
21, 23]. Interestingly, imposing cross-monotonicity usually lowers the best
attainable cost-recovery ratio [27]. Indeed, Immorlica, Mahdian, and Mirrokni
[16] upper bound the cost-recovery ratio for cross-monotonic cost allocations
using an elegant probabilistic method. In particular, a cross-monotonic cost
allocation for set cover can recover at most $1/\Delta$ of the cost, where
$\Delta$ is the size of the largest set. Moreover, even if all elements are
covered by at most two sets, the cost recovery ratio is at most
$\mathcal{O}\left((2+\epsilon)/n^{1/3}\right)$. Li et al. [24] describe a
cross-monotonic cost allocation for the CIP that recovers $1/(2n)$ of the cost
without explicit use of duality; simplify their proof using a strengthened
dual, generaliz the algorithm to CIP, and improve this to $1/(2\Delta)$.

###  2.5 Knapsack-cover inequalities and approximation algorithms

Working with the natural linear programming relaxation of CIP is challenging
because the integrality gap is unbounded. Carr et al. [5] provide a simple
example using only one user. Let $R>0$ be a large integer requirement for the
one user. Let there be two items. Item A provides $R-1$ units of coverage at
zero cost; Item B provides $R$ units of coverage at a cost of $1$. Clearly, a
feasible integer solution must include item B, with a total cost of $1$. A
fractional solution, however can select a full unit of item B, and only a
$1/R$ fraction of item $A$, with a cost of $1/R$. The cost ratio of the
integer solution to the fractional solution is $R$, which can be chosen to be
arbitrarily large.

Carr et al. [5] strengthen the linear programming formulation by adding an
exponentially large family of valid knapsack-cover (KC) inequalities. Suppose
facilities $S\subseteq\mathcal{F}$ have been built. Then user $j$ has
_residual demand_ $r^{S}_{j}=\max\left\\{r_{j}-\sum_{i\in
S}a_{ij},0\right\\}$. That is, to satisfy her requirement, user $j$ must
collect a contribution of at least $r^{S}_{j}$ from the remaining unbuilt
facilities $\mathcal{F}\backslash S$. In addition, there is no benefit to
exceeding $r^{S}_{j}$, so contributions $a_{ij}$ that exceed $r^{S}_{j}$ can
be reduced to $r^{S}_{j}$. We call
$a^{S}_{ij}=\min\left\\{a_{ij},r^{S}_{j}\right\\}$ the residual contribution,
and set it to zero whenever $i$ is in $S$. This defines a knapsack-cover
inequality for every subset $S\subseteq\mathcal{F}$ and user $j\in\mathcal{U}$

$\sum_{i\in F\backslash S}a^{S}_{ij}\geq r^{S}_{j}.$ (5)

There are $|\mathcal{U}|\times|2^{\mathcal{F}}|=m2^{n}$ KC-inequalities. It is
critical to note that adding these inequalities does not change the set of
feasible integer solutions.

The KC-inequalities define a strengthened linear programming relaxation with a
corresponding strengthened dual program. We call the strengthened primal
program the knapsack-cover linear program (2.5). For a given subset of users
$U\subseteq\mathcal{U}$, the program is:

$\displaystyle\min_{x}~{}$ $\displaystyle\sum_{i\in\mathcal{F}}c_{i}x_{i},$
$\displaystyle s.t.\quad$ $\displaystyle\sum_{i\in F\setminus
S}a^{S}_{ij}x_{i}\geq r^{S}_{j},$ $\displaystyle\forall(j,S)\in U\times
2^{\mathcal{F}},$ (KC-LP) $\displaystyle x_{i}\geq 0,$ $\displaystyle\forall
i\in\mathcal{F}.$

This is a pure covering program, as the multiplicity constraints are no longer
necessary222They are implicit in setting $a^{S}_{ij}$ to zero whenever $i\in
S$.. Associated with this primal is a dual packing program; the knapsack-cover
dual program (2.5). The dual has one constraint for each facility in
$\mathcal{F}$, and an exponential number of variables $y^{S}_{j}$, each
corresponding to one KC-inequality. For a fixed facility $i$, the main
constraint requires that the sum of all variables corresponding to selections
$S$ not including facility $i$ should add up to at most the cost of the
facility.

$\displaystyle\max_{y}~{}$ $\displaystyle\sum_{j\in U}\sum_{S\subseteq
F}r^{S}_{j}y^{S}_{j},$ $\displaystyle s.t.\quad$ $\displaystyle\sum_{j\in
U}\sum_{S\subseteq F\setminus\\{i\\}}a^{S}_{ij}y^{S}_{j}\leq c_{i},$
$\displaystyle\forall i\in F,$ (KC-DP) $\displaystyle y_{j}^{S}\geq 0,$
$\displaystyle\forall(j,S)\in U\times 2^{F}.$

There are state-of-the art approximation algorithms that produce integer
solutions with costs within a multiplicative factor of the KC-LP optimum. Some
also produce feasible solutions to the strengthened dual. Carr et al. [5]
describe a $\Gamma$-approximation algorithm based on rounding a solution to
KC-LP. Conversely, using a more involved rounding approach, Kolliopoulos and
Young [19] give a $\mathcal{O}\left(\log(1+\Delta)\right)$ approximation
algorithm. Together, these upper bound the strengthened integrality gap by
$\Gamma$ and $\mathcal{O}\left(1+\log\Delta\right))$. More recently, KC-LP
rounding algorithms have approximation ratios that are logarithmic in the
maximum column sum $\Delta_{1}=\max_{i\in\mathcal{F}}\sum_{j\in
U}a_{ij}/r_{j}$ rather than $\Delta$; the former term being at most $\Delta$,
and often much smaller [6, 7]. However, these solutions may violate the
multiplicity constraints by a small amount.333These are nevertheless relevant
to cost-sharing applications that have no multiplicity constraints, or in
which small violations can be tolerated. Finally, Carnes and Shmoys [4]
develop a primal-dual algorithm that uses the strengthened dual, providing a
2-approximation for the minimum-cost knapsack problem. While this algorithm
produces feasible dual solutions, the rounding algorithms require solving the
strengthened LP and its dual first.

The strengthened linear program and its dual can be efficiently solved to near
optimality despite the large number of constraints. Chekuri and Quanrud [6]
develop a multiplicative weights method that returns approximately optimal
primal and dual solutions in near linear time, although with a dependence on
the error term on the order of $\mathcal{O}\left(1/\epsilon^{5}\right)$. This
approach builds on the approach of Plotkin, Shmoys, and Tardos [30], and the
solution method outlined by Carr et al. [5]. The returned dual solutions are
feasible, within a $\frac{1}{1-\epsilon}$-factor of the optimum, and have a
polynomially bounded number of non-zero variables [6]. In practice, the primal
and dual problems can often be solved exactly using column generation; the
problem of finding a most violated inequality can be reduced to solving a
sequence of pseudo-polynomially-many minimum-cost knapsack problems, each
which admits a pseudo-polynomial exact algorithm (e.g. by adapting the
algorithm in [22]).

##  3 Cost-shares and strengthened LP

Our main result shows that any feasible solution to the strengthened dual
(2.5) produces natural cost-allocations that satisfy the core property. This
enables the use of existing KC-LP-relative approximation algorithms to find
cost-shares with good cost-recovery ratios.

###### Theorem 3.1

Fix users $U\subseteq\mathcal{U}$. Let
$\mathbf{y}=(y^{S}_{j})_{S\subseteq\mathcal{F},j\in U}$ be a KC-LP dual-
feasible solution. Then, cost shares

$\xi(j,U)=\sum_{S\subseteq\mathcal{F}}r^{S}_{j}y^{S}_{j}\qquad\forall j\in U,$
(6)

with $\xi(j,U)=0$ for $j\notin U$, satisfy the core property.

Clearly, the sum of cost shares over all users is exactly the strengthened
dual objective in (2.5). The theorem can be used in two ways. First, it can be
used to exploit approximation algorithms that find integer solutions with
costs bounded in terms of a corresponding dual-feasible solution.

###### Corollary 1

Fix users $U\subseteq\mathcal{U}$, and let $X\subseteq\mathcal{F}$ be a
feasible integral solution serving users $U$, and $\mathbf{y}$ a KC-LP dual
feasible solution for the problem defined on users $U$. If the solution $X$ is
KC-LP-relative $\alpha$-approximation, i.e.,

$\sum_{i\in X}c_{i}\leq\alpha\sum_{j\in
U}\sum_{S\subseteq\mathcal{F}}r^{S}_{j}y^{S}_{j},$

then the cost shares in Theorem 3.1 recover at least $1/\alpha$ of the cost.

This immediately implies that the Carr et al. [5] algorithm can produce cost
shares that recover $1/\Gamma$ cost, and that the rounding approach of
Kolliopoulos and Young [19] produces a cost-recovery ratio of
$\mathcal{O}\left(1/\ln\Delta\right)$. Moreover, if small violations of the
multiplicity bounds are tolerated, this is improved to
$\mathcal{O}\left(1/\ln\Delta_{1}\right)$. The $1/\Gamma$ bound is new. The
latter matches the $\mathcal{O}\left(1/\ln\Delta\right)$ ratio of Li et al.
[24] for the multi-set multi-cover problem, and applies more generally,
including when inputs are fractional. The second use of the result is to
completely decouple the search for an integral primal solution from the search
of a dual solution; for any integer solution, one can solve the dual (2.5) to
near optimality and user Theorem 3.1 to produce a cost-allocation in the core.

We proceed by proving the theorem. The proof is relatively simple; it
naturally uses dual feasibility, and a rearrangement of summations that is
standard in the analysis of primal-dual schema [33]. Fix the users
$U\subseteq\mathcal{U}$. We need to show that for any coalition $J\subseteq
U$,

$c(X^{*}_{J})\geq\sum_{j\in U}\xi(j,U),$

where $c(X^{*}_{J})$ is the minimum cost of an integer solution serving
coalition $J$.

Let $\mathbf{y}$ be a dual (2.5) feasible solution for users $U$, with
corresponding cost-shares $\xi(j,\mathcal{U})$ computed from $\mathbf{y}$ as
in the statement of Theorem 3.1. Now consider a subset of users
$J\subseteq\mathcal{U}$. To prove the main theorem, we must argue that the
total cost allocated to group $J$ are no more than the cost of serving the
coalition $J$ optimally.

To this end, let $X^{*}_{J}\subseteq\mathcal{F}$ be a minimum-cost solution
for serving group $J$. Using 2.5 feasibility of $\mathbf{y}$, the minimum cost
of serving group $J$ is bounded below by

$\displaystyle c(X^{*}_{J})$ $\displaystyle=\sum_{i\in
X^{*}_{J}}c_{i}\geq\sum_{i\in X^{*}_{J}}\left(\sum_{j\in U}\sum_{S\subset
S\backslash\\{i\\}}a^{S}_{ij}y^{S}_{j}\right).$

One right-hand-side, the middle sum is over all users $U$, while we are more
interested in the coalition $J$. However, because all data and variables are
non-negative, the inequality is preserved if summing only over the users $J$ .
If suffices to show that the RHS above is an upper bound on the total cost
allocation of coalition $J$.

A standard change in the order of summation completes the proof. The right
hand side terms above counts, for every item $i\in X^{*}$, the sum over
subsets $S\subseteq F$ that do not contain $i$. Equivalently, one can sum, for
each subset $S\subseteq F$, every item in $X^{*}_{J}$ not in $S$.

$\displaystyle\sum_{i\in X^{*}_{J}}\sum_{j\in J}\sum_{S\subset
F\backslash\\{i\\}}a^{S}_{ij}y^{S}_{j}=\sum_{j\in J}\sum_{S\subseteq
F}y^{S}_{j}\left(\sum_{i\in X^{*}_{J}\setminus S}a^{S}_{ij}\right)$

Recall now that $X^{*}_{J}$ is a feasible solution to the sub-problem induced
by coalition $J$. In other words, the residual demand at each subset $S$ is
satisfied by $X^{*}_{J}$ for all users in $J$;

$\sum_{i\in X^{*}_{J}\backslash S}a^{S}_{ij}\geq r^{S}_{J},\quad\forall j\in
J.$

The resulting resulting expression is precisely the cost allocation to group
$J$. We have shown

$c(X^{*}_{J})\geq\sum_{j\in J}\sum_{S\subseteq
F}r^{S}_{j}y^{S}_{j}=\sum_{j}\xi(j,\mathcal{U}).$ (7)

In other words, any 2.5 dual solution $\mathbf{y}$ produces cost-shares
satisfying the core propriety.

###  3.1 Tightness of the cost-recovery ratio

An natural question is whether there are cost-allocations, perhaps not derived
from dual variables, that have higher worst-case cost-recovery ratios than
ours. For CIP the answer is _no_ , at least with respect to parameters
$\Gamma$ and $\Delta$. In particular, when all contributions and requirements
are binary, the KC-LP and its dual reduce to the standard set cover linear
programs. Here, the folk theorem applies, and the cost-recovery ratio is
bounded by the integrality gap [9]. For Set Cover, hand hence CIP as well, the
integrality gap can be as large as $\Gamma$ and $\ln\Delta$ [12, 32]. All in
all, this shows that the KC-LP framework provides a simple framework for
finding cost allocations satisfying the core property, with optimal cost-
recovery ratios. However, there these cost allocations need not satisfy cross-
monotonicity, and hence need not produce a group strategyproof mechanism.

##  4 A group strategyproof primal-dual algorithm

Our strengthened linear programming approach and also be used to find cross-
monotonic cost shares. Our mechanism uses a primal-dual algorithm following
the general framework of Pál and Tardos [27]. While our algorithm is
equivalent to that of Li et al. [24], it differs in its analysis. In
particular the connection to primal-dual algorithms is new. Moreover, we
believe our analysis is simpler, and it improves on the worst-case $1/(2n)$
cost-recovery ratio of Li et al., to $1/(2\Delta)$, with $\Delta\leq n$. The
following theorem summarizes the the performance of the mechanism.

###### Theorem 4.1

Fix users $U\subseteq\mathcal{U}$. The mechanism (Algorithm 1) produces a
feasible solution $X$ for users $U$, and cross-monotone cost shares $\xi(j,J)$
that satisfy $\sum_{j\in J}\xi(j,J)\geq\left(\frac{1}{2\Delta}\right)c(X)$.

The main algorithmic idea behind the mechanism is to let each user
independently select facilities in complete isolation from the other users.
Cross-monotonicity by preventing any interactions between users’ dual
variables. Moreover, the problem faced by an individual user is a minimum
cost-knapsack problem, which each be solved with a primal-dual algorithm
(Algorithm 2) [4]. This produces, for each user $j\in U$, a selection of
facilities $X_{j}$, and a KC-LP dual solution $\mathbf{y}_{j}$ that is
feasible to the individual problem in which there are constraints for user $j$
only, and no variables corresponding to other users. Finally, our mechanism
selects the union of all selected facilities $(X_{j})_{j\in U}$, and scales
down the individual dual variables $\mathbf{y}_{j}$ by the column sparsity
$\Delta$. The procedure is summarized in Algorithm 1, in which
MinCostKnapsackPrimalDual is Algorithm 2.

Input: $(F,U,\mathbf{r},\mathbf{c},\mathbf{A})$

for  _all users $j\in J$ independently_ do

$X_{j},\mathbf{y}^{\prime}_{j}\leftarrow\text{MinCostKnapsackPrimalDual}(F,r_{j},ca_{j})$

$\mathbf{y}_{j}\leftarrow\mathbf{y}^{\prime}_{j}/\Delta$

$X\leftarrow\cup_{j\in U}X_{j}$

$\xi(j,U)\leftarrow\frac{1}{2\Delta}\sum_{S\subseteq F}y^{S}_{j}$ for all
$j\in U$

return _$X,\xi$_

Algorithm 1 A cross-monotonic primal-dual algorithm

Carnes and Shmoys [4] develop and analyze a primal-dual algorithm for the
minimum-cost knapsack problem based on the KC-LP formulation. Fix a single
user $j\in\mathcal{U}$ and let $\mathbf{a}_{j}=(a_{1j},\dots,a_{nj})$ denote
their contributions. The user starts with an all-zero dual solution
$\mathbf{y}_{j}$, and an empty selection $X=\emptyset$. While the residual
demand $r^{X}_{j}$ is positive, they increase the dual variable $y^{X}_{j}$.
Eventually, some constraint $\sum_{S\subseteq
F-\\{i\\}}a^{X}_{ij}y^{X}_{j}\leq c_{i}$ becomes tight for a facility $i$.
This facility is added to the selection $X$, and the process repeats. This
procedure is summarized in Algorithm 2. The algorithm returns a selection of
facilities $X_{j}$ and a feasible KC-LP dual solution. Critically, the cost of
$X_{j}$ is at most twice the KC-LP dual objective under $\mathbf{y}_{j}$.

######  Theorem 4.2 (Carnes and Shmoys [4])

Let $X_{j}\subseteq\mathcal{F}$ and $\mathbf{y}_{j}$ be a selection of
facilities, and the corresponding dual solution returned by Algorithm 2. These
satisfy the inequality

$\sum_{i\in X_{j}}c_{i}\leq 2\sum_{S\subseteq\mathcal{F}}r^{S}_{j}y^{S}_{j}.$

This result is used in two parts of our proof. First, we use the dual
feasibility of the individual dual variables $\mathbf{y}_{j}$ to construct a
feasible dual solution to the master CIP, which gives us the core-property via
Theorem 3.1. Secondly, the approximation ratio is used to derive our cost-
recovery ratio.

Input: $(\mathcal{F},\mathbf{c},r_{j},\mathbf{a}_{j})$

$X,\mathbf{y}_{j}\leftarrow\emptyset,\mathbf{0}$

while  _$r^{X}_{j} >0$_ do

Increase $y^{X}_{j}$ until for some $i\in\mathcal{F}\backslash X$:
$\sum_{S\subseteq F-\\{i\\}}a^{X}_{ij}y^{X}_{j}=c_{i}$ (8) $X\leftarrow
X\cup\\{i\\}$

return _$X$ , $\mathbf{y}_{j}$_

Algorithm 2 Minimum-Cost Knapsack Primal-Dual Algorithm

###  4.1 Proof of the theorem

The proof of our result is remarkably simple. We only need to argue for cross-
monotonicity, the core-property, and cost recovery. We argue for cross-
monotonicity first. Clearly, the dual variables $\mathbf{y}^{\prime}_{j}$ of
each user are entirely independent of the other users. Meanwhile, the maximum
number of users in $U$ served by any facility, $\Delta$, is monotonically
increasing in the size of $U$, so the dual variables
$\mathbf{y}_{j}=\mathbf{y}^{\prime}_{j}/\Delta$ are are monotonically
decreasing in $U$, as are the induced cost-shares.

The core property is easy to prove using dual feasibility and our Theorem 3.1.
Consider some selected facility $i\in X$. Then

$\sum_{j\in U}\sum_{S\subseteq
F\backslash\\{i\\}}a^{S}_{ij}y^{S}_{j}=\frac{1}{\Delta}\sum_{\\{j\in
U:a_{ij}>0\\}}\left(\sum_{S\subseteq F\backslash\\{i\\}}a^{S}_{ij}y^{\prime
S}_{j}\right)\leq\frac{1}{\Delta}\sum_{\\{j\in J:a_{ij}>0\\}}c_{i}\leq c_{i}$

The first equality follows from dropping users not served by facility $i$. The
second equality uses the definition of
$\mathbf{y}_{j}=\mathbf{y}^{\prime}_{j}/\Delta$. The following inequality uses
fact that the dual variables are individually feasible to the min cost
knapsack LP of each user $j$. The final inequality follows from the definition
of $\Delta$. The above shows that dual variables $(\mathbf{y}_{j})_{j\in U}$
are feasible for the CIP induced by users $U$, and so Theorem 3.1 implies that
the core-property is satisfied by the accompanying cost shares
$(\xi(j,U))_{j\in U}$.

Finally, the cost-recovery recovery ratio follows from the approximation ratio
of the minimum-cost knapsack algorithm. In particular, observe that

$\sum_{i\in X}c_{i}\leq\sum_{j\in U}\sum_{i\in X_{j}}c_{i}\leq 2\sum_{j\in
U}\sum_{S\subseteq\mathcal{F}}r^{S}_{j}y^{\prime S}_{j}=2\Delta\sum_{j\in
U}\sum_{S\subseteq\mathcal{F}}r^{S}_{j}y^{S}_{j}.$

The first inequality is obvious; the second follows from applying Theorem 4.2
to each user $j$ in $U$ individually. The last equality follows from the
definition of $\mathbf{y}_{j}$. This proves that the cost-recovery ratio is at
least $1/(2\Delta)$, as claimed.

Finally, the proof suggests there is potential for improvement. In fact,
whenever the contributions $\mathbf{A}$ are binary, the min-cost knapsack
algorithm is exact, in which case the cost-recovery ratio is $1/\Delta$ [24].
Moreover, if we know that each selected facility $X$ always selected by at
least two users, it also follows that the cost-recovery ratio is a factor $2$
larger, i.e., $1/\Delta$. On the other hand, no group strategyproof mechanism
can recover more than $1/\Delta$ of the cost in general [16]. Whether the
$1/(2\Delta)$ cost-recovery ratio is tight when contributions are non-binary
remains an open problem [24].

## References

  * [1] Almuhaya, M.A., Jabbar, W.A., Sulaiman, N., Abdulmalek, S.: A survey on LoRaWAN technology: Recent trends, opportunities, simulation tools and future directions. Electronics 11(1), 164 (2022)
  * [2] Attia, T., Heusse, M., Tourancheau, B., Duda, A.: Experimental characterization of LoRaWAN link quality. In: 2019 IEEE Global Communications Conference (GLOBECOM). pp. 1–6. IEEE (2019)
  * [3] Augustin, A., Yi, J., Clausen, T., Townsley, W.M.: A study of LoRa: Long range & low power networks for the internet of things. Sensors 16(9), 1466 (2016)
  * [4] Carnes, T., Shmoys, D.: Primal-dual schema for capacitated covering problems. In: Integer Programming and Combinatorial Optimization: 13th International Conference, IPCO 2008 Bertinoro, Italy, May 26-28, 2008 Proceedings 13. pp. 288–302. Springer (2008)
  * [5] Carr, R.D., Fleischer, L.K., Leung, V.J., Phillips, C.A.: Strengthening Integrality Gaps for Capacitated Network Design and Covering Problems. Tech. rep., Sandia National Lab.(SNL-NM), Albuquerque, NM, United States (1999)
  * [6] Chekuri, C., Quanrud, K.: On Approximating (Sparse) Covering Integer Programs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 1596–1615. SIAM (2019)
  * [7] Chen, A., Harris, D.G., Srinivasan, A.: Partial resampling to approximate covering integer programs. Random Structures & Algorithms 58(1), 68–93 (2021)
  * [8] Chiang, C.I., Hwang, M.J., Liu, Y.H.: An alternative formulation for certain fuzzy set-covering problems. Mathematical and Computer Modelling 42(3-4), 363–365 (2005)
  * [9] Deng, X., Ibaraki, T., Nagamochi, H.: Algorithmic aspects of the core of combinatorial optimization games. Mathematics of Operations Research 24(3), 751–766 (1999). https://doi.org/10.1287/moor.24.3.751, https://doi.org/10.1287/moor.24.3.751
  * [10] Devanur, N.R., Mihail, M., Vazirani, V.V.: Strategyproof cost-sharing mechanisms for set cover and facility location games. In: Proceedings of the 4th ACM Conference on Electronic Commerce. pp. 108–114 (2003)
  * [11] Farhad, A., Kim, D.H., Pyun, J.Y.: Scalability of lorawan in an urban environment: A simulation study. In: 2019 Eleventh International Conference on Ubiquitous and Future Networks (ICUFN). pp. 677–681. IEEE (2019)
  * [12] Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM (JACM) 45(4), 634–652 (1998)
  * [13] Garey, M.R., Johnson, D.S.: Computers and intractability: A Guide to the Theory of NP-Completeness (1979)
  * [14] Goemans, M.X., Skutella, M.: Cooperative facility location games. Journal of Algorithms 50(2), 194–214 (2004)
  * [15] Gupta, A., Kumar, A., Pál, M., Roughgarden, T.: Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem. In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. pp. 606–615. IEEE (2003)
  * [16] Immorlica, N., Mahdian, M., Mirrokni, V.S.: Limitations of cross-monotonic cost-sharing schemes. ACM Transactions on Algorithms (TALG) 4(2), 1–25 (2008)
  * [17] Jain, K., Mahdian, M.: Cost Sharing, p. 385–410. Cambridge University Press (2007). https://doi.org/10.1017/CBO9780511800481.017
  * [18] Jain, K., Vazirani, V.V.: Equitable cost allocations via primal–dual-type algorithms. SIAM Journal on Computing 38(1), 241–256 (2008)
  * [19] Kolliopoulos, S.G., Young, N.E.: Approximation algorithms for covering/packing integer programs. Journal of Computer and System Sciences 71(4), 495–505 (2005)
  * [20] Könemann, J., Leonardi, S., Schäfer, G., Van Zwam, S.: From primal-dual to cost shares and back: a stronger lp relaxation for the steiner forest problem. In: Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. Proceedings 32. pp. 930–942. Springer (2005)
  * [21] Könemann, J., Leonardi, S., Schäfer, G., van Zwam, S.H.: A group-strategyproof cost sharing mechanism for the Steiner forest game. SIAM Journal on Computing 37(5), 1319–1341 (2008)
  * [22] Lawler, E.L.: Fast approximation algorithms for knapsack problems. In: 18th Annual Symposium on Foundations of Computer Science (sfcs 1977). pp. 206–213. IEEE (1977)
  * [23] Leonardi, S., Schaefer, G.: Cross-monotonic cost-sharing methods for connected facility location games. In: Proceedings of the 5th ACM Conference on Electronic Commerce. p. 242–243. EC ’04, Association for Computing Machinery, New York, NY, USA (2004). https://doi.org/10.1145/988772.988814, https://doi.org/10.1145/988772.988814
  * [24] Li, X.Y., Sun, Z., Wang, W., Lou, W.: Cost sharing and strategyproof mechanisms for set cover games. Journal of combinatorial optimization 20(3), 259–284 (2010)
  * [25] Meir, R., Bachrach, Y., Rosenschein, J.S.: Minimal subsidies in expense sharing games. In: Algorithmic Game Theory: Third International Symposium, SAGT 2010, Athens, Greece, October 18-20, 2010. Proceedings 3. pp. 347–358. Springer (2010)
  * [26] Moulin, H., Shenker, S.: Strategyproof sharing of submodular costs: budget balance versus efficiency. Economic Theory pp. 511–533 (2001)
  * [27] Pál, M., Tardos, É.: Group Strategyproof Mechanisms via Primal-Dual Algorithms. In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. pp. 584–593. IEEE (2003)
  * [28] Parsons, S.G.: Cross-subsidization in telecommunications. Journal of Regulatory Economics 13, 157–182 (1998)
  * [29] Petrić, T., Goessens, M., Nuaymi, L., Toutain, L., Pelov, A.: Measurements, performance and analysis of LoRa FABIAN, a real-world implementation of LPWAN. In: 2016 IEEE 27th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC). pp. 1–7. IEEE (2016)
  * [30] Plotkin, S.A., Shmoys, D.B., Tardos, É.: Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research 20(2), 257–301 (1995)
  * [31] Semtech: LoRa® and LoRaWAN®: A technical overview. https://lora-developers.semtech.com/documentation/tech-papers-and-guides/lora-and-lorawan/, accessed: 2021-09-07
  * [32] Singh, M.: Integrality gap of the vertex cover linear programming relaxation. Operations Research Letters 47(4), 288–290 (2019). https://doi.org/https://doi.org/10.1016/j.orl.2019.03.015, https://www.sciencedirect.com/science/article/pii/S0167637718301949
  * [33] Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge university press (2011)