Detta dokument handlar om utformningen av mekanismer för online-schemaläggning där agenter bjuder på tillgång till en återanvändbar resurs såsom processortid eller trådlös nätverksåtkomst. Varje agent antas anlända och avgå dynamiskt, och i den grundläggande modellen kräver resursen för en enhet av tid. Vi söker mekanismer som är sanningsenliga i den meningen att sanningsenligt avslöjande om ankomst, avgång och värdeinformation är en dominerande strategi, och som är online i den meningen att de fattar fördelningsbeslut utan kunskap om framtiden. För det första tillhandahåller vi två karakteriseringar för klassen sanningsenliga online tilldelningsregler. Karaktäriseringarna sträcker sig bortom de typiska en-parameter inställningar, och formalisera rollen av begränsad felrapportering i att vända befintliga prisbaserade karakteriseringar. För det andra presenterar vi en onlineauktion för enhetslånga jobb som uppnår totalt värde som är 2-konkurrenskraftigt med det maximala offlinevärdet. Vi visar att ingen sanningsenlig deterministisk onlinemekanism kan uppnå ett bättre konkurrensförhållande. För det tredje anser vi att intäkter konkurrenskraft och bevisa att ingen deterministisk sanningsenlig online auktion har intäkter som är konstant konkurrenskraftig med den av offline Vickrey-Clarke-Groves (VCG) mekanism Vi tillhandahåller en randomiserad online auktion som uppnår ett konkurrenskraftigt förhållande av O (log h), där h är förhållandet mellan maximalt värde till minimivärde bland agenterna; denna mekanism kräver inte förkunskaper om h. Slutligen generaliserar vi vår modell till inställningar med flera återanvändbara varor och till agenter med olika jobblängder.
REF ] tillhandahöll en randomiserad mekanism vars effektivitetskonkurrensförhållande är O(log(σ)) (återkalla att σ är förhållandet mellan den maximala arbetslängden och den minsta arbetslängden.
Online auctions with re-usable goods
{'venue': "EC '05", 'journal': None, 'mag_field_of_study': ['Computer Science']}