טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentYoav Tangir
SubjectThe d-Player Partition Bargaining Problem
DepartmentDepartment of Industrial Engineering and Management
Supervisor Mr. Rothblum Uriel (Deceased)


Abstract

The partition bargaining problem concerns a model where n items are partitioned among d players, with each player associating a positive (additive) utility with each item. A partition of the items to the players is then associated with a corresponding d-dimensional utility vector in Rd. Consequently, lotteries over partitions are also associated with the d- vectors of expected utility. The convex hull of the set of vectors of expected utility associated with lotteries over partitions forms a polytope in Rd, which we refer to as the partition polytope. The aim of this thesis is to explore the maximization of some real valued objective function (called a game function) defined over the partition polytope. One such function is the product function π(x)=∏ixi whose (unique) maximizer is the Nash  solution of the corresponding bargaining game (for which the origin serves as the disagreement point).

Our approach is to enumerate the partitions associated with vectors on the Pareto-optimal surface of the partition polytope. In addition, we study properties of lotteries over Pareto-optimal partitions. It is shown that, there is only one item to be randomized between each couple of players, in a lottery whose expected utility is Pareto-optimal. In all, the assignment of most items under such lotteries is deterministic, while a limited set of at most d(d-1)/2 items is to be randomized among the players. In particular, we develop an efficient computational method for approximating the Nash solution for the corresponding Nash bargaining game.