Campus Event Calendar
Event Entry
What and Who
Group Strategy Proof Mechanisms via Primal-dual Algorithms
Maria Minkoff
Max-Planck-Institut für Informatik - AG 1
AG1 Mittagsseminar (others' work)
AG 1, AG 2, AG 3, AG 4
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 5 November 2003
13:30
-- Not specified --
46.1 - MPII
024
Saarbrücken
Abstract
Abstract of paper: We develop a general method for cost-sharing that is approximately budget balanced and group strategyproof. We use our method to design cost sharing mechanisms for two NPcomplete problems: metric facility location, and single source rent-or-buy network design. Both mechanisms are competitive, group strategyproof and recover a constant fraction of the cost. For the facility location game our cost-sharing method recovers a 1/3rd of the total cost, while in the network design game the cost shares pay for a 1/15 fraction of the cost of the solution.
No familiarity with the game theory and mechanism design is assumed. All of the terminology will be defined and explained in the talk.
Contact
Ingmar Weber
--email hidden
passcode not visible
logged in users only
Maria minkoff, 10/30/2003 12:13
Ingmar Weber, 10/29/2003 17:34
Ingmar Weber, 10/29/2003 17:34 -- Created document.
Ingmar Weber, 10/29/2003 17:34
Ingmar Weber, 10/29/2003 17:34 -- Created document.