M.Sc Thesis

M.Sc StudentBen-Dan Itay
SubjectTime Sharing under Dichtomous Preferences
DepartmentDepartment of Mathematics
Supervisor PROF. Ron Holzman


This thesis deals with the theory of collective choice under dichotomous preferences. Consider mathematical models of situations in which agents (machines, people) have different preferences.

In our setting the preferences are partitions of the set of outcomes, one for each agent.

Each agent partitions the outcomes into two sets: good and bad.

A mechanism is needed to decide how to divide the resource, usually time, into shares among the outcomes. Typical examples to such situations are scheduling and time sharing problems.

The main question is: what is a good mechanism? To answer this question, we define properties of mechanisms that reflect intuitive notions of efficiency, justice, reasonableness, and

so on. In the second phase we try to characterize the mechanisms that satisfy some of these properties and reveal additional information about them.

Given a fixed and known mechanism, the participants will choose strategies with every agent trying to get the maximum utility for himself, while taking into account that the other agents are doing the same. The theory of collective choice under dichotomous preferences uses ideas from game theory to try to anticipate the results of such behaviors, and to examine the mechanisms in terms of the induced games.

In our work we obtained the following: we found a characterization of the cases where two different notions of efficiency coincide, we characterized the Utilitarian mechanism which averages over all the outcomes approved by the maximal number of agents. We also improved  the upper bound (compared to previous works) on the minimal agent’s utility in an efficient, anonymous and neutral mechanism where truth telling is the dominant strategy.