Let $v_i(S)_{i \in [n], S \subseteq G}$ be a collection of Gross Substitute valuations. I am wondering if I can add a small perturbation to each valuation and still get Gross Substitute valuations. Essentially, is there a small interval for each valuation where it remains to satisfy Gross Substitutes?
Asked
Active
Viewed 22 times
0
-
Could you provide a definition of the gross substitute property? – Nameless Apr 18 '15 at 11:36
-
Sure. We say a set of valuations obeys gross substitutes if the following holds: Let $p$ be any price vector over elements in $G$ where $p(S) = \sum_{g \in S} p_g$ and for any player $i \in N$ we have $D_i(p) = \arg max_{S\subseteq G}{v_i(S) - p(S) }$. For a set $S \in D_i(p)$, any $p' \geq p$ (coordinate wise) there is a set $T \subseteq G$ such that $S \cup T \backslash P \in D_i(p')$ where $P = {g \in G: p_g < p_g' }$ – Eager Student Apr 18 '15 at 12:24