טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentDean Oren
SubjectSelection Mechanisms in Networks
DepartmentDepartment of Industrial Engineering and Management
Supervisors Professor Yakov Babichenko
Professor Moshe Tennenholtz
Full Thesis textFull thesis text - English Version


Abstract

The common motif of the studies presented in this work, is the omni-present situation of strategic agents who vote/review/confirm each other. Given a network of agents with directed (and possibly weighted) links, we investigate the possibility of a selection mechanism that maximizes some graph-theoretic value such as in-degree or progeny, while conforming to various axioms (e.g., strategy proofness, fairness, etc.). Our research is divided into four parts:

         Paradoxes in classical sequential voting. This part is not based on the above network model, but serves as a prelude to the second part. We extend here previously known findings on the counter intuitive outcome under subgame perfect equilibrium of a sequential voting.

         Sequential voting in networks. We show the limitations of subgame perfect equilibrium of the sequential voting as a selection mechanism in confirmation networks. In contrast to sequential voting under the classical model (which is discussed in the appendix), we establish both positive and negative aspects of this voting.

         Incentive compatible classification. Given a network with weighted directed links, we are looking for a mechanism to classify the agents to worthy and unworthy based on their average weights on their in-edges. The aim is to find a mechanism that will be as accurate as possible while ensuring that an agent will not be able to influence his own classification. Depending on the maximal out-degree in the network, we prove impossibility theorems and show that a common-practice procedure is a sound mechanism.

         Incentive compatible diffusion. Given an unweighted network, we are looking for a mechanism that will select a single agent with high influence (one whose messages in the network reach a large crowd), while being strategy proof. We present two different works on this problem. The first offers a family of mechanisms based on the intersection of two independent random walks. The main advantages of these mechanisms are the simple intuition behind them and the easy implementation. The second work narrows this problem for forests networks. In this work we offer two novel mechanisms. These mechanisms are less intuitive but offer a much better approximation ratio.