# Problema decisionale

Un problema decisionale nell'ambito della matematica riguarda un problema di scelta in cui si deve prendere una decisione tra un elevato numero di soluzioni (ammissibili) alternative, sulla base di uno o più criteri. Si parla di problemi decisionali soprattutto all'interno del campo della matematica applicata e, più nello specifico, della ricerca operativa.
La versione in Inglese di questa voce definisce un problema decisionale come un problema, appartenente alla teoria della computabilità ed alla teoria della complessità computazionale, che può essere posto sotto forma di una domanda riguardante i dati in ingresso a cui possa essere data una risposta nella forma "si" oppure "no". Un esempio di problema decisionale è, dato un numero naturale, stabilire se si tratta di un numero primo.

## Caratteristiche

I problemi decisionali sono caratterizzati da:
* Numero dei decisori: chi decide la soluzione al problema.
* Numero degli obiettivi: in base a quali criteri è decisa la soluzione del problema.
* Grado di incertezza dei dati: con quali (quantitativamente e qualitativamente) informazioni si decide la soluzione del problema.
Sulla base di queste caratteristiche diverse sono le scienze e le tecniche che si prefiggono di studiare e risolvere il problema:
* Programmazione matematica: un decisore, un obiettivo.
* Programmazione multi-obiettivo: più obiettivi.
* Teoria dei giochi: più decisori.
* Programmazione stocastica: grado di incertezza dei dati maggiore di zero.

## Esempi

Classici esempi di problemi decisionali sono:
* Assegnamento e distribuzione di risorse limitate;
* Progettazione di reti;
* Ricerca di cammini minimi.

## Formalizzazione di un problema decisionale

Un problema di decisione è definito dalla sua forma canonica, ossia la quadrupla $(\Omega ,\Delta ,W_{\delta }(\omega ),K)$ dove $\Omega$ indica lo spazio degli stati di natura, $\Delta$ lo spazio delle decisioni, $W_{\delta }(\omega )$ la funzione di perdita e $K$ un criterio di ottimalità. In particolare, se si adotta un'impostazione bayesiana della teoria della decisione, $\Omega$ è sostituito dal corrispondente spazio di probabilità.
Una volta posto in forma canonica, allora tale problema è risolvibile come un problema di ottimizzazione: va cercato $\min _{\delta \in \Delta }K(W_{\delta })$.
Normalmente, si dota $\Delta$ di un preordinamento ponendo che $\delta _{1}\succeq \delta _{2}$ se $W_{\delta _{1}}(\omega )\leq W_{\delta _{2}}(\omega )$ per ogni $\omega \in \Omega$. Si dice in tal caso che $\delta _{1}$ è debolmente preferibile rispetto a $\delta _{2}$, o che la domina debolmente. Notare che l'uso di un preordinamento anziché di un vero e proprio ordinamento è giustificato dal fatto che possono esistere decisioni distinte con funzioni di perdita coincidenti.
Di solito si affianca a questa un'altra relazione, ossia $\succ$, dove $\delta _{1}\succ \delta _{2}$ se $W_{\delta _{1}}\leq W_{\delta _{2}},W_{\delta _{1}}\neq W_{\delta _{2}}$; si dice allora che $\delta _{1}$ è strettamente preferibile a $\delta _{2}$ o che lo domina strettamente. Tale definizione implica che la due funzioni di perdita $W_{\delta _{1}}$ e $W_{\delta _{2}}$ devono differire per almeno un punto $\omega$; una definizione alternativa è che $\delta _{1}$ domina strettamente $\delta _{2}$ se vale che $\delta _{1}\succeq \delta _{2}$ ma non che $\delta _{2}\succeq \delta _{1}$. È importante notare che questa relazione, non essendoci riflessività, non è un preordinamento.
Alcuni problemi decisionali possono essere definiti con una forma canonica leggermente diversa, $(\Omega _{\delta },\Delta ,W_{\delta },K)$, qualora lo spazio degli stati di natura dipenda dalla decisione scelta.

## Analisi preottimale

L'analisi preottimale consiste nell'effettuare elaborazioni teoriche su un problema di decisione senza ricorrere a un criterio di ottimalità, sfruttando le proprietà delle relazioni di preferibilità.

### Classe completa di decisioni

Un primo obiettivo dell'analisi preottimale è restringere lo spazio delle decisioni in modo che possa esserne scelta una più facilmente.
In particolare, si dice che una classe di decisioni $C$ è completa se per ogni decisione $\delta$ al di fuori della classe esiste nella classe un'altra decisione $\delta '$ strettamente preferibile a $\delta$. Se vale solo la preferibilità debole, allora si dice che la classe è essenzialmente completa.
Dunque, esaminando un problema decisionale, ci si può restringere a una classe completa di decisioni, dato che al di fuori di essa non c'è una decisione preferibile a un'altra al suo interno; in altre parole, le decisioni al di fuori di una classe completa non possono essere preferibili a tutte quelle all'interno della classe e dunque, in un'ottica di massimizzazione della preferibilità, non ha senso sceglierle.
Si indica normalmente con ${\mathcal {C}}$ l'insieme di tutte le possibili classi complete per un problema; tale classe, essendo $\Delta$ banalmente completa, non può mai essere vuota.
Una classe completa che non contenga in sé sottoclassi a loro volta complete è detta minimale. Essa fornisce la massima semplificazione possibile del problema di decisione.

### Decisione ammissibile

Una decisione è ammissibile se non esistono altre decisioni che le sono preferibili, e la classe delle decisioni ammissibili è denotata con $\Delta ^{+}$. È ovvio che una decisione ammissibile non dovrebbe essere scartata in un'analisi preottimale, ma va notato che la classe delle decisioni ammissibili non è sempre completa.
Tuttavia, è possibile dimostrare che la classe delle decisioni ammissibili corrisponde all'intersezione di tutte le classi complete. Inoltre, se questa è completa, è anche minimale; e se esiste una classe completa minimale nel problema decisionale, questa coincide con la classe delle decisioni ammissibili.