I have a question regarding the uniqueness we need to prove in this question.

Consider items of price 0. Because we prove the prices are Walrasian, all unsold items will be such items.

For any set of items in the demand set, you can add / remove items of price 0 without changing its utility. This means if there are unsold items, there are multiple sets in the demand set, contradicting what we need to prove.

Can we assume the uniqueness is "up to elements of price 0"?

Opt is the maximum **social welfare**, the uniqueness of opt is independent of the prices. Also, adding an item of price zero **can** change the utility - a utility of a single item equals to its value minus its price (and if the agent already has a bundle the contribution for her utility from adding an item is its marginal value minus price).

I think that there was some confusion regarding what I meant by "unique". In this question, we need to prove the demand set of each agent has only one element - there is only one unique set in the demand set of each player.

Also, in this question we assume all valuations are unit-demand, which means that adding or removing items to a set of price 0 and value smaller than the value of the set doesn't change the set's utility.

An extreme example of this will be items of value and price 0, but in the context of the question, all unsold items which are of smaller value compared to agent i's set pose this problem as well.

Because adding and removing such items doesn't change the utility of agent i's set, I don't understand how their demand set can only have a single, unique set. I can always generate another, different set by adding/removing such an item.

You are right that in a unit demand valuation if you already have an item adding an item with price 0 **might** not change the utility (it can also change it if the new value is higher than the maximum without it). But anyway, my answer is no, the demand set is unique, not up to anything.

Assuming your answer in HW2 - Q3 , I think I misunderstood the meaning of OPT in this question.

OPT is defined as "OPT (i.e. maximum weighted matching)" - In the definition of a "matching" in graphs that I'm familiar with, no node can be matched twice. In the context of markets, it means that each player gets at most one item.

If I understand correctly, we usually assume that an allocation in a unit-demand market is a matching (i.e. each player gets at most one item, which is more restrictive), and we can assume this without loss of generality because the value of each set is determined by only one item.

Reading your answer, it seems like that you assume players can get more than one item in OPT. Is this the definition of a "matching" we should work with?

In a matching market each player gets at most one item. You are correct about that. The case in HW2 Q 3 is a matching market. There is also another assumption in the question - there is only **one** optimum (which is indeed, as you defined, a maximum weighted matching). It doesn't have to be like that of course in a general matching market. But in this question we prove that it leads, with the right prices, to a unique demand set for each agent.

Maybe it was confusing in this context, but in the previous answer I was talking about unit demand functions **in general** and the fact that adding an item with price 0 to a bundle of an agent can change the utility. You can think of many settings in which an agent **can** get a bundle of more than one item, even if she has a unit demand function. The fact that the function is unit demand doesn't restrict the number of item an agent can get. It depends on the mechanism and the restrictions of the market, and not the valuation function. You are right that the value for a bundle in a unit demand function is influenced only by one item, the most valuable item. When I said that adding an item with price 0 might change the utility I was talking about situation like the following: consider a unit demand function v over two items {a,b} which is defined as follows: v(a) = 1 , v(b) = 2. Consider a price vector: p(a) = 1, p(b) = 0. If the agent owns only {a} the utility is 0, if we add item b to her bundle we get: u({a,b}) = v({a,b}) - p({a}) - p({b}) = 2-1 -0 = 1 which is greater, even though we added an item of price 0.

I hope it is clearer now.