To australske dataloger har fundet en begrænset algoritme, som deler kager og andet, man vil dele, misundelsesfrit. Det skriver Erika Klarreich om i Quanta Magazine.  Jeg har tidligere skrevet om den type problemer på Numb3rsbloggen, så jeg tillader mig at kopiere mig selv. Opdelinger med forskellige mål for, hvad en ideel deling er, optræder eksempelvis i økonomi – der optræder “nyttefunktioner”, som er mål for, hvor meget mere tilfreds, bestemte personer bliver, hvis de køber dette eller hint. Her deler vi kager, men I må gerne tænke på andre mere økonomiske ting – løn, ferie,…:

Kageudskæringsalgoritmer:

Det handler groft set om at dele noget – en kage eller noget andet – i et antal stykker, så alle bliver tilfredse. Et mere avanceret og kompliceret eksempel er opdeling af landområder efter en krig.

Et eksempel på en kageudskæringsalgoritme er “du deler og din søster vælger først” algoritmen, som forældre i hele verden nok kender. Ideen er, at hvis jeg deler, må jeg mene, begge stykker er lige gode. Og jeg er altså tilfreds, uanset hvilket stykke hun vælger. Omvendt er hun tilfreds, for hun får det stykke, hun selv mener ser bedst ud.

Man forestiller sig, en kage skal deles mellem personer, som har forskellige præferencer; Charlie viste en lagkage med vanille og chokolade og med glasur. Nogen sætter meget pris på glasur, andre mindre, nogen er vilde med vanille, andre med chokolade.

Vi forestiller os altså, at et stykke af kagen kan have forskellig værdi for forskellige personer. Og hele kagen kan være mere værd for en person end for en anden. Lad os sige, der er n personer, der skal dele kagen.

Man kan stille mange forskellige krav til en deling – hvad betyder det, at den er rimelig. Det kunne være

1) Proportionalt – hver person mener, at værdien af deres eget stykke er mindst 1/n af den samlede værdi. (OBS. Hvis nu jeg bedst kan lide vanilje og min søster chokolade og kagen består af halvt af hver, kan vi begge to få mere end halvdelen af det, vi mener er den samlede værdi. Ved at lade mig få den halvdel, der er vanilje og hun får den anden.)

2) Misundelsesfrit: Hver person mener, hun har fået det bedste af de stykker, kagen er delt i. (Ikke en skarp ulighed – det er nok, at der ikke er et andet, hun hellere vil have.)

3) Pareto optimalt:Vi har en opdeling, hvor enhver anden opdeling, hvor en deltager får mere, vil medføre, at en eller flere får mindre. Begrebet er en slags stabilitet overfor ændringer og optræder ofte i økonomi. Hvis jeg skal overbevise de andre om at lave det om, skal jeg overtale en deltager til at få mindre. (Det er det, der starter krige)

4) Ligeligt: Alles stykker har samme værdi. Så værdien af mit stykke for mig, er det samme som værdien af min søsters stykke for hende. Det kræver, at man kender alle deltagernes værdisætning af kagen.

Lad os begynde med to personer, som har et snit til at dele kagen. Vi vil ikke have en deling, hvor man tillader så mange stykker, at det ender med, at hver får en bunke krummer. Med “du deler, din søster vælger” algoritmen bliver delingen proportional og misundelsesfri men ikke nødvendigvis ligelig og pareto optimal.

Eksempel: Halvdelen af kagen er vanilje, halvdelen chokolade. Jeg er vild med chokolade, min søster med vanilje. jeg skærer og ved ikke, at min søster helst vil have vanilje. Så for en sikkerhedsskyld deler jeg, så begge stykker har halvt chokolade og halvt vanilje. Vi ville begge to have foretrukket delingen hvor jeg fik kun chokolade, og min søster kun vanilje – det er altså ikke pareto optimalt.

