Kans op een positie bij loting onder voorwaarden

[Hans Kuiper]

Ik probeer duidelijk te krijgen wat de invloed is van een beslissingsalgoritme t.o.v. een loting onder voorwaarden.
Er liggen 5 balletjes in een vaas. Balletje A t/m E. Elk balletje stelt een combinatie voor van prijs en kwaliteit. Alleen de rangorde in prijs en in kwaliteit is hierbij van belang. Het verschil in prijs en kwaliteit is niet van belang. Het balletje met de hoogste kwaliteit is balletje A, aflopend naar balletje E met de laagste kwaliteit.
De balletjes worden één voor een uit de vaas getrokken. Er kan alleen een balletje worden getrokken dat niet wordt gedomineerd door een ander balletje. Een balletje wordt gedomineerd door een ander balletje als dat andere balletje zowel lager in prijs als hoger in kwaliteit is. Door de trekking van een balletje wordt zijn dominantie ook weggenomen.
Er zijn 120 (5!) verschillende beginsituaties mogelijk.
Wat is voor elke beginsituatie de kans van elk balletje om als 1e t/m 5e te worden getrokken?
Ik kan voor elke beginsituatie dit probleem oplossen door het tekenen van een kansenboom. Maar is er ook een algemene oplossing mogelijk? Kan dit in een spreadsheet worden opgelost, met of zonder macro?

[RedCat]

Elk balletje stelt een combinatie voor van prijs en kwaliteit.
...
Het balletje met de hoogste kwaliteit is balletje A, aflopend naar balletje E met de laagste kwaliteit.

Heb je ook informatie over de prijzen op de balletjes?

[Hans Kuiper]

Er zijn 120 verschillende prijsvolgordes mogelijk van ABCDE t/m EDCBA. Ik kan ze per geval doorrekenen door eerst de permutaties die niet kunnen te schrappen en vervolgens van de overgebleven permutaties de kansenboom te tekenen en de kans van de permutatie te berekenen. Vervolgens de kans voor balletje voor elke plek bepalen.
Ik kan een 5x5 matrix maken waarin de dominantie van elke is verwerkt bv +1 is dominant en -1 is dedomineerd en 0 is geen van beide.
Kan ik deze matrix, waarin dus alles al vastligt, ook gebruien om rechtstreeks deze kansen te berekenen.

[Hans Kuiper]

Verbeterde versie
Er zijn 120 verschillende prijsvolgordes mogelijk van ABCDE t/m EDCBA. Ik kan ze per geval doorrekenen door eerst de permutaties die niet kunnen te schrappen en vervolgens van de overgebleven permutaties de kansenboom te tekenen en de kans van de permutatie te berekenen. Vervolgens de kans van elk balletje voor plek 1 t/m 5 bepalen.
Ik kan een 5x5 matrix maken waarin de dominantie van elk balletje is verwerkt bv +1 is dominant en -1 is gedomineerd en 0 is geen van beide.
Kan ik deze matrix, waarin dus alles al vastligt, ook gebruiken om rechtstreeks deze kansen te berekenen?

[RedCat]

Als voor de kwaliteit van de ballen geldt: A > B > C > D > E,
en de prijzen 1 < 2 < 3 < 4 < 5 worden als een permutatie over de ballen verdeeld,

dan geldt voor permutatie [3, 1, 5, 4, 2] deze dominantie-tabel (1 ↔ bal linker kolom domineert bal eerste regel):

Code: Selecteer alles

    A3  B1  C5  D4  E2
A3   0   0   1   1   0
B1   0   0   1   1   1
C5   0   0   0   0   0
D4   0   0   0   0   0
E2   0   0   0   0   0

A3 domineert C5, want de kwaliteit van A is hoger en de prijs is lager.

Dat zou dan deze kansboom geven:

Code: Selecteer alles

