Topologija iliti matematika pomoću traka, konopa, kravata ...

Topologija iliti matematika pomoću traka, konopa, kravata ...

Kako podijeliti plijen? Franka Miriam Brckler PMF Matematiki odjel, Zagreb 06. 02. 2007. Priica... Crni Jack istresao je vreu na stol. Barica, Katica i Kumpi gotovo su pali u nesvijest vidjevi kako se stol pretrpava novanicama, kovanicama, draguljima i zlatnim polugama. Zavrio je laki dio posla, ostao je tei: podjela plijena. Znajui se dovoljno dobro meusobno, nitko ne vjeruje nikome. Lako je podijeliti novac na 4 jednaka dijela. S polugama je ve malo tee ako nisu sve jednake i njihov broj djeljiv s 4. A dragulji? Au! Svatko ima svoj stav koliko to vrijedi. I

to slijedi? Svaa. Ili: matematika. O problemu... Ukoliko ne ele da svaa potraje predugo, moraju nai strategiju kojom e plijen podijeliti na 4 dijela tako da svi budu zadovoljni tj. tako 1. da je svatko na kraju raspodjele uvjeren da je dobio barem koliko je pravedno za njega i 2. da nitko na kraju ne misli da je netko drugi dobio vie od njega. Gdje je problem? Nemaju svi isti stav o vrijednostima stvari koje se dijele! Pravedno i bez zavisti Uoimo: nije isto ako svatko vjeruje da je dobio bar koliko ga ide i ako svatko vjeruje da nitko nije dobio vie!

Ako uspijemo napraviti podjelu bez zavisti, ona je sigurno pravedna, ali mogue su pravedne podjele u kojima ima zavisti.... Primjer 3 osobe (A, B, C) ele raspodijeliti meu sobom prsten, ogrlicu i narukvicu (recimo da nijedno nije mogue rastaviti na manje dijelove). Svatko je relativno vrednovao ta tri predmeta: ogrlic narukvi prste a ca n A 50 B 50

C 20 40 30 30 10 20 50 Ako A uzme narukvicu, B ogrlicu i C prsten, podjela jest pravedna, ali je A zavidan na B! to ako dvoje dijeli plijen? Lako! Prvi raspodijeli plijen na pola prema svojim predodbama, ali prvi uzima drugi. Pravedno i bez zavisti!

ogrlic narukvi prste a ca n A 50 B 20 40 30 10 50 A stavi na jednu stranu ogrlicu, a na drugu narukvicu i prsten. B odabere narukvicu i prsten, A-u ostane ogrlica. to se desi pokuamo li taktiku kopirati za troje?

Utroje (uetvero, upetero...) je veselije Hugo Steinhaus, 1944., Lwow, Poljska... da ne misli na rat, pokuao je smisliti strategiju za troje. Jedan, sluajno odabran, dijeli. A B ili B: NE! B: NE! uzimaj u redom

C C, B, A ili uzimaju redom B, C, A B, C: C: NE NE B: NE A uzima komad koji nee ni B ni C, B onaj koji nee C, a C onaj koji nee B Steinhausov postupak ne garantira da nema zavisti, ali daje pravednu podjelu. Za vie

sudionika poopen je 1967. (Harold Kuhn). Ovaj postupak poznat je kao lone divider method. Primjer A B 1/3 1/3 1/3 1/2 1/3 C 1/6

A je dobio 1/3 i nije zavidan B je dobio 1/3 i zavidan je C C je dobio 1/2 i nije zavidan 1/2 1/3 1/6 C A B Matematiki model n sudionika A1,A2,...An koji trebaju raspodijeliti skup dobara S tako da svaki dobije pravedan dio pravedan dio za Ai je dio dobara iz S koje Ai smatra (u vlastitom sustavu vrijednosti) da

vrijede bar 1/n ukupne vrijednosti od S rjeenje je protokol tj. niz postupaka koje sudionici trebaju provesti (oekuje se da uvijek bude konaan); ne trai se najbolje rj. protokol je pravedan ako njime svi i u svakom sluaju (za svaki n i S) dobiju pravedan dio pretpostavke: svi su u stanju za sebe vrednovati svaki dio od S svi pristaju na potivanje pravila protokola svi su racionalni i neskloni riziku (tj. ele si osigurati maxmin-dio i njega nee riskirati ak ni ako rizik znai mogunost veeg udjela)

mogue poeljne dodatne osobine protokola: 1. nema zavisti 2. Pareto-optimalnost iliti efikasnost: efikasnost ne postoji raspodjela koja bi za nekog bila bolja, bez da je slabija za nekog drugog 3. jednakost: jednakost svi vjeruju da su dobili tono 1/ n vrijednosti S (ako ih je bilo n) ovo recimo ne zadovoljava protokol ja reem, ti bira Za 3 ili vie osoba ne moe se nai protokol koji je uvijek (za sve n i sve S) i 2. i 4.! Vrste protokola neprekidni za sluaj kad je S mogue raspodijeliti na beskonano mnogo naina i proizvoljno male dijelove

