  Many scenarios where agents with restrictions compete for resources can be
cast as maximum matching problems on bipartite graphs. Our focus is on resource
allocation problems where agents may have restrictions that make them
incompatible with some resources. We assume that a Principle chooses a maximum
matching randomly so that each agent is matched to a resource with some
probability. Agents would like to improve their chances of being matched by
modifying their restrictions within certain limits. The Principle's goal is to
advise an unsatisfied agent to relax its restrictions so that the total cost of
relaxation is within a budget (chosen by the agent) and the increase in the
probability of being assigned a resource is maximized. We establish hardness
results for some variants of this budget-constrained maximization problem and
present algorithmic results for other variants. We experimentally evaluate our
methods on synthetic datasets as well as on two novel real-world datasets: a
vacation activities dataset and a classrooms dataset.
