Strategic Mechanism Design in Decision-making
Explore the concept of mechanism design with strategic mediators optimizing global objectives and welfare. Learn about facility location on a line, dominant strategies, two-sided incentive compatibility, and the weighted median of medians.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Mechanism Design with Strategic Mediators Moran Feldman EPFL Joint work with: Moshe Babaioff, Microsoft Research Moshe Tennenholtz, Technion
Mechanism Design Mechanism Decision Should make a global decision Players (Approximately) optimizes a global objective Incentive compatible Requirements 2
Introducing Strategic Mediators Optimization Goal Global welfare Mechanism Welfare of his players In a federal country, the elected representative of a state represents the global interests of the state s population. Mediators Personal welfare Players 3
Facility Location on a Line n clients are located along a line metric. A facility should be placed on the line. The cost of client is its distance from the facility. The social cost is the total costs of all clients. The optimal facility location is the median. The median mechanism makes being truthful a dominant strategy. [Moulin 1980] compatibility concept Summary: 1-competitive strong incentive 4
Adding Strategic Mediators Direct Revelation Mechanism Each mediator reports the locations of all its clients. Locations of B, D and E Next Objective Choosing an incentive compatibility concept ? Location of E A B C D E 5
First Attempt Dominant Strategy Truthful The mechanism: Must locate the facility at the location of the client to get any finite ratio. Must accept the location reported by the mediator, in case everyone is truthful. If the client lies: The mediator must still report the right client location, i.e., he must alter the report of the client. Follows from the sequential nature of the problem all entities share their objective. 6
Two-Sided IC Definitions Agent-Side IC mechanism: It is a dominant strategy for an agent to be truthful assuming its mediator is truthful. Mediator-Side IC mechanism: It is a dominant strategy for a mediator to be truthful assuming its clients are truthful. A mechanism is Two-Sided IC if it is Agent-Side IC and Mediator-Side IC. Stronger than requiring truthfulness to be an ex- post Nash equilibrium. 7
Weighted Median of Medians Calculate the median of the agents of every mediator. Pretend they all are located at this median. Locate the facility at the median of the resulting set. Theorem The above algorithm is Two-Sided IC and 3-competitive, which is the best possible deterministicly. 2 3 8
Analysis Previous works implies: [Procaccia and Tennenholtz 2013 and Dekel et al. 2010] 3-competitive, which is optimal deterministicly Mediator-Side IC What can an agent achieve by lying? At most, it has the power to push the median away. What can that do? The median can only move The median is unchanged. away. No effect. Either has no effect or moves the facility away. Median of mediator Agent 9
Random Algorithm Real agent locations: Locations after every agent is moved to the median of its mediator: 2 3 u1, u2 u3, u4, u5 Randomly select a location for the facility from the middle half of the agents: u1 un/4+1 u3n/4 un 10
Result The above algorithm is Two-Sided IC and 2-competitive, which is the best possible. Analysis Idea (A) For a central segment, in any solution about half of the agents use it. (B) For an extreme segment, the virtual move of the agents can make the segment only slightly more central. Hence, the facility remains on its right side. (C) For other segments: (A) applies partially, i.e., a mistake is not that bad. (B) applies when the random facility location is chosen near the other end. 11
Extensions Generalizing the line metric into a tree metric. All the above results generalize to tree metrics. The random algorithm is more involved. Multiple levels of mediators. The competitive ratio is exponential in the number of levels. 12
Open Problems Extending the model: Multiple facilities. More general metrics. Both have been studies without mediators [Procaccia and Tennenholtz 2013, Lu et al. 2010]. Studying the impact of introducing strategic mediators in other settings. 13