diskretni za sluaj kad se S sastoji od nedjeljivih objekata (ili bar ne lako djeljivih) mjeoviti Neprekidni protokoli Lone-chooser protokol 1964. A. M. Fink 1.Bira se jedan chooser C, ostali su divider-i 2.Svi osim C dijele kola na n-1 pravedan dio. 3.Svaki dijeli svoj dio na n jednakovrijednih dijelova. 4.C bira po jedan dio od svakog. Rekurzivni algoritam!!! Slijedi primjer za troje... Chooser: C, Divider: A,B

A: 1/2 A: 1/6 A: 1/6 B: 1/6 A: 1/6 B: 1/2 B: 1/6 B: 1/6 A: 1/6 A: 1/6 B: 1/6 C: C: 1/6

B: 1/6 A C B C B Banach-Knasterov protokol (lastdiminisher) Steinhaus-ovi prijatelji S. Banach i B. Knaster nali su poopenje Steinhausovog protokola na vie od 3 sudionika raspodjele. Sudionici trebaju raditi idue: 1.Definira se redoslijed meu sudionicima. 2.Prvi odvoji jedan poten dio C (dakle, po njegovom mjerilu, vrijedan 1/n). Sve ostalo je R.

3.Drugi moe, ako C smatra prevelikim, od C oduzeti viak, tako da C ostane poten komad; viak stavlja u R. 3. Trei ima isto pravo kao i drugi itd. svi do zadnjeg od C, ako to smatraju potrebnim, oduzimaju viak i stavljaju u R. 4. Ukoliko nitko nije smanjio C, onda ga dobiva prvi sudionik; inae se dio dodjeljuje zadnjem koji ga je smanjio. Onaj koji je sad dobio C ispada iz nastavka podjele. 5. Sad se postupak ponavlja s R i sudionikom manje sve dok ne ostanu samo 2 sudionika (koji dijele standardnom strategijom). Naalost: nije bez zavisti! Petero brodolomaca na pustom otoku odluilo je podijeliti otok... Neka su to 1,2,3,4,5.

1. R R R C C C 4 smatra da C vrijedi >1/5, 5 nakon toga da je <1/5 4 dobiva C 2 smatra da C

vrijedi <1/5, 3 smatra da vrijedi >1/5 1 smatra da C vrijedi 1/5 2. (vie ne igra 4) C R 4 1 smatra da C vrijedi 1/4 5

C R 4 2 i 3 se slau, 5 smatra da C 4 5 dobiva C 3. (vie ne igraju 4 i 5) C 5 4 C

R 1 smatra da C vrijedi 1/3 4 2 smatra da C vrijedi >1/3 4. (ostali su 1 i 3) 1 dijeli, 3 bira 2 5 4 2

5 R 5 4 3 smatra da C vrijedi <1/3 2 dobiva C 5. gotovo! 2 1 4 5 3

Selfridge-Conway-ev protokol za troje Poetkom 60ih godina 20. stoljea John Selfridge i John Horton su nezavisno jedan od drugog nali pravedan protokol za troje koji garantira da nema zavisti. Slijedi algoritam. 1. A dijeli na 3 pravedna dijela (x,y,z) 2. B (u sebi) reda ta tri dijela po vrijednosti (recimo x,y,z) i od najvrednijeg (x) odree onoliko koliko treba da ostane jednako vrijedan komad (w) kao to mu je drugi po vrijednosti (y); odrezani dio se stavlja na stranu. 3. Sad u redoslijedu C, B, A sudionici uzimaju po jedan dio od x,y,z. Ako C ne uzme x, mora ga uzeti B.

4. Ukoliko je u 2. koraku bilo oduzimanja, potrebno je raspodijeliti i ostatak w (inae smo gotovi). Korak 1. na taj ostatak primjenjuje B ili C (onaj koji nije uzeo komad w). Od toga prvo bira onaj koji nije dijelio w, pa A pa tek onda onaj koji je dijelio w. A x B y z w

x-w y z B C, B, A x-w A C B A C B,A,C C C

A B B A C Pokretni no Za dvoje: No ide neprekidno slijeva udesno. Kad jedan vikne rei on dobiva lijevi dio, a drugi ostatak. Za troje: Stromquistov postupak (1980) Uz troje sudionika potreban je i sudac koji pomie no polako slijeva udesno. Svaki od sudionika takoer ima no (svi noevi su paralelni) i pomie ga tako da u svakom trenutku smatra da njegov no raspolavlja dio kolaa desno od sueva noa. Svaki sudionik smije viknuti rei u bilo kojem trenutku.

