The uniqueness refers to all the allocations, even ones that give more than one item to an agent.
Notice that in a market s.t. all agents have unit demand valuation functions- if there is an allocation (not necessarily and a matching) that yields SW of value v, there is also a matching with SW at least v. In a general setting there might be more than one optimum, but in the current question we assume only one optimum, hence the optimum is a matching and there is no other allocation that gives the same SW.
Recent Forum Posts
I don't understand your claim. Since we're talking about optimal matching, an agent can be assigned with at most one item. You can't just assign the not-taken item to an agent, it will not be a legal matching and won't contradict the uniqueness.
I think one should assume that there are no outgoing edges in G_I from vertix j if j was not sold under OPT.
This makes the graph well defined and makes it possible to prove the theorem.
Is this an acceptable assumption ?
Why is that the case? The uniqueness is for an optimal matching, not optimal SW allocation, therefore it must leave out an item if #items > #agents. Consider a case where there are 2 agents {1,2} and 3 items {a,b,c} such that v1(a) = v2(b) = 2, v1(b) = v2(a) = 1, v1(c) = v2(c) = 0. There's a single optimal matching (1,a), (2,b) with SW = 4, and the item c is left unmatched. In order to prevent unmatched items from hindering the proofs, I assumed the weight of outgoing edges of unmatched items is 0, and then their affect is basically neutralized from the proofs, is it acceptable?
The greedy process takes polynomial time only if we can assume value queries are answered in polynomial time. I can't see a way to avoid that, and it's a reasonable assumption given the value function is fixed, so I'll assume that's the case and write it explicitly.
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.
in discussion Discussions / Spring 2018 Forum » Looking to switch presentation date
אנחנו נשמח להחליף תאריכי הצגה מה6.6 ל13.6
צרו קשר דרך:
mendelsohn@mail,tau,ac,il
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?
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.
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.
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 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"?
in discussion Discussions / Spring 2018 Forum » Looking to switch presentation date
We would like to switch dates with you.
Please contact me at: yotam.nitzan@gmail . com
in discussion Discussions / Spring 2018 Forum » Looking to switch presentation date
We are presenting on the 13.6
Does anyone present on the 6.6 and wants to switch with us?
I'm not sure that I understand your question. The greedy process takes polynomial time. Do you agree on that?
The first option: if there is a tie the agent chooses the item that leads to the worst SW. For example, if agent 1 wants items a and b equally and agent 2 wants item a then if agent 1 arrives first she takes item a.
Re answering your question- when the optimum is unique there can't be non taken item, such item can go to any agent without changing the optimum which contradicts the uniqueness.
Hi,
I managed to prove that the greedy algorithm indeed outputs a correct result for a demand query, however I'm having trouble proving poly(m) time. In each iteration the algorithm needs to compute v(j|S) for items, and we were taught that computing v(j|S) requires computing a demand query several times. Given at worse case the greedy algorithm needs to compute v(j|S) when |S| = m-1, I realized that computing v(j|S) using the greedy algorithm as demand query oracle will result in infinite recursion, since computation of v(j|S) will require computing demand query over items set S + {j} which is the full item set. How should I proceed?
Thanks,
Eldar
Assume worst case as in assume the worst possible SW in this arrival order
or assume worst case as in assume the best poosible SW in the arrival order (which is the worst case when trying to show SW is low)
For your first question- no, you need to show an example that works for any prices, even identical.
Tie breaking can be arbitrary. Assume worst case option (this should help you).
In the definition of G_I it says that:
"For each pair of items j, j', let the weight of the edge (j, j') in G_I be v_i({j}) − v_i({j'}),
where i is the agent that was matched by M to j."
What happens if j was not matched to any agent in M ?
This case isn't defined explictly.
Can one assume that it means j has no outgoing edges ?
Thanks.