20.500.12556/RUL-81063 Spernerjeva lema in poštene delitve Sperner's lemma and fair division Problem poštenih delitev je aktualno raziskovalno področje v matematiki, ekonomiji, računalništvu, itd. Obstaja več vrst problemov, ki so pogosto poimenovani po vsakdanjih situacijah: pošteno razdeljevanje virov, rezanje torte, poštena delitev opravil, dodeljevanje sobe – delitev najemnine,… Čeprav že obstaja veliko natančnih kot tudi aproksimativnih metod za iskanje rešitev, se področje še vedno razvija in išče čim boljše rešitve za vsakdanje težave. Cilj diplomskega dela je bil poiskati, na strnjen način predstaviti in primerjati metode za reševanje problemov poštenih delitev, ki temeljijo na Spernerjevi lemi. Predstavljeni so naslednji aproksimativni postopki: Simmonsova metoda za reševanje problema rezanja torte, Sujev postopek za reševanje problema dodeljevanja sob – delitve najemnine in Scarfov algoritem za izračun ekonomskega ravnovesja. Izdelana je aplikacija z grafičnim uporabniškim vmesnikom, ki omogoča testiranje delovanja opisanih postopkov. Fair division is an active research area in Mathematics, Economics, Computer Science, etc. There are many different kinds of fair division problems. These are often named after everyday situations: fair resource allocation, fair cake-cutting, fair chore division, room assignment – rent division, and more. Although many exact and approximative methods for finding fair solutions already exist, the area of fair division still expands and tries to find better solutions for everyday problems. The objective of the thesis was to find, present and compare methods based on Sperner's Lemma, that can be used for solving different fair division problems. The thesis presents next approximative methods: Simmons' approach to cake-cutting, Su's approach to room assignment – rent division and Scarf's method for computation of equilibrium prices. An application with graphical user interface was build, which allows us to try out described methods in different test scenarios. poštene delitve Spernerjeva lema rezanje torte dodeljevanje sob – delitev najemnine fair division Sperner's Lemma cake-cutting room assignment – rent division true false false Slovenski jezik Angleški jezik Diplomsko delo 2016-03-25 16:45:03 2016-03-25 16:45:04 2022-08-01 21:13:19 0000-00-00 00:00:00 2016 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 16942 Dakskobler_Larisa_-_Spernerjeva_lema_in_postene_delitve.pdf Dakskobler_Larisa_-_Spernerjeva_lema_in_postene_delitve.pdf 1 16D8DDA7419B5EEFAB558B71F6796704 26212dc8d6853c3ab7b61ecb8df145673d66c2779c8e851f34d530d4ea0a1b03 6b868da4-a1ad-11eb-a523-00155dcfd717 20.500.12556/rul/01e516ca-faed-492f-8d72-7b2202816c84 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=81282 Fakulteta za računalništvo in informatiko 0 0 0