Tada se kola ree na 3 dijela suevim noem i srednjim od noeva sudionika. Lijevi dio dobiva onaj koji je viknuo rei, srednji onaj od druge dvojice iji no je blii suevom. Diskretni protokoli Tajna aukcija (SteinhausKnaster) Zgodna kad sudionika ima priblino jednako koliko i dobara za raspodijeliti. Uvjet je da je svaki u stanju i voljan mijenjati bilo koje dobro za novac. 1. Svaki dodijeli subjektivnu vrijednost svakoj stvari (koliko bi novaca bio spreman dati za nju) i stavlja te ponude u zatvorenu kovertu. Prosjena cijena koju nudi za stvari jednaka je njegovoj procjeni pravednog dijela. Bitno je da nijedan ne zna procjene drugih. Koverte se istovremeno otvaraju i svaka stvar ide onom koji je najvie ponudio. 2. Svaki koji je dobio vie od svog pravednog dijela

plaa viak u zajedniki fond. Svakom koji je dobio manje, isplauje se ta razlika. Ukoliko ostane viak novca, on se raspodijeli. nasljednika treba podijeliti nasljedstvo ... Tomisla v Stvar Ana Boris Marko Petra Kua 20000

0 21500 0 19500 0 17500 205000 0 Vikendic 60000 a 49000 62500

59500 55000 BMW 29000 24500 25000 27500 27500 Saab

25000 19000 22500 24500 19500 Jahta 12000 0 12500 0 11900

0 12900 132500 0 Mondria n 95000 89000 50000 75000 65000

15000 13500 17900 99000 149000 ViakEscher novca: 91700 0 tj. svaki 0 dobije jo i 18340. 0 Metoda markera (W. F. Lucas) Primjenjiva je ako se dijeli puno stvari sline vrijednosti, npr. bomboni.Te se stvari poredaju u niz. Svaki igra stavlja n-1 markera kojima raspodjeljuje niz na segmente koje smatra jednako vrijednima, tj. spreman je uzeti bilo koji dio izmeu dva svoja markera. Prvo pogledamo iji je prvi prvi marker toj osobi ide prvi dio niza ispred markera, njegovi markeri se miu

Sad prvi od drugih markera... Moe se desiti da neki dijelovi ostanu neraspodijeljeni (raspodijele se nekim sluajnim nainom). 4 osobe dijele 20 pia i jela ... Ogranienja i pitanja svijet nije idealno matematiki, a ponekad je ipak jednostavnije bez algoritma... alternative: odoka, grubom silom, metoda pokuaja i pogreki, varanje, moljenje veeg dijela, ... otvoren problem: 1944; donekle zatvoren: 1995 (prvi protokol bez zavisti za proizvoljan n) postoji li rjeenje? postoji li protokol? ako ne, postoji li aproksimativna procedura? gornja mea broja koraka (u opem diskretnom sluaju neodreena!)? to se moe postii ograniavanjem broja rezova? protokoli s minimalnim brojem koraka (n-1)? Zasad

samo dva za troje i jedan za etvero. samo povezani dijelovi? ako interesi nisu dijametralno suprotni protokoli esto dovode do boljeg od maxmin rjeenja za sve! S druge strane, to su razliitiji interesi, lake je podijeliti. emu sve ovo? - svakodnevni problemi raspodjele - raspodjela pri brakorazvodnim parnicama, razdvajanju firmi i nasljeivanju - odreivanje granica na moru ili izbornih jedinica, podjela zemljita... - bliske matematike discipline: teorija grafova, kombinatorna topologija, raunarstvo, teorija mjere, teorija igara Odreivanje granica izbornih

jedinica Dvostranaki sustav... Stranka na vlasti moe odrediti granice kako hoe (uvjet je podjednak broj graana u izbornim jedinicama i da je izborna jedinica povezana uz jo neke tradicionalne uvjete). Gerrymandering je pojam koji oznaava odabir granica izbornih jedinica kako bi se politiki profitiralo (Elbridge Gerry, 1812. je kreirao jedinicu oblika gutera). Ukupno: Roza : crni = 13:12 Dobiveni zastupnici Gore: Roza : crni = 4:1 Desno:

