Vi studerar utformningen av sanningsenliga mekanismer som inte använder betalningar för den generaliserade uppdragsproblem (GAP) och dess varianter. Ett exempel på GAP består av en bipartit graf med jobb på ena sidan och maskiner på den andra. Maskiner har kapacitet och kanter har värden och storlekar; målet är att skapa ett välfärdsmaximerande genomförbart uppdrag. I vår modell av privata värderingar, som motiveras av omöjliga resultat, är värdet och storleken på alla jobb-maskin par offentlig information; dock, om en kant finns eller inte i bipartite grafen är ett jobb privata information. Det vill säga, de själviska agenterna i vår modell är jobben, och deras privata information är deras fördel. Vi vill utforma mekanismer som är sanningsenliga utan pengar (därför strategiskt säkra), och producera uppdrag vars välfärd är en bra approximation till den optimala allvetande välfärden. Vi studerar flera varianter av GAP som börjar med matchning. För den oviktade versionen ger vi en optimal strategisäker mekanism. För maximal viktbipartitmatchning, visar vi att ingen strategisäker mekanism, deterministisk eller randomiserad, kan vara optimal, och presentera en 2-ungefärlig strategisäker mekanism tillsammans med en matchande lägre band. Nästa vi studerar Knapsack-liknande problem, som, till skillnad från matchning, är NP-hård. För dessa problem utvecklar vi en allmän LP-baserad teknik som utökar idéerna om Lavi och Swamy [14] för att minska utformningen av en sanningsenlig ungefärlig mekanism utan pengar till att utforma en sådan mekanism för den fraktionerade versionen av problemet. Vi utformar strategisäkra approximativa mekanismer för fraktionerade avkopplingar av flera knapsack, storleksinvariant GAP, och värdeinvariant GAP, och använda denna teknik för att erhålla, respektive 2, 4 och 4- approximat strategisäkra mekanismer för dessa problem. Vi utformar sedan en O(log n)-ungefärlig strategisäker mekanism för GAP genom att reducera, med logaritmisk förlust i approximationen, till vår lösning för värdeinvariant GAP. Vår teknik kan vara av oberoende intresse för att utforma sanningsenliga mekanismer utan pengar för andra LP-baserade problem.
Senast studerade Dughmi och Ghosh REF ungefärlig mekanismdesign utan pengar i samband med det generaliserade uppdragsproblemet.
Truthful assignment without money
{'venue': "EC '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}