We consider the bipartite matching problem on a set of agents and a set of programs.
Each agent and every program has a preference ordering over a subset from the other side.
The goal is to compute an assignment of agents to programs such that an agent is matched to at
most one program. In the standard setting, every program also specifies an upper-quota which represents the maximum number of agents that can be assigned to it in a matching. Stability is a well-studied notion of optimality in this setting. There exist applications which mandate that every agent must be matched. Additionally, the quotas at programs are derived from logistic requirements and may not be rigid. Motivated by these facts, we propose a setting in which programs do not have input upper-quota but instead have a non-negative integral cost as part of the input. The cost associated with a program denotes the cost of matching an agent to that program.

We consider envy-freeness as a notion of optimality with respect to input preferences, which is a natural substitute for stability in the absence of input quotas. We propose two optimization problems w.r.t. the
cost criteria -- minimization of the total cost of the matching (MINSUM) and minimization of the maximum cost spent at a program (MINMAX). We show a sharp contrast between the computational complexity of these two problems -- the MINMAX problem is polynomial time solvable whereas the MINSUM problem is strongly NP-hard and cannot be approximated within 7/6-epsilon, epsilon>0 unless P=NP even under severe restrictions. For the MINSUM problem, we present approximation algorithms for general instances and a novel primal-dual algorithm for a restricted hard case. We also perform empirical evaluation to assess the performance of our algorithms, the quality of the output matching and to compare the cost-controlled quota setting with the standard setting.