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?

  • $\begingroup$ 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. $\endgroup$ – Disenchanted Toad Sep 3 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.