We consider a private variant of the classical allocation problem: given k
goods and n agents with individual, private valuation functions over bundles of
goods, how can we partition the goods amongst the agents to maximize social
welfare? An important special case is when each agent desires at most one good,
and specifies her (private) value for each good: