Approximate Strategyproof Mechanisms Design for Facility Location Games

Speaker:

Mengfan Ma(University of Electronic Science and Technology of China)

Time:

  • 9:00AM(Time in Beijing)
  • 2:00PM(Time in Auckland)
  • February 5, 2021 (Friday)

Address:

Online meeting

VooVmeeting:

ID: 349 933 612 Password: 1936

Link:

https://meeting.tencent.com/s/xvmzXgslf53A

Abstract:

In the basic settings of facility location games, agents are located on the real line and public facilities are to be placed on this line based on the reported locations of the agents. The cost of an agent is its distance from the nearest facility. Procaccia and Tennenholtz(2009) first consider it as a game theoretic optimization problem where the optimal social welfare solution may not be strategyproof. They established upper and lower bounds for the approximation ratio of strategyproof mechanisms without payments, with respect to both deterministic and randomized mechanisms, under two objective functions: the total cost and the maximum cost. Their results were further improved by Lu(2009), Lu(2010) and Fotakis(2013). Since then, various variants of this problem has been studied and multiple papers come out each year.

The purpose of this seminar is twofold: Firstly, to give an introduction to the facility location games, to demonstrate some basic results and techniques, and to provide a brief review on related work; secondly to discuss our proposed new model — facility with entrance fee, including some results and some unsolved problems.

Download poster
Download slides

,