  Given the proximity of many wireless users and their diversity in consuming
local resources (e.g., data-plans, computation and even energy resources),
device-to-device (D2D) resource sharing is a promising approach towards
realizing a sharing economy. In the resulting networked economy, $n$ users
segment themselves into sellers and buyers that need to be efficiently matched
locally. This paper adopts an easy-to-implement greedy matching algorithm with
distributed fashion and only sub-linear $O(\log n)$ parallel complexity, which
offers a great advantage compared to the optimal but computational-expensive
centralized matching. But is it efficient compared to the optimal matching?
Extensive simulations indicate that in a large number of practical cases the
average loss is no more than $10\%$, a far better result than the $50\%$ loss
bound in the worst case. However, there is no rigorous average-case analysis in
the literature to back up such encouraging findings, which is a fundamental
step towards supporting the practical use of greedy matching in D2D sharing.
This paper is the first to present the rigorous average analysis of certain
representative classes of graphs with random parameters, by proposing a new
asymptotic methodology. For typical 2D grids with random matching weights we
rigorously prove that our greedy algorithm performs better than $84.9\%$ of the
optimal, while for typical Erdos-Renyi random graphs we prove a lower bound of
$79\%$ when the graph is neither dense nor sparse. Finally, we use realistic
data to show that our random graph models approximate well D2D sharing networks
encountered in practice.
