Spernerjeva lema in poštene delitve

DAKSKOBLER, LARISA (author), Mramor Kosta, Nežka (mentor)

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.

• Language: Slovenian
• Keywords: poštene delitve, Spernerjeva lema, rezanje torte, dodeljevanje sob – delitev najemnine
• Work type: Undergraduate thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2016
• PID: 20.500.12556/RUL-81063
• Publication date in RUL: 25.03.2016

Secondary language

• Language: English
• Title: Sperner's lemma and fair division

Abstract

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.

• Keywords: fair division, Sperner's Lemma, cake-cutting, room assignment – rent division