20.500.12556/RUL-172989 Oblikovanje aproksimacijskih mehanizmov brez denarja delo diplomskega seminarja Approximate mechanism design without money V diplomskem delu je obravnavan problem oblikovanja mehanizmov za postavitev javnih ustanov v mesto. Osredotočimo se na scenarije, kjer so lokacije posameznikov znane le njim samim, cilj pa je minimizirati skupno ali največjo razdaljo prebivalcev do izbrane lokacije. Klasični pristopi, ki temeljijo na denarnih plačilih, v teh primerih niso primerni, zato iščemo mehanizme, ki kljub temu preprečujejo, da bi prebivalci poročali napačno lokacijo z namenom profitirati, torej biti bližje ustanovi. Ker taki optimalni mehanizmi pogosto ne obstajajo, se osredotočimo na iskanje aproksimacijskih mehanizmov, ki zagotavljajo čim boljše razmerje glede na optimalno rešitev. Najprej obravnavamo problem, ko je oblika mesta realna os, lociramo pa zgolj eno ustanovo. Problem nato razširimo še na lociranje dveh ustanov in na koncu še na primer, ko je oblika mesta graf. In this thesis, we study the problem of designing mechanisms for placing public facilities in a city. We focus on scenarios where the locations of individuals are private information, and the objective is to minimize either the total or the maximum distance of all individuals to the chosen facility location. Traditional approaches that rely on monetary transfers are often inappropriate in such settings, so we seek mechanisms that prevent individuals from misreporting their true location in order to gain an advantage-i.e., to be closer to the facility. Since optimal truthful mechanisms often do not exist, we turn our attention to approximation mechanisms that guarantee a solution not too far from the optimal in terms of social cost. We begin by considering the case where the city is modeled as the real line and a single facility is to be located. We then extend the problem to the case of two facilities and, finally, to the case where the city is represented as a graph. oblikovanje mehanizmov aproksimacija problem dodeljevanja lokacij mechanism design approximation facility location problem true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2025-09-12 08:15:28 2025-09-12 08:15:29 2025-10-29 03:53:12 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.8 153210 248760323 19093.pdf 19093.pdf 1 3B8831123621571932D495C23240FA3F 28d4b6e27dc7a5cb0b3ef5e964d9782ca3030f7cc05821568409e3208e92ffe5 b75ef3df-8f9f-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=217141 Fakulteta za matematiko in fiziko 0 0 0