Produrre un ordine totale o parziale da una relazione incoerente
Immagina di voler costruire un ordine totale da un insieme di elementi, $E$, ma la funzione di confronto produce risultati non deterministici. Produco un elenco di coppie di elementi (e, e) attraverso l'applicazione ripetuta della funzione di confronto, in modo tale che ogni elemento dell'insieme sia rappresentato almeno una volta.
Come posso utilizzare questo input per produrre un ordine totale? Qual è la classe di algoritmi che possono essere applicati qui?
Per maggiore chiarezza, fornirò un esempio concreto.
Quali sono i migliori condimenti per la pizza?
Il mio insieme di elementi $E$ include alcuni condimenti per pizza popolari: peperoni, formaggio, funghi, ananas, peperone, oliva.
Quindi, per ciascuno dei miei amici, scelgo sottoinsiemi di condimenti di dimensioni casuali e chiedo al mio amico di metterli in ordine dal migliore al peggiore. I miei amici rispondono diligentemente e creano l'input per il mio algoritmo:
- formaggio, peperoni, oliva
- formaggio, ananas, funghi, olive
- peperone, fungo, oliva
- peperoni, formaggio, oliva
- formaggio, peperone
Sembra che ci sia un ordine sfocato qui (tutti sono d'accordo che le olive sono le peggiori) ma i miei amici non sono arrivati a un consenso su quale sia la migliore guarnizione per la pizza: formaggio o peperoni. Considerando la posizione degli elementi negli input e la frequenza con cui si verificano, probabilmente produrrei un ordine simile a questo.
- formaggio> peperoni> peperone> ananas> funghi> oliva
Non sono sicuro di come formalizzarlo e farlo funzionare per input molto più grandi.
Penso che la soluzione coinvolga probabilmente i grafici e gli archi ponderati, ma non ho familiarità sufficiente con gli algoritmi dei grafi per riconoscere se questa è un'area di studio denominata. Mi sono già imbattuto in "ordinamento topologico", ma funziona solo per grafi aciclici diretti, e sono particolarmente interessato agli input che non possono produrre un DAG.
Ho anche notato che questo problema sembra simile al voto per i rappresentanti eletti. È, infatti, la stessa classe di problemi?
Risposte
È difficile dirlo senza più contesto e più modellazione. Richiederà alcune ipotesi su come i risultati della funzione di confronto si riferiscono all'ordine totale desiderato (nascosto).
È possibile che tu voglia il modello Bradley-Terry-Luce . In tal caso, esistono molti algoritmi standard. Guarda anchehttps://cs.stackexchange.com/a/85204/755.
È possibile che tu voglia un sistema di classificazione, come Elo, ecc.
È possibile che tu voglia un sistema di voto classificato , come IRV, metodo Condorcet, conteggio Borda o uno qualsiasi dei tanti altri. Hanno tutti vari difetti e compromessi. C'è una prova che nessun sistema avrà tutte le proprietà che potremmo desiderare - vedi, ad esempio, il teorema di Arrow e il problema della non transitività (che anche se ciascuna delle preferenze individuali del tuo amico è transitiva, cioè un ordine totale, allora non vi è alcuna garanzia che esista un ordine totale globale coerente con tutti loro).