Abstract-Combinatorial Auktioner är ett centralt problem i Algorithmic Mechanism Design: prissättning och tilldelning av varor till köpare med komplexa preferenser för att maximera några önskade mål (t.ex. social välfärd, intäkter, eller vinst). Problemet har varit välstuderat vid begränsad leverans (en kopia av varje vara), och när det gäller digitala varor (försäljaren kan producera ytterligare kopior utan kostnad). Men när det gäller resurser olja, arbetskraft, datorcykler, etc.-ingen av dessa abstraktioner är helt rätt: ytterligare resurser av dessa resurser kan hittas, men på ökande svårigheter (marginalkostnad) som resurser utarmas. I detta arbete initierar vi studien av problemet med algoritmisk mekanism design av kombinatorisk prissättning under ökande marginalkostnad. Målet är att sälja dessa varor till köpare med okända och godtyckliga kombinatoriska värderingsfunktioner för att maximera antingen den sociala välfärden, eller säljarens vinst; specifikt fokuserar vi på fastställandet av postade postpriser med köpare som anländer online. Vi ger algoritmer som uppnår konstanta faktor approximationer för en klass av naturliga kostnadsfunktioner-linjära, låggradiga polynom, logaritmisk-och som ger logaritmiska approximationer för mer allmänna ökande marginella kostnadsfunktioner (tillsammans med en nödvändig additiv förlust). Vi visar att dessa gränser i huvudsak är bästa möjliga för dessa inställningar.
Fallet med ökande marginalkostnader undersöktes i REF där konstant konkurrensförhållande angavs.
Welfare and Profit Maximization with Production Costs
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}