Managers and employers use an array of rewards to attract and retain quality employees. An increasingly significant component of the overall compensation is the employee's benefits package. Flexible packages offer more choice but also incur higher decision costs. We conduct an experiment on choices over stylized benefits packages where discrete 'goods' have multiple attributes affecting the payoff function. We investigate the degree to which these complications affect choices. Eighty subjects play an individual-choice decision-cost game where they are implicitly asked to solve a complex programming problem. Our main results are that: (a) individual subjects respond to the relative tradeoff between the attributes, (b) some combinations of the attributes (apparently) entice subjects to search more and thus earn more, and (c) most subjects appear to adopt a heuristic that approximates the optimal solution. Further, subjects appear to value the right to make choices, as they rarely choose a fixed payoff option with a known payoff and low decision cost, even when the fixed payoff is 80% of the maximum possible under the decision-making task.