--- 0.5000 A --- 0.5000 B --- 0.1667 C --- 0.0833 D --- 0.0833 E
                                       --- 0.0833 E --- 0.0833 D
                          --- 0.1667 D --- 0.0833 C --- 0.0833 E
                                       --- 0.0833 E --- 0.0833 C
                          --- 0.1667 E --- 0.0833 C --- 0.0833 D
                                       --- 0.0833 D --- 0.0833 C
--- 0.5000 B --- 0.2500 A --- 0.0833 C --- 0.0417 D --- 0.0417 E
                                       --- 0.0417 E --- 0.0417 D
                          --- 0.0833 D --- 0.0417 C --- 0.0417 E
                                       --- 0.0417 E --- 0.0417 C
                          --- 0.0833 E --- 0.0417 C --- 0.0417 D
                                       --- 0.0417 D --- 0.0417 C
             --- 0.2500 E --- 0.2500 A --- 0.1250 C --- 0.1250 D
                                       --- 0.1250 D --- 0.1250 C

Eerste trekking: bal C, D en E worden geblokkeerd, alleen A en B kunnen getrokken worden.
Als bal B in de eerste trekking getrokken wordt, vervallen alle blokkades van B (de overige blokkades blijven bestaan, in dit geval blokkeert alleen A nog ballen C en D), dus in de tweede trekking kunnen A en E getrokken worden.


Dit geeft opgeteld voor ballen A t/m E de kans dat ze in trekking 1 t/m 5 getrokken worden:

Code: Selecteer alles

       1       2       3       4       5
A:  0.5000  0.2500  0.2500  0.0000  0.0000
B:  0.5000  0.5000  0.0000  0.0000  0.0000
C:  0.0000  0.0000  0.2500  0.3750  0.3750
D:  0.0000  0.0000  0.2500  0.3750  0.3750
E:  0.0000  0.2500  0.2500  0.2500  0.2500

Is dit wat je zoekt?

[Hans Kuiper]

(Ik vergat in het voorgaande nog op te schrijven dat elk balletje een offerte voorstelt bij een aanbesteding)
Ja, RedCat, dit is exact het probleem wat ik bedoel. En zelf op een moeilijke (dwz Excel==>papier==>Excel) manier kon oplossen. Ik deed de kansenboom op papier.
Je geeft de outputtabel voor één prijsvolgorde. Maar er zijn nog 119 andere mogelijke prijsvolgordes.
Ik zoek een papierloze oplossing, liefst in Excel, voor alle 120 prijspermutaties.

[Marko]

Het kan wel in Excel maar het is wel een beetje omslachtig, maar met geschikte LOOKUP's, COUNTIF en SUMIF functies kun je tellen hoe vaak een bepaalde bieder in een geldige permutatie voorkomt in een bepaalde ronde. En aan de hand daarvan kun je de kans op trekking in die ronde berekenen.

Bijgaand een file voor 3 biedingen. Het concept is uit te breiden naar 5 biedingen maar ik denk dat het beter is om eerst te kijken of dit de bedoeling is, of de aanpak niet handiger kan en of hij uberhaupt correct is.

[RedCat]

Ik ben geen Excel-specialist, maar heb de berekeningen gemaakt in programmeertaal C.
Mocht het je alleen gaan om de eindresultaten zijn hier eerst voor elk van de 120 permutaties de 5x5 kans tabellen, met:
- op de rijen bal A t/m E
- op de kolommen de trekkingsnummers 1 t/m 5
- in de tabel de kansen in 8 decimalen achter de komma,
allemaal TAB-gescheiden, dus dit zou je zo in Excel moeten kunnen invoeren.

ballenbak.txt

(34.24 KiB) 58 keer gedownload

Hieronder nog de volledige uitwerkingen met alle kansbomen zoals in mijn eerdere post.
Je kan hiermee zelf nog even checken of e.e.a. overeenkomt met jouw bedoelingen en berekeningen.

ballenbomen.txt

(183.81 KiB) 60 keer gedownload

Volstaat dit voor je?

[RedCat]

Code: Selecteer alles

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

//---------------------------------------------------------------------------

#define MAXBALL 25