Roza : crni = 1:4 Protokol za 2 stranke i 1 neutralca stranke: roza i crna; treba podijeliti teritorij na n izbornih jedinica s po d stanovnika neutralac crta n-1 podjelu teritorija na dva dijela (zvat emo ih Xi i Yi) tako da svaki idui X sadri prethodni i da je redom odnos stanovnika u podjeli d:(n-1)d, 2d:(n-2)d, ... za svaku takvu podjelu i roza i crna stranka biraju: a) roza dijeli Xi na i dijelova, a crni Yi na n-i dijelova ili b) roza dijeli Yi na n-i dijelova, a crni Xi na i dijelova (nitko nee htjeti dijeliti X1 i Yn-1 jer su oni veliine jedne izborne jedinice) ako su obje stranke za neki i izabrale istu od gornje dvije opcije, neka tako i uine; inae: nai in-2 za koji je roza birala b), ali u iduem koraku a), pa sluajnim izborom napravi podjelu po jednoj od dvije opcije za i ili i+1

i=1 Roza: opcija b) Crni: opcija a) i=2 Roza: opcija b) Crni: opcija a) i=3 roza: opcija a) crni: opcija b) i=4 roza: opcija a) crni: opcija b) roza mijenja opciju izmeu koraka i=2 i i+1=3 biramo jednu od opcija a) ili b) za i=2 ili 3,

recimo i=3 i opcija b) tj. roza dijeli desni, a crni lijevi dio stvar donekle ovisi o podjeli na X-eve i Y-e, no moe se raditi vie raznih takvih podjela t.d. obje stranke rangiraju dobivene rezultate i onda se odabere ona podjela ije najslabije mjesto je Literatura S. J. Brams, M. A. Jones & C. Klamler: Better Ways to Cut a Cake, Notices of the AMS 11(52) 2006 1314-1321 Z. Landau, O. Reid, I. Yershov: A Fair Division Solution to the Problem of Redistricting, 2006. J. Robertson & W. Webb: Cake-Cutting Algorithms, Amer. Math. Monthly 107 (2000)185-188 P. Tannenbaum: Excursions in Modern Mathematics, Pearson Education, 2004. Wikipedia: Fair Division http://en.wikipedia.org/wiki/Fair_division Su, Francis E., et al. "Envy-free Cake Division. Mudd Math Fun Facts

http://www.math.hmc.edu/funfacts Fair Division Problems and Fair Division Schemes: http://www.colorado.edu/education/DMP/fair_division.html A. Bogomolny: Cut the Knot http://www.cut-the-knot.org/Curriculum/index.shtml (toke 301, 302, 303) Extra Cake-Cutting Practice: http://www.merrimack.edu/~krunge/applets/CakePractice.htm Fair Division Calculator: http://3quarksdaily.blogs.com/3quarksdaily/ 2005/04/3qd_monday_musi.html

Recently Viewed Presentations

  • AMI Update - Smart Energy International

    AMI Update - Smart Energy International

    California's Statewide Pricing Pilot Larsh Johnson - President and Chief Technical Officer, eMeter
  • Winning Telephone Techniques Module 4 Module 4 41

    Winning Telephone Techniques Module 4 Module 4 41

    Phone Contacts Communicating effectively on the telephone is a unique skill Basic Phone Skills Telephone etiquette can make or break the caller's perception of your service Inflection 86% of the message is from your tone of voice 14% is grasped...
  • Theoretical Foundations

    Theoretical Foundations

    Educational Technology Educational technology is any technology that is used to support teaching and learning ISTE's NETS-T and NETS-S standards articulate what teachers and students should know Educational Technology and Instruction Technology are the tools to help create an effective...
  • Reflections on issues of power in packaged software selection

    Reflections on issues of power in packaged software selection

    IT Consultants and Packaged Software Selection Debra Howcroft CRESC and MBS University of Manchester, UK [email protected]
  • Source Removal Quote Form/ Source Removal Work Orders

    Source Removal Quote Form/ Source Removal Work Orders

    Source Removal Report is the final deliverable for all work orders and retainage (non-PPA) will not be paid on any work order until the Source Removal Report has been received and approved. Utilize the RAC and CO worksheets when preparing...
  • OpenMP - PUC-Rio | Home

    OpenMP - PUC-Rio | Home

    Title: OpenMP Author: Noemi Rodriguez Last modified by: Noemi Rodriguez Created Date: 9/28/2009 1:46:41 PM Document presentation format: On-screen Show (4:3)
  • Welcome to class of International Marketing Strategy by

    Welcome to class of International Marketing Strategy by

    International Marketing Strategy Standardization versus Customization Ethnocentric Strategy Polycentric Strategy Regiocentric Strategy Geocentric Strategy Expansion Process and Strategic Decisions Expand or not International market evaluation Mode of entry Overall strategy Marketing mix Standardization vs. Customization Ethnocentric Strategy ...
  • PresPrint Template

    PresPrint Template

    Building Secure Systems Plattform Security - Isolation, Privileges and Server Security Walter Kriha, Computer Science and Media Faculty