Algorithmic mechanism design on distributed computing and facility location


Student thesis: Doctoral Thesis

View graph of relations


  • Qiang ZHANG

Related Research Unit(s)


Awarding Institution
  • Minming LI (Supervisor)
  • Xiaotie DENG (Co-supervisor)
Award date2 Oct 2013


The field of algorithmic mechanism design has drawn much attention in the recent years. Its idea comes from algorithm design with additional considerations on inputs. In algorithm design, the objective is usually to achieve desirable outcomes when inputs are given. However, in algorithmic mechanism design, these problems mostly occur in a decentralized environment, meaning some inputs are reported by agents in order to achieve a desirable outcome. This scenario would give agents incentives to submit their inputs strategically, which may lead to good outcomes for themselves. These strategic plays also make outcomes unpredictable. One of the main challenges in algorithmic mechanism design is to design mechanisms to solve these complicated problems, in which agents may have different interests or conflicting interests. Hence, mechanisms must take into consideration the rational behaviors by agents. Very often mechanisms that output optimal outcomes (e.g. social welfare is maximized) cannot avoid such strategic plays by agents. The ideal mechanisms are the ones where it is better for agents to reveal their true information regarding inputs. We call such mechanisms strategyproof mechanisms. Besides avoiding strategic plays by agents, we would like to design strategyproof mechanisms to approximate the optimal outcomes. This thesis explores the design of strategyproof mechanisms on two specific problems. First, the strategyproof mechanisms for allocating and pricing CPU time slots in distributed or cloud computing services are studied. In particular, a concrete model for distributed or cloud computing services is studied and greedy-based mechanisms are proposed to solve this problem. From this model, a new parallel machine scheduling model is derived. Previous existing models on parallel machine scheduling require each task to be processed on a constant number of machines, which may not be applicable in some practical applications. In the proposed model, this constraint is relaxed by allowing tasks to be scheduled at any number of machines during its process. The minimum weighted completion time is examined and an approximation algorithm is developed in this study. The simple Largest-Ratio-First schedule is shown to give a 2-approximation for this problem. An essential condition for previous strategyproof mechanisms to avoid agents' strategical plays is by employing payments. The other part of this thesis focuses on strategyproof mechanism design without payment by studying strategyproof mechanisms without money when a single facility will be located on a real line. Each agent has a location on the line which is private information and is asked to report it to a central authority, which then decides where to locate the facility, aiming to optimize some function of the locations reported by agents. The self-interested agents would want to minimize their costs, which are their distances away from the facility. This cost function is often called singled-peaked preference. To generalize and complement existing models in the literature, two following extensions are studied. First, strategyproof mechanisms without payment are investigated when agents have different costs for the facility built at the same distance away from their locations. A natural approach is to consider the case of weighted agents. It shows that existing mechanisms for unweighted agents still achieve the best performances in the well-studied objectives when agents are weighted. The performance of such mechanisms highly depends on the maximum and minimum weights of agents. To address this drawback, a novel threshold-based approach is proposed to capture agents' uniqueness. It shows that the mechanism, which outputs the optimal outcome from locations reported by agents, is strategyproof. These two new concepts give the initial study on mechanism design without payment for non-identical agents. Second, singledpeaked preference may not be applicable in some real-life situations. To complement the study in facility location games, strategyproof mechanisms without payment are studied when agents have so-called double-peaked preference in facility location games. The performances of such mechanisms with respect to different objectives are also analyzed. These results significantly improves our knowledge and understanding on mechanism design of facility locations.

    Research areas

  • Electronic data processing, Distributed processing, Algorithms