Lad os kigge nærmere på betingelserne ligelig og misundelsesfri. Pareto optimal er en lidt pudsig betingelse her, for hvis jeg får det hele, kan min søster ikke forbedre sin situation, uden jeg får mindre, end jeg havde; det er altså Pareto optimalt – og nok er jeg storesøster, men mon ikke FN eller forældre ville gribe ind.

Ligelig opdeling giver kun mening, hvis alle deltagere har samme samlede værdi af kagen, og man antager også, at alle sætter værdien af nok så små stykker højere end 0. Hellere chokolade end slet ingen kage. Lad os sige, den samlede værdi er 1.

En yderligere forsimpling er, at man kun må skære i en på forhånd valgt retning ( Tænk på en langstrakt skærekage, hvor man skærer på tværs – ikke noget med kagemænd, hvor man kan foretrække en af fødderne).

Vi kalder midtpunktet af kagen 1/2 og siger, man kan skære i punkter fra 0 til 1 (kagen er 1 lang). Fra 0 til 1/2 er der chokolade og fra 1/2 til 1 er der vanilje. (Vi antager, at stykker med areal 0, ikke har nogen værd, så det er ligemeget, hvad der er i 1/2.)

Hvis nu A er dobbelt så vild med chokolade som med vanilje, er hans værdisætning 4/3⋅x for et stykke af længde x med chokolade. Den er 2/3⋅ x for et stykke med vanilje. Vi antager, B har det omvendt.

Hvis A skal dele, vil hans strategi være, at det stykke, han ender med, har værdi mindst 1/2. (En minimax strategi – man satser ikke, men sørger for, at få mest muligt ud af det værste, der vil kunne ske.)

Så han deler i punktet p=3/8. Han har kun chokolade på stykket til venstre for p, så det har værdi

3/8 ⋅ 4/3 = 1/2

B vil vælge stykket til højre og få en værdi på 3/4, så det er ikke ligeligt, og A har snydt sig selv.

Havde A delt i midten, ville B stadig vælge stykket til højre, begge ville få værdi 2/3, og det ville være ligeligt og misundelsesfrit.

For n = 3 eller flere, kan man vise, at der findes situationer, hvor man ikke med n-1 snit kan lave en misundelsesfri og ligelig deling. Se f.eks. Better ways to cut a cake S. Brams, M.A. Jones og C. Klamler, Notices of the AMS, Vol 53 no. 11. Husk, hvis du går igang med den, at det handler om strategier og algoritmer: Hvordan ser det ud, hvis A ikke er ærlig om sin værdifunktion; er der en udenforstående involveret (FN eller andre) etc.

I How to cut a cake fairly, Walter Stromquist, American Mathematical Monthly, Vol 87, No.8, Oct. 1980, pp 640-644 (findes på Jstor for dem, der har adgang til det), bevises, at der eksisterer en misundelsesfri opdeling med n-1 snit for n deltagere. Men der er ikke en algoritme til at finde den. Det er et meget smukt argument (jo, det er det altså).
En opdeling i n+1 stykker betragtes som en stribe snit x1,x2,…,xn hvor 0 ≤ x1 ≤ x2 … ≤ xn ≤ 1. Det er de steder i intervallet mellem 0 og 1, hvor der skæres. Det tænker man så på som et punkt (x1,x2,…,xn) i et n-dimensionalt rum.
Las os begrænse os til at dele i tre stykker. Punkterne (x1,x2) vil ligge i en trekant i planen med hjørner (0,0), (0,1) og (1,1). Så hvert punkt svarer til en opdeling.
Hjørnepunkterne svarer til, at der to “stykker” uden noget, og et stykke, der er hele kagen. Kald de tre stykker, der kommer ud af opdelingen for nummer 1, 2 og 3 for stykket mellem 0 og x1, mellem x1 og x2 og mellem x2 og 1. Så er (0,0) der, hvor stykke 3 udgør hele kagen. (0,1) er, hvor stykke 2 er hele kagen og i (1,1) er det stykke 3, der er det hele.
På kanten mellem (0,0) og (0,1) er stykke nummer 1 “tomt”, og tilsvarende på de andre kanter.
I et punkt (x1,x2) vil spiller A måske foretrække stykke nummer 1, spiller B nummer 2 og spiller C måske også nummer 1. Der vil være en del af trekanten, hvori A vil foretrække 1, en anden del, hvor A foretrækker 2, og en tredie, hvor han foretrækker 3. (og nogen grænseområder, hvor han er ligeglad). Og tilsvarende for spillerne B og C. Nu skal man vise, at der findes et punkt, hvor spillerne foretrækker hver sit stykke. Og det kan man – med visse forudsætninger, men sådan er det jo i matematik. Ingrediensen i beviset er Brouwers fikspunktsætning, som har forbavsende mange anvendelser. Den siger:
En kontinuert afbildning fra en kugle til en kugle (tænk her på en klump modellervoks, som man kun må ælte og ikke flå) har et fikspunkt. (Et punkt er kommet tilbage, hvor det var)
Som illustration: Hvis man tager en blok papir, tager det øverste stykke af og krøller det sammen og lægger papirkuglen ovenpå blokken. Så vil der være et punkt, der ligger lige præcis lodret over der, hvor det var, før vi rev papiret af blokken.
Jeg vil ikke gengive, hvordan det bliver brugt i kageudskærings eksistensbeviset, men det står i artiklen.

Bemærk i øvrigt, problemet kan vendes om, så man skal dele noget, man ikke bryder sig om. Opvask og lignende. Det giver tilsvarende udskæringsalgoritmer “med modsat fortegn” i en vis forstand.

 

Hvad er det nye?

De to australiere har lavet en algoritme, som deler misundelsesfrit i endelig mange skridt. Er man kun 2, vil du deler, din søster vælger, være misundelsesfri. Men er man flere om det, bliver det mere vanskeligt, for den, der vælger sidst, kunne jo misunde en af dem, der valgte først. Den nye algoritme gør, for tilfældet med 3 personer, A,B, C følgende:

C deler i tre dele, X,Y,Z og A og B peger på det stykke, de helst vil have. Er det to forskellige stykker, er alt fint og C får det sidste.

Peger A og B på samme stykke, Z, sker følgende: B skærer så meget af dette stykke, at det, der er tilbage, Z’ er lige så meget værd – for hende! – som det, hun næsthelst ville have – lad os sige Y.

Læg det, der er skåret af til side. Lad A vælge. Hvis A ikke vælger Z’, er B tvunget til at tage det stykke. Vi har nu en misundelsesfri deling af kagen, bortset fra det, vi har lagt til side: A er tilfreds, da hun vælger først. B er tilfreds, da de to stykker, var lige meget værd. C er tilfreds, da de tre oprindelige stykker var lige meget værd. Vi har nu fordelt C fik X, B fik Y og A fik Z’ hvis ikke B blev tvunget til at tage Z’

Nu skal det afskårne deles (eller gives til hunden). Hvis A tog det tilrettede stykke, går det som følger:

B deler i tre dele. A vælger først, derefter C og til sidst B. Det er nu alt i alt misundelsesfrit. C har allerede fået X, der er lige så meget værd som Y og Z og derfor også lige så meget værd som Z’+det stykke A har fået i anden omgang. Derfor er C ikke misundelig på  A. Og C vælger før B og er heller ikke misundelig på hende. B delte og er derfor tilfreds. A valgte først og er derfor glad. (Jeg indser nu, at det nok kan skrives smukt ned med uligheder mellem de forskelliges præferencefunktioner, men det kan I selv filosofere over.)

For flere “spillere”, bliver det en meget lang proces, hvor der skal byttes om på, hvem der vælger, tages hensyn til, om en delmængde af spillerne alle foretrækker samme stykke…