# choosing the best subset where the metric is based on pairwise relationship

I want to model the competition between agents. Say there is a set of agents, and at each time step each agent $$i \in \{0,1,\cdots, n-1\}$$ can select a nonnegative number $$x_i$$ from a given range $$[0, p]$$. Each agent's utility is

• proportional to its own choice
• inversely proportional to the sum of (a polynomial function of) other agents' choices and weights

The positive weight $$g(i,j)$$ between any agent $$i$$ and $$j$$ are known.

For example, the utility function can take the form $$f_i = \frac{x_i} {\sum_{j\neq i} x_j \cdot g(i, j)}$$.

I am interested in the problem of maximizing the total sum system utility across a given number of time steps, by finding the best agent action at each time step.

Obviously, at each time step, only a subset of the agents can choose a non-zero number. If the individual utility does not depend on the choice of others, I am aware that it is essentially a backpack problem; but with the interdependence, how is this type of problem classified and handled from the theoretical CS point of view?

• so far I am throwing heuristic techniques like greedy, multi-start and local search at the problem and the solution quality is acceptable. But would appreciate a theoretical characterization of this sort of problem. – Disenchanted Toad Sep 3 '19 at 23:16