A Monetary Mechanism for Stabilizing Cooperative Data Exchange with Selfish Users
Abstract
In this research, we address the stability issues in Cooperative Data Exchange (CDE),
one of the central problems in wireless network coding. We consider a setting in which the
users are selfish, i.e., would like to maximize their own utility. More specifically, we
consider a setting where each user has a subset of packets in the ground set X, and wants
all other packets in X. The users can exchange data by broadcasting coded or uncoded
packets over a lossless channel, and monetary transactions are allowed between any pair
of users. We define the utility of each user as the sum of two sub-utility functions: (i)
the difference between the total payment received by the user and the total transmission
rate of the user, and (ii) the difference between the total number of required packets by
the user and the total payment made by the user. A rate-vector and payment-matrix
pair (r, p) is said to stabilize the grand coalition (i.e., the set of all users) if (r, p) is Paretooptimal
over all minor coalitions (i.e., all proper subsets of users who collectively know
all packets in X). Our goal is to design algorithms that compute a stabilizing ratepayment
pair with minimum total sum-rate and minimum total sum-payment for any
given instance of the problem. In this work, we propose two algorithms that maximize the
sum of utility of all users (over all solutions), and one of the algorithms also maximizes
the minimum utility among all users (over all solutions). The second algorithm requires a
broker, where each user has to trust the broker and use the broker to exchange payments,
whereas in the first algorithm there is no such requirement. In the first algorithm, the users
directly compensate user broadcasting the packet in that particular round. Our scheme
minimizes the total number of transmitted packets, as well as the total amount of
payments. We also perform an extensive simulation study to evaluate the performance of
our scheme in practical setting.
Citation
Tyagi, Ishan (2018). A Monetary Mechanism for Stabilizing Cooperative Data Exchange with Selfish Users. Master's thesis, Texas A & M University. Available electronically from https : / /hdl .handle .net /1969 .1 /174363.