Cost-sharing mechanisms for Network Design

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=f4lS1qBPcIM


Duration: 50:08
54 views
2

Today's Internet seamlessly connects billions of users that mostly pursue selfish motives in both, single-handed and collaborative ways. By design the Internet is anarchic and hence, it is devoid of a central authority that possesses global knowledge and the power to regulate the agents' behavior. In this talk we focus on the design of so called 'mechanisms' that encourage truthful and fair behavior among the agents/users by means of issuing rewards and by postulating interaction rules. We present a first mechanism able to share between users in a fair manner the cost of a Steiner forest that connects a set of terminal pairs. This mechanism is also proved to recover at least 1/2 the cost of the solution. This mechanism is a primal dual algorithm based on a new linear programming relaxation that is shown strictly stronger that the classical undirected cut relaxation. We also prove that no such mechanism can recover more than 1/2 of the cost of the solution for the Steiner tree game, therefore implying tightness of our result. This is joint work with Guido Schaefer at Universita' di Roma La



Other Videos By Microsoft Research


2016-09-05Headwinds and Tailwinds:  Where is the U.S. economy going?
2016-09-05Paradigms of Worm Defense & Thoughts from an Ivory Tower
2016-09-05Machine Learning Methods for Discovery of Regulatory Elements in Bacteria
2016-09-05Eyes on Multimodal Interaction
2016-09-05From Promoter to Expression ΓÇô A Probabilistic Framework for Inferring Regulatory Mechanisms
2016-09-05Automated Reconstruction of 3D City Models from Laser Scans and Camera Images
2016-09-05Bergman complexes, Coxeter arrangements, and graph associahedra
2016-09-05Biomal Human Emotion Recognition and Peer Steaming Projects at  Ryerson Multimedia Research Lab
2016-09-05Interfaces for Staying in the Flow         [1/3]
2016-09-05Place Lab: Device Positioning Using Radio Beacons in the Wild
2016-09-05Cost-sharing mechanisms for Network Design
2016-09-05Market-Based Programming Paradigms for Sensor Networks
2016-09-05Convex Geometry of Orbits
2016-09-05The Benefit of Adaptivity in Stochastic Optimization [1/6]
2016-09-05Bridging art and architecture: How emergent digital media have transformed our landscapes
2016-09-05Effective Use of Microsoft Word for Academic Writing
2016-09-05Impala: A Middleware System for Managing Autonomic, Mobile, Wireless Sensor Networks
2016-09-05Transactional Coherence & Consistency
2016-09-05Pathfinder/MonetDB: making XQuery scale using the relational approach
2016-09-05ASM View of Abstract Cryptography
2016-09-05Deterministic Network Coding by Matrix Completion


Tags:
microsoft research