int balprijs[MAXBALL]; // prijs van elke bal
int nbal;              // aantal ballen
int getrokken[MAXBALL]; // 1 <-> bal is (al) getrokken

int dom[MAXBALL][MAXBALL]; 	// i x j dominantietabel: bal i domineert bal j
int nblok[MAXBALL];         // aantal blokkades van elke bal
double prob[MAXBALL][MAXBALL];  // kanstabel


// maak de dominantietabel, afhankelijk van de permutatie (= balprijzen):
void setdom(void)
{
int i,j;
memset(dom,0,sizeof(dom));
memset(nblok,0,sizeof(nblok));
for(i=0;i<nbal;i++){
	for(j=i+1;j<nbal;j++){
		if(balprijs[i]<balprijs[j]){
			dom[i][j]=1;
			++nblok[j];
			}
		}
	}
}

// print de permutatie:
void printpermutatie(void)
{
int i;

printf("\npermutatie ");
printf("[%d",balprijs[0]);
for(i=1;i<nbal;i++)
	printf(", %d",balprijs[i]);
printf("]:\n");
}

// print het resultaat:
void printprob(void)
{
int i,j;

for(j=0;j<nbal;j++)
	printf("%8d",j+1);
printf("\n");

for(i=0;i<nbal;i++){
	printf("%c:",'A'+i);
	for(j=0;j<nbal;j++)
		printf("%8.4lf",prob[i][j]);
	printf("\n");
	}
printf("\n");
}

// is bal i beschikbaar <-> 1 (= true)
int isavail(int i)
{
return(nblok[i]==0 && getrokken[i]==0);
}

// tel aantal beschikbare ballen = r
int countavail(void)
{
int i, r=0;
for(i=0;i<nbal;i++)
	if(isavail(i))
		r++;
return(r);
}

// verwijder een bal uit de bak en update de blokkades
void removebal(int balID)
{
int j;
getrokken[balID]=1;
for(j=balID+1; j<nbal; j++)
	nblok[j]-=dom[balID][j];
}

// leg een bal terug in de bak en update de blokkades
void addbal(int balID)
{
int j;
getrokken[balID]=0;
for(j=balID+1; j<nbal; j++)
	nblok[j]+=dom[balID][j];
}


// trek een bal:
// IN: ntr = volgnummer van de trekking
//     Pin = kans op ingang huidige aftakking
void trekking(int ntr, double Pin)
{
int j, id, av;
double Pcur;

av=countavail();  // tel beschikbare ballen
if(av>0){
	Pcur=Pin/(double)av; // bepaal de kans per bal in deze tak
	for(id=0;id<nbal;id++){
		if(isavail(id)){ // voor alle beschikbare ballen:
			prob[id][ntr]+=Pcur; // update de kans dat deze bal als ntr-de getrokken wordt
			removebal(id);  // verwijder de bal uit de bak
			trekking(ntr+1, Pcur); // trek de volgende bal
			addbal(id);     // stop de verwijderde bal weer terug in de bak
			}
		}
	}
}

void ballenbak(void)
{
int permutatie[] = {9, 12, 10, 7, 11, 5, 8, 2, 6, 3, 4, 1};  // <<<< HARDE CODERING VAN DE INPUT

// init alle variabelen:
memcpy(balprijs,permutatie,sizeof(permutatie));
nbal=sizeof(permutatie)/sizeof(int);
memset(getrokken,0,sizeof(getrokken));
memset(prob,0,sizeof(prob));
setdom();

// voer alle mogelijke trekkingen uit voor de huidige permutatie.
// start met bal nul en kans 1.0:
trekking(0, 1.0);

// output:
printpermutatie();
printprob();
}

int main()
{
ballenbak();
return 0;
}

Hierboven de C-code om aan te sleutelen of te vertalen naar een andere taal.
De functie ballenbak() handelt alles af voor de daarin gedefinieerde permutatie:
[9, 12, 10, 7, 11, 5, 8, 2, 6, 3, 4, 1].
Hier dus een voorbeeld met 12 ballen.
Dat gaat bij mij in 0.39 sec.

