Approximation algorithms for hard combinatorial problems and games
Speaker: Prof. Stefano Leonardi. Dipartimento di Informatica e Sistemistica, Sapienza University of Rome
- https://computing.phd.upc.edu/en/events/copy_of_curs-master-in-computing
- Approximation algorithms for hard combinatorial problems and games
- 2011-02-08T15:00:00+01:00
- 2011-02-10T15:00:00+01:00
- Speaker: Prof. Stefano Leonardi. Dipartimento di Informatica e Sistemistica, Sapienza University of Rome
When
Feb 08, 2011 03:00 PM to Feb 10, 2011 03:00 PM (Europe/Madrid / UTC100)
Where
UPC.Room tba, building Omega
Add event to calendar
There will be two sessions from 15 to 16:30 on February 8 and 10.
Summary:
This two sessions will be a continuation of the course held the previous year devoted to the basic concepts and techniques for approximating hard combinatorial problems and will focus on approximation in mechanism design.
Cost-sharing methods have been originated in Economics since developing fair cost-haring methods is a central problem in cooperative game theory. We'll address the issues of the design of cost-sharing mechanisms that encourage truthful and fair behavior among users. We'll present mechanisms able to share in fair manner the cost of a network infrastructure with several connectivity requirements and objective functions. The mechanisms should satisfy at the same time several objectives as for instance truthfulness, cost recovery, social costs and be resilient against coalitions. These cost-sharing mechanisms take in general the form of primal-dual approximation algorithms. However, the truthfulness requirement imposes additional limitation to the approximation factors that can be achieved.
Finally we'll consider the approximation of hard combinatorial problems when the input data is private knowledge of independent selfish players. We cast this class of problems in the broad area of mechanism design. The dominant solution concept is the development of mechanisms/algorithms that define a solution and a set of payments such that every player is incentivized to reveal the truth values of the input data. The Vickrey-Clarke-Groves (VCG) mechanism provides a cornerstone method to design truthful algorithms. However, VCG is not computationally efficient for hard combinatorial problems. Alternative methods based on some monotonicity criteria have been proposed to design efficient truthful approximation algorithms and approximation schemes. We'll present the basic concepts for designing truthful mechanisms for single and multiple objective optimization.
Summary:
This two sessions will be a continuation of the course held the previous year devoted to the basic concepts and techniques for approximating hard combinatorial problems and will focus on approximation in mechanism design.
Cost-sharing methods have been originated in Economics since developing fair cost-haring methods is a central problem in cooperative game theory. We'll address the issues of the design of cost-sharing mechanisms that encourage truthful and fair behavior among users. We'll present mechanisms able to share in fair manner the cost of a network infrastructure with several connectivity requirements and objective functions. The mechanisms should satisfy at the same time several objectives as for instance truthfulness, cost recovery, social costs and be resilient against coalitions. These cost-sharing mechanisms take in general the form of primal-dual approximation algorithms. However, the truthfulness requirement imposes additional limitation to the approximation factors that can be achieved.
Finally we'll consider the approximation of hard combinatorial problems when the input data is private knowledge of independent selfish players. We cast this class of problems in the broad area of mechanism design. The dominant solution concept is the development of mechanisms/algorithms that define a solution and a set of payments such that every player is incentivized to reveal the truth values of the input data. The Vickrey-Clarke-Groves (VCG) mechanism provides a cornerstone method to design truthful algorithms. However, VCG is not computationally efficient for hard combinatorial problems. Alternative methods based on some monotonicity criteria have been proposed to design efficient truthful approximation algorithms and approximation schemes. We'll present the basic concepts for designing truthful mechanisms for single and multiple objective optimization.
Share: