Vi studerar urvalet komplexiteten i lärande intäkter-optimala multi-punkt auktioner. Vi får den första uppsättningen positiva resultat som går utöver standard men orealistiska fastställande av objektoberoende. Framför allt överväger vi inställningar där budgivarnas värderingar hämtas från korrelerade distributioner som kan fångas upp av Markov Random Fields eller Bayesian Networks - två av de mest framträdande grafiska modellerna. Vi etablerar parametriserade prov komplexitet gränser för att lära sig en up-to-ε optimal mekanism i båda modellerna, som skala polynomialt i storleken på modellen, dvs.. Antalet poster och budgivare, och endast exponentiellt i modellens naturliga komplexitetsmått, dvs. antingen den största in-graden (för Bayesian Networks) eller storleken på den största hyper-kanten (för Markov Random Fields). Vi får våra lärbarhetsresultat genom ett nytt och modulärt ramverk som innebär att vi först bevisar en robusthetsteorem. Vi visar att vi kan lära oss en mekanism vars intäkter är nästan optimala samtidigt för alla "sanna distributioner" som ligger nära de som vi fick på Prokhorovs avstånd. För att lära sig en bra mekanism räcker det alltså med att lära sig ungefärliga fördelningar. När objektvärden är oberoende, lärande i Prokhorov avstånd är omedelbar, därav vårt ramverk direkt innebär det huvudsakliga resultatet av Gonczarowski och Weinberg [35]. När objektvärden provtas från mer allmänna grafiska modeller, kombinerar vi vår robusthet teorem med nya prov komplexitet resultat för att lära Markov Random Fields eller Bayesian Networks i Prokhorov avstånd, vilket kan vara av oberoende intresse. Slutligen, i enpunktsfallet, kan vårt robusthetsresultat stärkas för att hålla under ett ännu svagare distributionsavstånd, Lévy-avståndet.
Brustle m.fl. REF generalisera resultatet till inställningar där objektets värden hämtas från korrelerade men strukturerade distributioner som kan modelleras av antingen Markov slumpmässiga fält eller Bayesian Networks.
Multi-Item Mechanisms without Item-Independence: Learnability via Robustness
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}