Find information:
[4-14]Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games
Date:2010-04-02
Algorithm and Information Colloquium (AIC)
Title: Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games
Speaker: Pinyan Lu 陆品燕
Time: 16:30 – 17:30, April 14, 2010, Wednesday
Place: Lecture Room, Level 3, Building No. 5, Institute of Software
Tea time: 16:00 – 16:30, Common Room, Level 3, Building No. 5
Abstract:
We consider the problem of locating facilities in a metric space to serve a set of selfish agents. The cost of an agent is the distance between her own location and the nearest facility. The social cost is the total cost of the agents. We are interested in designing strategy-proof mechanisms without payment that have a small approximation ratio for social cost. A mechanism is a (possibly randomized) algorithm which maps the locations reported by the agents to the locations of the facilities. A mechanism is strategy-proof if no agent can benefit from misreporting her location in any configuration. This setting was first studied by Procaccia and Tennenholtz. They focused on the facility game where agents and facilities are located on the real line. Alon et al. studied the mechanisms for the facility games in a general metric space. However, they focused on the games with only one facility. In this paper, we study the two-facility game in a general metric space, which extends both previous models. We first prove an Ω(n) lower bound of the social cost approximation ratio for deterministic strategy-proof mechanisms. Our lower bound even holds for the line metric space. This significantly improves the previous constant lower bounds. Notice that there is a matching linear upper bound in the line metric space. Next, we provide the first randomized strategy-proof mechanism with a constant approximation ratio of 4. Our mechanism works in general metric spaces. For randomized strategy-proof mechanisms, the previous best upper bound is O(n) which works only in the line metric space.
Joint work with Xiaorui Sun, Yajun Wang and Zeyuan Allen Zhu
Title: Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games
Speaker: Pinyan Lu 陆品燕
Time: 16:30 – 17:30, April 14, 2010, Wednesday
Place: Lecture Room, Level 3, Building No. 5, Institute of Software
Tea time: 16:00 – 16:30, Common Room, Level 3, Building No. 5
Abstract:
We consider the problem of locating facilities in a metric space to serve a set of selfish agents. The cost of an agent is the distance between her own location and the nearest facility. The social cost is the total cost of the agents. We are interested in designing strategy-proof mechanisms without payment that have a small approximation ratio for social cost. A mechanism is a (possibly randomized) algorithm which maps the locations reported by the agents to the locations of the facilities. A mechanism is strategy-proof if no agent can benefit from misreporting her location in any configuration. This setting was first studied by Procaccia and Tennenholtz. They focused on the facility game where agents and facilities are located on the real line. Alon et al. studied the mechanisms for the facility games in a general metric space. However, they focused on the games with only one facility. In this paper, we study the two-facility game in a general metric space, which extends both previous models. We first prove an Ω(n) lower bound of the social cost approximation ratio for deterministic strategy-proof mechanisms. Our lower bound even holds for the line metric space. This significantly improves the previous constant lower bounds. Notice that there is a matching linear upper bound in the line metric space. Next, we provide the first randomized strategy-proof mechanism with a constant approximation ratio of 4. Our mechanism works in general metric spaces. For randomized strategy-proof mechanisms, the previous best upper bound is O(n) which works only in the line metric space.
Joint work with Xiaorui Sun, Yajun Wang and Zeyuan Allen Zhu
Biography:
Pinyan Lu is an Associate Researcher at Theory Group of Microsoft Research Asia. He studied in Tsinghua University (BS (2005) and PhD (2009) both in Computer Science). His advisor was Prof. Andrew C. Yao, and he was also co-supervised by Prof. Jin-Yi Cai at University of Wisconsin-Madison. He is mainly interested in complexity theory, algorithms design and algorithmic game theory.
http://research.microsoft.com/en-us/people/pinyanl/
Pinyan Lu is an Associate Researcher at Theory Group of Microsoft Research Asia. He studied in Tsinghua University (BS (2005) and PhD (2009) both in Computer Science). His advisor was Prof. Andrew C. Yao, and he was also co-supervised by Prof. Jin-Yi Cai at University of Wisconsin-Madison. He is mainly interested in complexity theory, algorithms design and algorithmic game theory.
http://research.microsoft.com/en-us/people/pinyanl/