Ett brett spektrum av on-line beteenden förmedlas av gränssnitt där människor gör val bland uppsättningar av alternativ. Ett rikt och växande arbete inom beteendevetenskapen visar att mänskliga val inte bara beror på nyttan av alternativ, utan också på det val i vilket alternativ presenteras. I detta arbete studerar vi jämförelsebaserade valfunktioner, en enkel men förvånansvärt rik klass av funktioner som kan uppvisa så kallade choice-set e ects. Motiverade av utmaningen att förutsäga komplexa val, studerar vi frågan komplexiteten i dessa funktioner i en mängd olika aspekter. Vi anser att åtgärder som möjliggör aktiva frågor eller passiv observation av en ström av frågor, och ger analyser både på granularitet av individer eller populationer som kan uppvisa heterogena val beteende. Vårt huvudsakliga resultat är att varje jämförelsebaserad valfunktion i en dimension kan härledas lika effektivt som en grundläggande maximal eller minimal valfunktion i många frågekontexter, vilket tyder på att choice-set eects inte behöver medföra några grundläggande algoritmiska hinder för slutledning. Vi introducerar också en klass av valfunktioner som vi kallar distansjämförelsebaserade funktioner, och brie y diskuterar analysen av sådana funktioner. Ramverk vi beskriver ger spännande kopplingar mellan mänskligt val beteende och en rad frågor i teorin om sortering. Ytterligare nyckelord och fraser: Choice-set eects, sortering med bullriga jämförelser, sortering i en omgång. Moderna informationssystem över ett brett spektrum av domäner brottas med allt mer expansiva och heterogena corpora av data som beskriver mänskliga beslut - från online marknadsplatser som Amazon och AirBnB inspelning olika inköp beteende till sökmotorer och rekommendationssystem som behandlar kontinuerliga klickströmmar, där klick re ect val. Många av de beslut som fattas i dessa on-line miljöer har en konsekvent struktur: användarna presenteras med en uppsättning alternativ - en lista över rekommenderade böcker, sökresultat, ight alternativ, eller användare att följa - och de väljer en eller flera objekt från uppsättningen. Allestädes närvarande inom denna ram har lett till en aktiv forskningslinje om problemet med rankningsfunktioner för lärande [1]. Ere är många formuleringar i litteraturen, men det viktigaste är att anta att en användare har en rankning över alternativ som är dolda för oss, och genom att observera deras val skulle vi vilja dra slutsatsen denna rankning. Frågan kan ställas på individnivå eller på populationsnivå som innehåller heterogena men besläktade rankningar. Valbara eekter. Ett centralt antagande i arbetet med ranking är att individer utgår från en underliggande total order på möjliga alternativ. Ungefär, överväga en inventering Z = {z 1, z 2,. .., z n } av möjliga val, globalt beställt så att en viss användare föredrar z i till z j för i < j. När användaren presenteras med en uppsättning val S  på Z, de väljer det objekt i S som rankas rst enligt denna globala ordning. Det finns många variationer på denna grundläggande pa ern - det kan finnas buller i valet, eller alternativ kan vara oobserverade - men den totala beställningen är en avgörande del av strukturen. En lång rad av arbete inom beteendevetenskap [9, 15, 22, 25, 28], visar dock att människors empiriska val tenderar att avvika avsevärt från denna bild. En persons val beror i själva verket inte bara på den totala beställningen på den fullständiga uppsättningen alternativ Z, som är o en enorm och implicit, men också på valet uppsättning S de visas som en del av den specifika c beslut till hands. Viktiga exempel på sådana val-set e ect inkluderar kompromiss e ect, likhet aversion, och lockbete e ect (även känd som asymmetrisk dominans), och har observerats i olika sammanhang både o ine och online; nyligen arbete inom maskininlärning har lyft fram förekomsten av val-set e ects [4, 19, 23, 33] och icke-transitiva jämförelser [7, 8], särskilt i online-sökning, online-annonser och online-spel. Ett kanoniskt exempel på ett val-set e ect är den så kallade kompromiss e ect [24]: inför valet mellan ett medelmåttigt alternativ för $ 10, ett bra alternativ för $ 15, och ett utmärkt alternativ för $ 20, kommer människor tenderar att välja det bra alternativet för $ 15, men ställs istället inför ett val mellan samma bra alternativ för $ 15, det utmärkta alternativet för $ 20, och ett enastående alternativ för $ 25, människor kommer att vara mer benägna att välja det utmärkta alternativet för $ 20. Med andra ord finns det en tendens att gynna alternativet att kompromissa mellan de två ytterligheterna i den uppsättning som presenteras. Mer allmänt, anta att en uppsättning produkter uppvisar en trade-o mellan två faktorer -till exempel, pris vs. kvalitet, kraft vs. tillförlitlighet, eller estetik vs. bränsleeffektivitet. De är de alternativ för vilka ingen annan produkt är mer önskvärd i båda faktorerna. Betrakta fyra produkter A, B, C och D som arrangeras i denna ordning längs den endimensionella gränsen (A är den minst kraftfulla men mest tillförlitliga, och D som den mest kraftfulla men minst tillförlitliga). I en mängd olika set, B kommer empiriskt väljas mer o en när det presenteras som ett av de tre valen S = {A, B, C} än när det är ett av de tre valen S = {B, C, D} -med andra ord, när det är kompromissalternativet snarare än ett extremt alternativ. Genom samma resonemang, C kommer att väljas mer o en när det presenteras som en del av S än som en del av S. Man kan fråga om detta är helt enkelt en representativ fråga, men i själva verket är det mycket djupare. e Poängen är att i varje modell baserat på en total beställning på alternativen Z, skulle en användare föredra antingen B eller C, och detta skulle hålla i alla val som S som innehåller båda av dem. Men B och C är alternativ i båda uppsättningarna S = {A, B, C} och S = {B, C, D}, och den sammanlagda fördelningen av val till förmån för B kontra C förändringar över dessa två uppsättningar. är tyder på att den relativa beställningen av B och C i själva verket inte är väl avgränsade separat, men måste utvärderas i samband med valet som (S eller S ). Det är vad som annars finns på Oer. Jämförelsebaserade valfunktioner. I det här dokumentet överväger vi en uppsättning grundläggande algoritmiska frågor som uppstår när vi försöker dra slutsatser om modeller av användarval i närvaro av jämförelsebaserade choice-set e ects. Vi fokuserar på en grundläggande formulering där dessa eekter uppstår, och visar hur vårt ramverk gör det möjligt att härleda asymptotiska gränser på frågekomplexitet och prov komplexitet i att utföra dessa typer av inferens. Vi satte upp problemet på följande sätt. (1) Inbäddning av alternativ. e full samling av alternativ är en uppsättning U = {u 1,. ., u n }, och det finns en inbäddning av U i ett utrymme av en rimutes X via en funktion h : U → X. För de flesta av vår diskussion kommer vi att ta X att vara den verkliga linjen R 1, så att h (u i ) är ett reellt tal; således större delen av tiden kan vi tänka på de inbäddade punkterna { h(u 1 ),. .., h (u n )} som representerar en endimensionell trade-o continuum som i diskussionen ovan. Vi kommer att anta att inbäddningen h inte är känd för oss. Ja, även om vi ibland kan veta den avgörande endimensionella en ribout av ett objekt, sådan
Kleinberg m.fl. Ref överväga en allmän klass av jämförelsebaserade urvalsmodeller, och studera komplexiteten i att lära sig sin modell från prover.
Comparison-based Choices
{'venue': "EC '17", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}