HW2 - Q3

HW2 - Q3

Yotam Nitzan 23 May 2018 17:52

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.

Re: HW2 - Q3

KineretS 25 May 2018 13:12

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.

Last edited on 28 May 2018 19:47 by KineretS Show more

Re: HW2 - Q3

eldarsehayek 28 May 2018 21:14

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?

Re: HW2 - Q3

Yotam Nitzan 29 May 2018 14:49

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 ?

Last edited on 29 May 2018 14:49 by Yotam Nitzan Show more

Re: HW2 - Q3

KineretS 29 May 2018 20:59

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.