We consider the problem of balancing the penalties associated with budgetary slack (being underbudget) and cost overruns in the project portfolio selection problem by addressing randomness in project costs and making individual project budgets decision variables. Setting the budget for a single project is shown to be analogous to the newsvendor problem. For related versions of the project portfolio selection problem we provide optimal and heuristic procedures. Numerical experiments are used to test the procedures and provide managerial guidelines. We show project budgets should be set so that each project in the portfolio has the same probability of running over budget, it is better to have a larger number of projects with less than ideal funding compared to a smaller number of projects with ideal funding, and substantial opportunities to select more projects with a higher expected profit are available if an aggregate portfolio budget is used.