1  Consider a public endowment problem with 6 individuals,  {i1 ,i2 ,i3 ,i4 ,i5 ,i6 }, and  6  objects,  {a1 ,a2 ,a3 ,a4 ,a5 ,a6 }.   The  individuals’  preferences  over  these objects are as follows:

Pi3

a .  Give an example of a wasteful assignment  (and explain why) .

b .  Give an example of an inefficient assignment, di↵erent from that you found in a .  (and explain why) .

c .  Find the assignment produced by SD for the order i6 ,i5 , ...,i1  .

d .  Show, without referring to SD, that the assignment you obtained in c .  is efficient .

e .  Suppose that i2  lies about her preference by reporting the following alter- native ranking:

i2

a5

a4

a3

a6

a1

a2

What’s the assignment produced by SD if i2 reports Pi\2  and every other in- dividual reports truthfully (i .e . , the above rankings)?  Is i2  strictly better- o↵?

2.  Five friends, Alice, Ben, Carly, Dan, and Emily all work together at the local favorite ice cream shop .  As high school seniors, they each only have the abil- ity to work  one  of the five  available time  slots,  labeled  A through  E .   Their preferences for these time slots are illustrated in the table below .

PAlice PBen PCarly PDan PEmily

C         D         A         C          A

B         B         B         A          C

A                     E         D         E

D                     C                      D

E                                              B

Remember that  if an  object  is  not  listed  in  an  individual’s preferences,  they consider it unacceptable (in this example, this may possibly be due to schedul- ing constraints) .

a .  Propose an assignment that fails individual rationality  (IR) . Suppose we have the following assignment µ:

µAlice  = C

µBen  = D

µCarly  = E

µDan  = ;

µEmily  = A

b .  Is  this  assignment  wasteful?   Is  this  assignment  IR?  Is  this  assignment efficient?  Explain each answer .

Suppose we made a slight adjustment and created a new assignment µ\ :

µ = C

µ = D

µ = A

µ = ;

µ = E

c .  Do any of your answers to part b .  change under this new assignment?

d .  Find the  assignment  created  by  using the  serial  dictatorship  (SD)  algorithm with the following order:  Dan, Alice,  Emily,  Ben,  and  Carly.  Repeat part b . with this assignment .

3.  Alice,  Carly, Dan,  and Emily all decide to attend  State College  (Ben instead leaves to  attend  City  College) .  As incoming freshman to  State  College, they apply for and enter the housing lottery over the schools five dorms:  H1 , H2 , H3 , H4 , and H5 .  For simplicity sake, assume each dorm can only house 1 student . As part of the application they rank their preferences over the dorms, shown below

PAlice PCarly PDan PEmily

H4             H2            H3            H5

H3             H1            H4            H4

H5             H3            H5            H1

H1             H4            H1            H2

H2             H5            H2            H3

a .  Is it possible to construct a final assignment that does not satisfy IR? If “yes,” provide an example .  If “no,” explain why not .

b .  Notice  that  there  are  five  potential  dorms  to  be  assigned  but  there  are only four students to be assigned .  Does this mean that any assignment is necessarily wasteful?  Explain why or why not .

c .  Intuitively, we can think of the following assignment as the “best” assign- ment:

µAlice  = H4

µCarly  = H2

µDan  = H3

µEmily  = H5

since every individual receives their top pick .  Clearly this is an efficient assignment .  Is this the only efficient assignment?  If “yes,” explain why. If “no,” provide another efficient assignment .

4.  Alice, Ben, Carly, and Dan do incredibly well in college and the four of them go to medical school and eventually become doctors .  They coincidentally enter the  labor  market  in  the  same  area  and  form  preferences  over  four  potential hospitals W , X , Y , and Z, to work in .  Management at each hospital also form priority orderings on the four doctors (including the possibility of determining one or more is unacceptable) .

PAlice      PBen      PCarly      PDan

Alice      Dan      Alice       Ben

Dan      Alice     Carly     Alice

Carly    Carly      Dan      Carly

Ben        Ben        Ben       Dan

a .  Consider the following assignment:  Alice is assigned to Y , Ben is assigned to  Z,  Carly  is  assigned  to  W,  and  Dan  is  assigned  to  X .    Does  this assignment lead to justified envy?  Explain .

b .  Consider a new assignment:  Alice is assigned to W, Ben is assigned to Z , Carly is assigned to Y , and Dan is assigned to X .  Does this assignment lead to justified envy?  Explain .

c .  Use the  SD algorithm with the following order:  Ben, Alice,  Dan,  Carly. What assignment does this result in?  Does this assignment lead to justi- fied envy?

5.  This problem revisits the notion of individual rationality in public endowment problems with priorities, when not all individuals are acceptable to all objects . Suppose that 5 public houses  (objects) must be allocated among a group of 5 families  (individuals), and imagine that the following tables describe rankings and priorities, where f denotes a generic family, and h a generic house:

Pf1        Pf2        Pf3        Pf4        Pf5

Remember  that  objects  not  listed  on  rankings,  or  individuals  not  listed  on priorities, are considered unacceptable .  One way to interpret these tables is to imagine that they capture, implicitly, some heterogeneity among the di↵erent houses  (e .g . ,  number  of  rooms)  and  families  (e .g . ,  number  of  members  in  a household .)

Consider  the  following  alternative  definition  of  individual  rationality  (IR), termed “IR for all:”

Definition 1. An assignment µ is IR for all if µi Pf ; for every f  and µh ⇡h ; for every h,

where ⇡h  denotes the priority of house h .  In words,  “IR for all” requires that no individual and object receives an assignment that is unacceptable .

a .  Is “IR for all” stronger or weaker than IR? i .e . , must an assignment that is IR also be “IR for all” or the other way around?  Why?

b .  Does Serial Dictatorship  (SD) satisfy “IR for all”?  i .e . , does SD produce an assignment that is “IR for all” for every order of individuals?  Why?

6.  This  problem  invites  you  to  think  about  an  alternative  notion  of  efficiency, termed “efficiency for all”, in public endowment problems with priorities .  To define this new notion, let A denote the set of all individuals and objects  (A stands for “agents .”) .  Thus, a will denote either an individual or an object .

Definition 2. An  assignment µ is efficient for all if there is no  alternative assignment µ\  such  that  every agent strictly prefers µ\  to µ,  or is  indi↵erent, and there  exists  at least one agent that strictly prefers µ\  to µ .

Notice that this is the same definition of efficiency we discussed in class, with the exception that this definition is in terms of agents instead of individuals . Thus, this definition takes into account not only individuals’ rankings, but also objects’ priorities .

a .  It turns out that “efficiency  for  all”  is weaker than  efficiency;  i .e . ,  if an assignment is efficient, then it is efficient for all .  Explain why, as precisely as you can, without using any particular example .

b .  Is the converse true?  i .e . , is it true that if an assignment is “efficient for all”, then it must be efficient?  If “yes”, explain why.  If “no”, provide an example .

7.  This  problem  revisits  the  SD  algorithm  in  public  endowment  problems  with priorities .   Consider  a  di↵erent  version  of  SD  in  which  objects  are  the  ones picking  individuals,  given  some  order .    Let’s  term  this  new  algorithm  OSD (where  O stands for ”object .”)  Specifically,  OSD fixes some order of objects, and objects choose in that order, among the individuals that were not picked before by some other object .