Vi studerar online budgeterad tilldelning (även kallad ADWORDS) problem, där en uppsättning intryck som anländer online tilldelas en uppsättning budgeterade annonsörer för att maximera intäkterna. Motiverad av Internetreklam har flera varianter av detta problem undersökts sedan Mehta, Saberi, Vazirani och Vazirani (FOCS 2005). Hela detta arbete är dock inriktat på en enda budget för varje reklamkampanj, medan en reklambudget bör vara uttrycklig på flera nivåer för att fullt ut representera en annonsörs faktiska agenda. Ett enkelt exempel är en reklamkampanj som begränsas av en övergripande budget men som också åtföljs av en uppsättning underbudgetar för varje målgruppsdemografi. I ett sådant avtalssystem kan en annonsör ange sina verkliga användarmål, vilket gör det möjligt för förlaget att uppfylla dem genom relevanta tilldelningar. I detta dokument ger vi en fullständig karakterisering av ADWORDS-problemet för allmänna reklambudgetar. I den mest allmänna situationen visar vi att det till skillnad från problemet med ADWORDS med en enda budget är omöjligt att uppnå ett konstant konkurrensförhållande och ge asymptotiskt snäva övre och nedre gränser. Men för vårt huvudresultat konstaterar vi att i många verkliga scenarier (som i exemplet ovan) har budgetar på flera nivåer en laminär struktur, eftersom de mest relevanta konsument- eller produktklassificeringarna är hierarkiska. För laminära budgetar får vi ett konkurrensförhållande på e/e − 1) i det lilla anbudsärendet, vilket motsvarar det mest kända ADWORDS-resultatet för enskilda budgetar. Vår algoritm har en primal-dual struktur och generaliserar den primära analysen för en budget ADWORDS först ges av Buchbinder, Jain och Naor (ESA 2007). Men många nya idéer krävs för att övervinna de hinder som införts av laminar budgets-our algoritm använder en ny formulering som övervinner icke-monotonicitet i de syntaktiskt definierade dubbla variablerna, samt ett dynamiskt underhållet märkningssystem som följer de "mest begränsade" budgetarna i hierarkin.
REF betraktas som onlinebudgeterad tilldelning med allmänna budgetar, där offline-agenter har flera nivåer av budgetbegränsningar som bildar en laminär struktur.
Online Budgeted Allocation with General Budgets
{'venue': "EC '16", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}