2. We consider the allocation of m indivisible items to n agents, in order to maximize...

 

Transcribed Image Text:

2. We consider the allocation of m indivisible items to n agents, in order to maximize the sum of valuations. (a) Suppose each agent i is interested in precisely one subset S; of the m items; her value for S; or any superset of Si is vi 0, and her value for any other set of items is 0. Given all the Si's and vi's as input, show that an allocation T,,Tn that maximizes the total values is NP-hard to compute. (By total value we mean the sum of the agents' values for their allocated subsets.) (b) Suppose each agent i has value v; (j) for each item j, and then for any subset S; her value is min{jes vi(j), B}, where B; can be seen as some budget. Given all v(j)'s and Bi's as input, show that an allocation T,,Tn that maximizes the total values is NP-hard to compute. 2. We consider the allocation of m indivisible items to n agents, in order to maximize the sum of valuations. (a) Suppose each agent i is interested in precisely one subset S; of the m items; her value for S; or any superset of Si is vi 0, and her value for any other set of items is 0. Given all the Si's and vi's as input, show that an allocation T,,Tn that maximizes the total values is NP-hard to compute. (By total value we mean the sum of the agents' values for their allocated subsets.) (b) Suppose each agent i has value v; (j) for each item j, and then for any subset S; her value is min{jes vi(j), B}, where B; can be seen as some budget. Given all v(j)'s and Bi's as input, show that an allocation T,,Tn that maximizes the total values is NP-hard to compute.