Mechanism Design without Money for Heterogeneous and Distributed Facility Location Problems

  • Thu 7 Dec 23

    12:00 - 13:00

  • Colchester Campus


  • Event speaker

    Rongsen Zhang

  • Event type

    Lectures, talks and seminars
    CCFEA Seminar series

  • Event organiser

    Computer Science and Electronic Engineering, School of

Algorithmic Mechanism Design (AMD) is an interdisciplinary field that bridges economics and computer science and aims to design mechanisms for systems with self-interested agents. This study focuses on motivating truthful information disclosure while optimizing social goals. Traditional payment-based mechanisms cannot be effectively applied to these problems, but we can utilize approximate mechanisms to obtain truthfulness without recourse to payments.

One of the well-established problems in approximate mechanism design without money is the facility location problem. In this context, agents possess private positions along a line, and the goal is to determine the location of a public facility while motivating truthful disclosures and achieving optimal social outcomes.

This presentation presents contributions across three key dimensions of facility location problems: (1) Heterogeneous Two-Facility Location Problem: Addressing a discrete setting where agents occupy nodes on a line graph and possess private preferences for two facilities, the research introduces deterministic strategy-proof mechanisms with improved approximation ratios, surpassing existing approaches. (2) Two-Facility Location with Candidate Positions: Investigating another variant, where agents have private positions and known preferences for two facilities, the study identifies deterministic strategy-proof mechanisms that achieve the best possible approximation ratios for social and maximum costs. (3) Distributed Facility Location Problem: Agents are grouped into districts with positions along a real-number line in setting a distributed facility location. The research analyzes two mechanism classes: unrestricted, where agents directly provide truthful positions, and strategy-proof, designed to incentivize honesty. The study establishes tight bounds for various social objectives, including average social cost, max cost, and other fairness-inspired criteria.

In summary, approximate mechanism design without money addresses complex challenges in multi-agent systems, creating mechanisms that promote truthfulness and optimize societal objectives. This presentation introduces innovative mechanisms and provides comprehensive insights into facility location problems from three distinct perspectives.