Vi studerar problemet med att fördela delbara dåliga (kores) bland flera agenter med additiva verktyg, när penningöverföringar inte är tillåtna. Konkurrensregeln är känd för att vara den bästa mekanismen för varor under additiva verktyg och utvidgades nyligen till sysslor av Bogomolnaia et al. [BMSY17].......................................................................................................... För både varor och sysslor ger regeln Pareto optimala och avundsfria tilldelningar. När det gäller varor kan resultatet av konkurrensreglerna lätt beräknas. Konkurrenskraftiga tilldelningar lösa Eisenberg-Gale konvex program; därför resultatet är unikt och kan ungefär hittas med standard gradient metoder. En exakt algoritm som körs i polynom tid i antalet agenter och varor gavs av Orlin [Orl10]. När det gäller sysslor löser inte konkurrensregeln några konvexa optimeringsproblem; istället motsvarar konkurrenskraftiga tilldelningar lokala minima, lokala maxima, och sadelpunkter Nash Social Welfare på Pareto gränsen av uppsättningen av genomförbara verktyg. Regeln blir flervärdig och ingen av standardmetoderna kan användas för att beräkna resultatet. I detta dokument visar vi att alla resultat av konkurrensregeln för sysslor kan beräknas i starkt polynom tid om antingen antalet agenter eller antalet sysslor är fast. Metoden bygger på en kombination av tre idéer: alla konsumtionsgrafer av Pareto optimala tilldelningar kan listas i polynom tid; för en given konsumtion graf, en kandidat för en konkurrenskraftig tilldelning kan konstrueras med uttrycklig formel; och en given tilldelning kan kontrolleras för att vara konkurrenskraftig med hjälp av en maximal flödesberäkning som i Devanur et al. [DPSV02]. Vår algoritm ger omedelbart en ungefärlig fördelning av odelbara sysslor genom avrundningstekniken hos Barman och Krishnamurthy [BK19].
REF visar att en tilldelning som är avundsfri upp till avlägsnande av två sysslor (EF 1 1 ) och Pareto optimal (PO) alltid finns och kan beräknas i polynom tid om antalet agenter är xed.
Algorithms for Competitive Division of Chores
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Economics']}