Vi studerar problemet med rättvis fördelning av odelbara varor. Vi använder Maxmin share paradigm som infördes av Budish [16] som ett mått på rättvisa. Kurokawa, Procaccia och Wang [36] var de första som undersökte detta grundläggande problem i tillsatsen. De visar att en maximal garanti (1-MMS tilldelning) inte alltid är möjlig även om antalet agenter är begränsat till 3. Även om det finns en tillnärmningslösning (t.ex. En 1/2-MMS tilldelning) är ganska enkelt, förbättra garantin blir subtilare för större konstanter. Kurokawa m.fl. [36] ger bevis för att det finns en fördelning på 2/3 MMS och lämnar frågan öppen för bättre garantier. Vårt huvudsakliga bidrag är ett svar på ovanstående fråga. Vi förbättrar resultatet av Kurokawa et al. till en 3/4 faktor i tillsatsen. Huvudidén för vår fördelningsmetod på 3/4 MMS är att klumpa ihop agenterna. I detta syfte introducerar vi tre begrepp och tekniker, nämligen reducibilitet, matchning av tilldelning, och cykel-avsikt-frihet, och bevisa den approximativa garantin för vår algoritm via icke-triviala tillämpningar av dessa tekniker. Vår analys innebär färgning och dubbelräkning argument som kan vara av oberoende intresse. En stor brist i de aktuella studierna om rättvis fördelning är additionalitetsprincipen på värderingarna. Vi lindrar detta genom att utvidga våra resultat till fall av submodulära, fraktionerat subadditiva och subadditiva inställningar. Mer exakt ger vi konstanta approximativa garantier för submodulära och XOS-agenter, och en logaritmisk approximation för subadditiva agenser. Dessutom kompletterar vi våra resultat genom att tillhandahålla nära övre gränser för varje klass av värderingsfunktioner. Slutligen presenterar vi algoritmer för att hitta sådana tilldelningar för additiva, submodulära och XOS-inställningar i polynom tid. Läsaren hittar en sammanfattning av våra resultat i tabell 1. 1 Antag att vi har en uppsättning m odelbara objekt, och vill fördela dem bland n agenter. Agenter har värderingar för varje uppsättning poster som inte nödvändigtvis är identiska. Hur svårt är det att dela upp objekten mellan agenterna för att se till att alla får en rättvis andel? Rättvisa divisionsproblem har studerats i stor utsträckning under de senaste 60 åren (se t.ex. [3, 5, 13, 16, 21, 36, 42]....................................................................................................... Denna forskningslinje initierades av Steinhaus [42] arbete där författaren introducerade tårtskärarproblemet enligt följande: med en heterogen kaka och en uppsättning agenter med olika värderingsfunktioner är målet att hitta en rättvis fördelning av kakan till agenterna. För att studera detta problem har flera begrepp om rättvisa föreslagits, varav de mest kända är proportionalitet och avundsfrihet, som infördes av Steinhaus [42] och Foley [28]. En division kallas proportionell, om det totala värdet av de tilldelade bitarna till varje agens är minst 1/n fraktion av hans totala värde för hela kakan, där n är antalet agenser. I en avundsfri division vill ingen agent byta ut sin andel mot en annan agent, d.v.s. varje agents värdering av sin aktie är minst lika mycket som hans värdering av de andra agenternas aktier. Det är uppenbart att proportionaliteten är underförstådd med avundsfrihet. Dubins och Spanier [21] föreslår ett enkelt flytta knivförfarande som kan garantera en proportionell uppdelning av kakan. För avundsfrihet designar Selfridge och Conway en algoritm som garanterar avundsfrihet när antalet agenter är begränsat till 3. Senare utvidgar Brams och Taylor denna garanti till ett godtyckligt antal agenser i tillsatsen [14]. Men deras metod för fördelning av kakan gör ett obundet antal nedskärningar. Nyligen, avgränsade protokoll föreslås för avundsfri tilldelning av kaka och chore [6, 19]. Problemet blir ännu mer subtilt när vi antar att objekten är odelbara. Det är inte svårt att visa att varken proportionalitet eller avundsfrihet kan garanteras för odelbara föremål; till exempel, när antalet föremål är mindre än antalet agenter, får minst en agent inga föremål. Ur teoretisk synvinkel är proportionaliteten och avundsfriheten alltför starka för att kunna levereras när det gäller odelbara varor. Budish [16] föreslog därför ett nyare begrepp om rättvisa för odelbara varor, nämligen maxminandelen, som har rönt stor uppmärksamhet under de senaste åren [1–3, 7–9, 13, 23, 36]. Tänk dig att vi ber en agent en i att partitionera en uppsättning M av m objekt i n buntar och samla bunten med det minsta värdet. För att maximera hans vinster, agent en jag försöker dela M på ett sätt som maximerar värdet av bunten med det lägsta värdet för honom. Baserat på detta, den maximala andelen av en agent a i, betecknad av MMS i, är värdet av den minst värdefulla bunt i agent en i's tilldelning; det vill säga den maximala vinsten a jag kan få i detta förfarande. Det är uppenbart att MMS i är det bästa som kan garanteras en agent, eftersom om alla värderingar är desamma får minst en agent en värdering av högst MMS i från sin tilldelade uppsättning. Frågan är då om det finns en tilldelning som garanterar MMS i för varje agent a i? Därför kallar vi en tilldelning MMS, om varje agent en i får en samling av objekt som tillsammans är värda minst MMS i till honom. Bouveret och Lemaitre [13] visade att när värderingen av posterna för varje agent är antingen 0 eller 1 eller när m ≤ n + 3 garanteras en MMS-tilldelning. Med andra ord, var och en a i kan garanteras att få en vinst på minst MMS i från hans fördelade poster. Även om experimenten stöder förekomsten av en MMS-tilldelning i allmänhet [13] vederlades detta antagande av Kurokawas, Procaccias och Wangs pionjärarbete [36]. Kurokawa m.fl. [36] gav ett överraskande motexempel som inte medger någon tilldelning av MMS. De visar också att det alltid finns en fördelning på 2/3 MMS, dvs. Det finns en algoritm som fördelar objekten till agenterna på ett sådant sätt att varje agent en jag får en aktie som är värd minst 2/3MMS i till honom. Session 9a: Rättvis fördelning
Tillnärmningsgarantin för MMS förbättrades ytterligare till 3/4 genom REF.
Fair Allocation of Indivisible Goods: Improvements and Generalizations
{'venue': "EC '18", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}