Solution Concept

A Solution Concept is a Criterion for determining whether a specific location in a search space is a solution.

Example(s):
Counter-Example(s):
- a Criterion Validity,
- an Eisenstein's Criterion,
- an Euler's Criterion,
- an Optimal Solution,
- a Stopping Criterion,
- a Thermodynamic equilibrium,
- a Weyl's Criterion,
See: Data Mining Task, Machine Learning Algorithm, Nash Equilibrium, Game Theory, Backward Induction, Forward Induction, Search Problem.

References

(Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Solution_concept Retrieved:2020-1-5.
- In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium.
  Many solution concepts, for many games, will result in more than one solution. This puts any one of the solutions in doubt, so a game theorist may apply a refinement to narrow down the solutions. Each successive solution concept presented in the following improves on its predecessor by eliminating implausible equilibria in richer games.

(Yu et al., 2019) ⇒ Lantao Yu, Jiaming Song, and Stefano Ermon (2019). "Multi-Agent Adversarial Inverse Reinforcement Learning". In: Proceedings of the 36th International Conference on Machine Learning (ICML 2019). ArXiv:1907.13220.
- QUOTE: A correlated equilibrium (CE) for a Markov game (Ziebart et al., 2011) is a joint strategy profile, where no agent can achieve higher expected reward through unilaterally changing its own policy. CE first introduced by (Aumann, 1974; 1987) is a more general solution concept than the well-known Nash equilibrium (NE) (Hu et al., 1998), which further requires agents' actions in each state to be independent, i.e. $\pi(a|s) = \displaystyle\prod^N_{i=1}\pi_i(a_i |s)$. It has been shown that many decentralized, adaptive strategies will converge to CE instead of a more restrictive equilibrium such as NE (Gordon et al., 2008; Hart & Mas-Colell, 2000). To take bounded rationality into consideration, (McKelvey & Palfrey, 1995; 1998) further propose logistic quantal response equilibrium (LQRE) as a stochastic generalization to NE and CE.

(Sammut & Webb, 2017) ⇒ Claude Sammut, and Geoffrey I. Webb. (2017). "Solution Concept". In: (Sammut & Webb, 2017). DOI:10.1007/978-1-4899-7687-1_764
- QUOTE: A criterion specifying which locations in the search space are solutions and which are not. In designing a coevolutionary algorithm, it is important to consider whether the solution concept implemented by the algorithm (i.e., the set of individuals to which it can converge) corresponds with the intended solution concept.

(Alonso et al., 2007) ⇒ Oscar Alonso, Fabio A. Gonzalez, Fernando Nino, and Juan Galeano (2007, August). “A Solution Concept For Artificial Immune Networks: A Coevolutionary Perspective". In: Proceedings of The International Conference on Artificial Immune Systems (pp. 35-46). Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-73922-7_4
- QUOTE: A solution concept is a set of criteria used to determine which elements of a search space can be considered as solutions to a particular search problem. A solution concept partitions the search space into solution regions and non-solution regions. Therefore, a population-based algorithm should be designed in such a way that the population converges to solution regions. It is important to notice that a solution concept is specific to a particular search problem.
  Every search problem defines a solution concept, which characterizes what is being searched. Also, each search algorithm implements a solution concept, which corresponds to what it actually searches. Sometimes, coevolution dynamics generates unexpected behavior. According to Ficici (2004), this is related to a mismatch between the intended solution concept and the algorithm’s solution concept. Therefore, solution concepts are a formalism useful in the design of proper algorithm dynamics, performance measures, and stopping criteria.

(Ficici 2004) ⇒ Sevan Gregory Ficici (2004)."Solution Concepts in Coevolutionary Algorithms". PhD thesis, Computer Science Department. Brandeis University, USA.
- QUOTE: Fundamental to all search problems is the notion of a solution concept. Whatever properties our problem domain may possess, and however we embed that domain into a search space, we require a solution concept to indicate which locations in the search space- if any - constitute solutions to our problem. A solution concept thus partitions a search space into two classes: Solutions and non-solutions. Typically, the two classes are distinguished in a systematic way—by some number of measurable properties that are present or absent in class members; in general, however, any arbitrary binary partition constitutes a valid solution concept. (Real-world search problems are usually difficult enough that we must be content with satisficing rather than optimization; nevertheless, any satisficing problem can be formally stated as an optimization problem, where a solution is any result that we deem “good enough.”) Thus, a search space can have an exponential number of solution concepts applied to it. When we apply a particular solution concept to a search space, we obtain a particular search problem.