Om de code uit te voeren kan je die bijvoorbeeld copy-pasten naar het codeveld van
https://www.onlinegdb.com/online_c_compiler (wel eerst even de voorbeeldcode van die pagina wissen).
De groene knop "> Run" linksboven levert dan de output:

Code: Selecteer alles

permutatie [9, 12, 10, 7, 11, 5, 8, 2, 6, 3, 4, 1]:
       1       2       3       4       5       6       7       8       9      10      11      12
A:  0.2000  0.1900  0.1627  0.1235  0.0963  0.0724  0.0587  0.0482  0.0482  0.0000  0.0000  0.0000
B:  0.0000  0.0333  0.0689  0.0969  0.1078  0.1094  0.1077  0.1052  0.1023  0.1081  0.0803  0.0803
C:  0.0000  0.0333  0.0689  0.0980  0.1119  0.1159  0.1144  0.1088  0.1091  0.1199  0.1199  0.0000
D:  0.2000  0.1733  0.1407  0.1101  0.0955  0.0790  0.0615  0.0521  0.0439  0.0439  0.0000  0.0000
E:  0.0000  0.0000  0.0000  0.0047  0.0184  0.0417  0.0686  0.0909  0.1090  0.1393  0.2037  0.3236
F:  0.2000  0.1733  0.1452  0.1170  0.0957  0.0793  0.0619  0.0515  0.0380  0.0380  0.0000  0.0000
G:  0.0000  0.0000  0.0250  0.0553  0.0679  0.0880  0.1032  0.1149  0.1143  0.1302  0.1506  0.1506
H:  0.2000  0.1833  0.1550  0.1211  0.1034  0.0778  0.0607  0.0494  0.0494  0.0000  0.0000  0.0000
I:  0.0000  0.0000  0.0180  0.0446  0.0697  0.0936  0.1096  0.1202  0.1308  0.1472  0.1332  0.1332
J:  0.0000  0.0400  0.0752  0.0981  0.1039  0.1154  0.1160  0.1103  0.1038  0.1187  0.1187  0.0000
K:  0.0000  0.0000  0.0080  0.0238  0.0433  0.0575  0.0796  0.1003  0.1127  0.1229  0.1666  0.2852
L:  0.2000  0.1733  0.1324  0.1069  0.0862  0.0700  0.0582  0.0483  0.0384  0.0319  0.0271  0.0271

De slechts mogelijke permutatie met 12 ballen = [12,11,10,9,8,7,6,5,4,3,2,1] duurt bij mij bijna 2 minuten.
We lopen hier met deze code dus ongeveer tegen de grens aan van wat in de praktijk uitvoerbaar is.
Ik heb nog geen efficienter algoritme kunnen vinden, wellicht iemand anders...

[OOOVincentOOO]

Misschien een ideetje.

Maar kan men misschien werken met generating functies? Bijvoorbeeld door het fitten van een polynoom? Dan kan men analytische/functie analyse en bewerkingen doen.

Polynoom fitten kost een fractie van seconde. Maar dan kan je wel afgeleide/integreren etc.

Voorbeeld trekking kwaliteit:

Polynoom fitten in excel (in andere code als python wellicht netter):
\(\small =LINEST(known~ys, known~xs \text{^\{ 1, 2, 3, 4 \}})\)

Polynomic Fit.xlsx

(11.34 KiB) 74 keer gedownload

Ik begrijp het vraagstuk helaas niet helemaal om daadwerkelijk input te geven.

[RedCat]

wtfbb.png (7.71 KiB) 2269 keer bekeken

Het vraagstuk in het kort:
In een winkel staan 5 varianten van een product met verschil in:
- kwaliteit: kwaliteit A > B > C > D > E
- prijs: 1 t/m 5 euro, via een gegeven permutatie gekoppeld aan de producten
In het plaatje een voorbeeld waarbij A 3 euro kost, B 1, C 5, D 4 en E 2 euro.

