Algoritmisk prissättning är det beräkningsproblem som säljare (t.ex. i stormarknader) ställs inför när de försöker sätta priser för sina produkter för att maximera sin vinst i närvaro av en känd efterfrågan. Guruswami m.fl. [9] Föreslå detta problem och ge logaritmiska approximationer (i antalet konsumenter) för fall med enhetsefterfrågan och en enda parameter där det finns en särskild uppsättning konsumenter och deras värderingar för paket är kända exakt. Därefter har flera versioner av problemet visat sig ha polylogaritmisk omätbarhet. Detta problem har direkta kopplingar till den viktiga öppna frågan om bättre förståelse för Bayesian optimal mekanism i multi-parameter agent inställningar; dock, för detta ändamål approximationsfaktorer logaritmiska i antalet agenser är otillräckliga. Det är därför av vitalt intresse att överväga särskilda fall där konstanta approximationer är möjliga. Vi anser att enhetsefterfrågan är en variant av detta prisproblem. Här har en konsument en värdering för varje enskild post och deras värde för en uppsättning poster är helt enkelt det maximala värde de har för varje post i uppsättningen. I stället för att överväga en uppsättning konsumenter med exakt kända preferenser, som den tidigare algoritmiska prislitteraturen, antar vi att konsumenternas preferenser hämtas från en distribution. Detta är standard antagandet i ekonomi; dessutom, fastställandet av en särskild uppsättning kunder med särskilda preferenser, som används i alla tidigare arbete i algoritmisk prissättning, är ett specialfall av detta allmänna Bayesian prissättningsproblem, där det finns en diskret Bayesian distribution för preferenser som specificeras genom att plocka en konsument enhetligt från den givna uppsättningen konsumenter. Observera att fördelningen över värderingarna för de enskilda poster som detta genererar uppenbarligen är korrelerad. Vårt arbete kompletterar dessa befintliga verk genom att beakta det fall där konsumentens värderingar för de olika objekten är oberoende slumpvariabler. Vår huvudsakliga * Forskning som stöds av en NSF Matematisk Vetenskap Postdoktor Forskning Fellowship. Delar av detta arbete slutfördes medan författaren var en NSF postdoktor kollega vid U.C. Det är Berkeley. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Resultatet är en konstant approximation algoritm för detta problem som använder sig av en intressant koppling mellan detta problem och begreppet virtuella värderingar från singleparameter Bayesian optimal mekanism design litteratur.
Chawla et.al Ref tar hänsyn till fallet med en enda anbudsgivare per enhet och föreslår en postprissättningsmekanism som uppnår en konstant faktor approximation av det optimala.
Algorithmic pricing via virtual valuations
{'venue': "EC '07", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}