School Seminars and Colloquia

Mechanism Design without Money for Obnoxious Facility Games

Discrete Structures and Algorithms (Seminar)

by Yukun Cheng


Institution: Zhejiang University, and Zhejiang University of Finance and Economics
Date: Wed 27th March 2013
Time: 2:30 PM
Location: Old Geology Theatre 2

Abstract: We will talk about an obnoxious facility game on a network, where the facility is undesirable and all agents try to be as far away from the facility as possible, so that an agent's utility can be measured by the distance from the facility. We will also discuss the obnoxious facility game with a bounded service range on a path, where each facility is not only undesirable but also has a service radius $r$. Thus each agent tries to be far away from the facilities, but still to be served by a facility. In other words, the distance between an agent and her nearest facility is at most $r$ and the utility of an agent is defined as this distance. In a deterministic or randomized mechanism, based on the addresses reported by the selfish agents, the locations or the location distributions of facilities are determined. The aim of the mechanisms is to maximize the obnoxious social welfare, namely the total utilities of all agents. The objective of each agent is to maximize her own utility and she may lie if, by doing so, more benefit can be obtained. A mechanism is called strategy-proof if it enforces all agents to report their true locations. We are interested in strategy-proof mechanisms without money that can be used to decide the facility locations so that the obnoxious social welfare is maximized.

We made the first attempt to studying the obnoxious facility game without or with a bounded service range on different networks and provided different deterministic and randomized mechanisms with provable approximation ratios. Lower bounds on any deterministic strategy-proof mechanism for some networks are also obtained. We will discuss these results and introduce some characterizations of the strategy-proof deterministic mechanisms for different networks.