# Maximize utility given an arbitrary number of goods and the condition that exactly X number of items must be bought

How does one maximize the utility given some budget restriction, an arbitrary number of different goods (with varying utility and prices) and the added condition that exactly X number of items must be bought?

I guess this must be done algorithmically, but I have no idea how.

• Sounds like a very typical problem in constraint maximization. In general, you can use the Lagrange method and derive the Kuhn-Tucker conditions. However, if you want a more specific answer, you'd need to edit your question to make it more concrete: tell us what the utility function looks like, what are the constraints, etc. – Herr K. Feb 20 '17 at 18:48
• @HerrK. I think this seems like a discrete optimization problem but frankly not enough details are given. – Giskard Feb 20 '17 at 20:42
• By "X number of items" you mean "X number of different goods"? – Alecos Papadopoulos Feb 20 '17 at 20:55
• @AlecosPapadopoulos No, there will be an arbitrary number of goods to choose from, but X number of items must be bought. Let's say there's 2 goods and we absolutely need to buy 3 items with some budget constraint. In this example we might maximize the utility buying 1 item of goods A and 2 items of goods B given our budget constraint. But how to determine which combination maximizes our utility given an arbitrary number of goods and X number of items? – Dennis Feb 20 '17 at 22:04
• @denesp What details would you need? – Dennis Feb 20 '17 at 22:06

Utility maximization problem is \begin{eqnarray*} \max_{x_1, x_2, \ldots, x_n} && u(x_1, x_2, \ldots, x_n) \\ \text{s.t.} && \sum_{i=1}^n p_ix_i \leq M \\ && \sum_{i=1}^n x_i = X \\ && x_i\in\mathbb{Z}_+ \ \ \forall i\in\{1,2,\ldots, n\} \end{eqnarray*}

If we ignore the budget constraint, the equation $\sum\limits_{i=1}^n x_i = X$ has ${X+n-1\choose n-1}$ solutions. List them, sort them from high to low by utility, and then identify the highest one in the sorted list that also satisfy the budget constraint.

If $u$ is strictly increasing, differentiable and quasi-concave on $\mathbb{R}_+^n$, then one can solve the utility maximization problem in the usual way by ignoring the $\sum_{i=1}^n x_i = X$ constraint, and then inspect the integral solutions of $\sum_{i=1}^n x_i = X$ that surrounds the solution of the utility maximization problem, and choose the best amongst them to get the final solution.

$$\max U(z_1,...,z_n)$$

$$s.t. \sum p_iz_i \leq I$$

and

$$s.t. \sum z_i = X, \;\;\; z_i\in N$$

So you have an additional linear constraint, but also, as noted in a comment, the $z_i\in N$ constraint makes this an optimization problem where the decision variables are discrete (specifically integers), meaning that, formally speaking, you don't get to have derivatives.

In practice, many discrete optimization problems are attacked by "pretending" that we can calculate derivatives, (so form the Lagrangian with the two constraints, obtain Karush-Kuhn-Tucker conditions, etc), obtain the maximizer vector in this way, and then check what happens as we round up or down its elements so that they become integers.

You also need to check the budget constraint is not violated by these roundings, and allow only those combinations that don't. Here the budget constraint as inequality is important because the permissible maximizer vector of $z_i$'s most likely won't fully exhaust the budget.

See here for some introductory bits on Integer Programming.

Dennis - as it stands, your question is not always possible to answer. At least, not in the way that I think is of interest to you. Specifically, restricting a consumer's choices to some finite, arbitrary set of choices, endowing that agent with some amount of wealth and then necessitating that the consumer purchase a certain amount of goods is not always feasible whenever those goods are discretized.

Suppose some agent $i$ has wealth $w$ and faces choices between goods in the set
$G \equiv$ {$g_1,...,g_n$} where we assume that we can innumerate over prices s.t. $p_{g1}<p_{g2}<...<p_{gn}$. If we suppose $w<p_{g1}$, then we can't satisfy any type of requirement that this agent must purchase some minimum amount of goods, whether we define the minimum over types or amounts of goods. This is just the most simple example of which I can think to illustrate a point. You could also think in terms of needing to fulfill some minimum requirement of $n$ goods. Further, we could have that agent $i$ faces $w-p(n-1)$

The only 'maximum' agent $i$ can achieve is $U(w)$ since this agent cannot participate in this market.