Research Article
Reciprocity-driven Sparse Network Formation
@INPROCEEDINGS{10.4108/eai.5-12-2017.2274430, author={Konstantinos P. Tsoukatos}, title={Reciprocity-driven Sparse Network Formation}, proceedings={11th EAI International Conference on Performance Evaluation Methodologies and Tools}, publisher={ACM}, proceedings_a={VALUETOOLS}, year={2018}, month={8}, keywords={network formation proportional-response nonlinear pricing transaction costs sparse interactions}, doi={10.4108/eai.5-12-2017.2274430} }- Konstantinos P. Tsoukatos
Year: 2018
Reciprocity-driven Sparse Network Formation
VALUETOOLS
ACM
DOI: 10.4108/eai.5-12-2017.2274430
Abstract
A resource exchange network is considered, where exchanges among nodes are based on reciprocity. Peers receive from the network an amount of resources commensurate with their contribution. We assume the network is fully connected, and impose sparsity constraints on peer interactions. Finding the sparsest exchanges that achieve a desired level of reciprocity is in general NP-hard. To capture near-optimal allocations, we introduce variants of the Eisenberg-Gale convex program with sparsity penalties. We derive decentralized algorithms, whereby peers approximately compute the sparsest allocations, by reweighted l1 minimization. The algorithms implement new proportional-response dynamics, with nonlinear pricing. The trade-off between sparsity and reciprocity and the properties of graphs induced by sparse exchanges are examined.