# solution concepts

Anthony • Dec 16, 2021 • #coev #complexity #solutions #domains

There is a lot to say about these, but primarily I am coming from the perspective of theory, where the notion is meant to be "arg min for ". Below are some details.

First, a punchline: should consist of the specification of an interactive domain, a solution concept, and some form of evolutionary dynamics over the interactive domain that aims to find solutions as specified by the solution concept.

When optimizing functions, there are a number of possibilities for specifying exactly what you're trying to accomplish. If you have some function $f\colon S\rightarrow\mathbb{R}$, "maximizing" it could mean:

• Finding the value $r\in\mathbb{R}$ that $f$ actually takes on some unspecified input that is larger than or equal to any other value the function takes on other inputs
• Finding an element $s\in S$ such that $f(s) = r$
• Finding all elements in $S$ that $f$ gives value $r$

The last, or possibly the second to last, are sometimes called arg max. All this puts aside things like suprema, or the possibility that $f$ never takes a maximum value.

When it comes to a two-input function like $p\colon S\times T\rightarrow R$, a simplest-possible interactive domain, a new layer of complexity is added

• $R$ may have incomparable elements
• It is not specified whether we are seeking an $s\in S$, a $t\in T$, a pair $(s,t)\in S\times T$, or something else such as an ensemble

What we do with both these points needs to be clarified before we can begin to talk about optimizing. The interactive domain definition specifies who gets the value from a function like $p$ (second point), while the solution concept specifies what solutions are selected given all this information.

As with max or arg max, solution concepts are in a sense polymorphic. Rather than try to write down what they are in full generality using symbols, I'll just say that a solution concept should be such that it specifies a well-defined collection of solutions for any view/state of an interactive domain.

In the case of a single function $p\colon S\times T\rightarrow R$ interpreted as giving values to elements of $S$ such that higher up $R$'s order is better, then a solution concept might take a form like $\partial\colon\mathscr{P}(S)\times \mathscr{P}(T)\rightarrow\mathscr{P}(S)$. In algorithms that seek Nash equilibria, the output might be $\mathscr{P}(\Lambda^S)$ (sets of mixtures of elements of $S$) instead. In algorithms that seek Pareto non-dominated fronts, the output might be $\mathscr{P}(\mathscr{P}(S))$ (there are technical reasons why it does not suffice to output a single Pareto front). So a slight generalization is to say the solution concept maps the "raw material" from the interactive domain or search algorithm to a collection of configurations; the solution concept, or some other device, will have to specify what these configurations are then.

Sevan Ficici's PhD dissertation develops a notion of monotonic solution concept and shows these have nice ratcheting properties. I've done some work on that develops techniques for (some) non-monotonic solution concepts.