De eerste klant in die winkel zal NIET kiezen voor product:
- C: deze is duurder dan zowel A als B, terwijl de kwaliteit minder is
- D: deze is duurder dan zowel A als B, terwijl de kwaliteit minder is
- E: deze is duurder dan B, terwijl de kwaliteit minder is
De eerste klant zal dus kiezen voor A of B.
Met andere woorden: aanwezigheid van A blokkeert dat C en D gekozen worden, B blokkeert de keuze van C, D en E

Voor de kansen P(X=eerste) dat product X als eerste gekozen wordt hebben we dan:
P(A=eerste) = P(B=eerste) = 0.5 (de kansen voor alle verkiesbare producten worden steeds gelijk verondersteld)
P(C=eerste) = P(D=eerste) = P(E=eerste) = 0
Dit zijn tevens de getallen van de eerste kolom van het eindresultaat.

En zo verder voor de klanten die daarna komen en de rest van de kansboom vormen (in het plaatje hierboven alleen de vertakkingen voor de eerste en de tweede klant, de volledige boom staat in een eerdere post).

[Hans Kuiper]

Dank RedCat voor het delen van je C-programma en het geven van alle oplossingen voor elke beginsituatie. Ik ga je uitkomsten inlezen in een array (120,5,5) en die in een macro gebruiken in de Excelbewerking.
Dank Marko voor je poging het rechtstreeks in Excel op te lossen. Er zit nog een bug in je 3-ballen-oplossing want de som van de kansen, zowel horizontaal als verticaal, is niet altijd gelijk aan 1. Dus een opschaling naar 5 ballen is nu nog geen goed idee.
Dank OOOVincentOOO voor je bijdrage die ik wel begrijp maar niet als een oplossing herken.

[Marko]

Dank RedCat voor het delen van je C-programma en het geven van alle oplossingen voor elke beginsituatie. Ik ga je uitkomsten inlezen in een array (120,5,5) en die in een macro gebruiken in de Excelbewerking.
Dank Marko voor je poging het rechtstreeks in Excel op te lossen. Er zit nog een bug in je 3-ballen-oplossing want de som van de kansen, zowel horizontaal als verticaal, is niet altijd gelijk aan 1. Dus een opschaling naar 5 ballen is nu nog geen goed idee.
Dank OOOVincentOOO voor je bijdrage die ik wel begrijp maar niet als een oplossing herken.

Wat bererekend wordt is de kans voor elke bieder op een bepaalde eindpositie. Die kansen moeten optellen tot 1. En dat doen ze ook, voor elke bieder in elke permutatie. Dat heb ik net nog gecheckt. Per ronde tellen deze kansen inderdaad niet op tot 1 maar dat is inherent aan de definitie.

[Hans Kuiper]

@ Marko
In het voorbeeld (A3,B1,C2) dat jij uitwerkte in Excel geldt:
A-B-C heeft een kans van 0.5
B-A-C heeft een kans van 0.25
B-C-A heeft een kans van 0.25
Dan heeft C 25% kans op een 2e plaats en 75% kans op een 3e plaats.
Jouw Excel berekening kwam echter uit op 33.33% resp. 66.67%
Er zijn evenveel 1e plaatsen als 2e en 3e plaatsen dus moet hun kansensom gelijk zijn aan 1.

[Marko]

@ Marko
In het voorbeeld (A3,B1,C2) dat jij uitwerkte in Excel geldt:
A-B-C heeft een kans van 0.5
B-A-C heeft een kans van 0.25
B-C-A heeft een kans van 0.25
Dan heeft C 25% kans op een 2e plaats en 75% kans op een 3e plaats.
Jouw Excel berekening kwam echter uit op 33.33% resp. 66.67%
Er zijn evenveel 1e plaatsen als 2e en 3e plaatsen dus moet hun kansensom gelijk zijn aan 1.

Je hebt gelijk. Ik zal de Excelsheet aanpassen en meteen kijken of ik die ook naar 5 (of een willekeurig aantal) partijen kan uitbreiden.