Ми представили Теорію пошуку з фіксованою моделлю пошуку зразків. Споживач вибирає з населення магазинів і отримує список n цін на товар, потім вибирає мінімальну ціну. Чим більше n, тим нижча мінімальна ціна в списку, але ціна, заплачена для отримання цінових котирувань, збільшується з ростом n. Споживач повинен вирішити, скільки цін отримати.
У цьому розділі розглядаються властивості іншої ситуації, відомої як модель послідовного пошуку. На відміну від фіксованого вибіркового пошуку, де споживач отримує набір цінових котирувань, а потім вибирає найнижчу ціну, послідовний пошук триває по черзі. Споживач відбирає у населення і отримує єдину ціну, потім вирішує, приймати її чи ні. Якщо вона відкине це, вона не може повернутися назад. Як показує епіграф, модель послідовного пошуку легко застосовується до пропозицій роботи, але вона буде застосована в цьому розділі до іншої поширеної проблеми пошукукупівлі газу.
Налаштування моделі
Уявіть, що ви їдете по дорозі, і вам потрібно паливо. Коли ви їдете, є заправки (скажімо N = 100) ліворуч і праворуч (взявши вліво вас не надто турбує), і ви можете легко прочитати ціну за галон, коли ви під'їжджаєте до кожної станції. Якщо ви проїжджаєте повз станцію, про поворот не може бути й мови (є трафік, і у вас дивна фобія щодо розворотів).
Існує найнижча цінова станція, і станції можна ранжувати від 1 (найнижча, найкраща ціна) до 100 (найвища, найгірша ціна). Ви не знаєте ціни, що піднімаються, тому що станції випадковим чином розподілені на дорозі. Найнижча цінова станція може бути 18-ю або 72-ю або навіть найпершою. Малюнок 7.7 підсумовує все це.
Малюнок 7.7: Вирішуємо, де купити газ.
Припустимо, ви зосереджуєтеся на наступному питанні: Як ви максимізуєте шанси знайти найдешевшу станцію?
Ви можете стверджувати, що ви повинні їздити по всіх станціях, а потім просто вибрати найкращу. Це жахлива ідея, тому що ви не можете повернутися назад (пам'ятайте, ніяких розворотів). Після того, як ви пройдете станцію, ви не зможете повернутися до неї. Отже, ця стратегія спрацює тільки в тому випадку, якщо найдешевша станція буде найостаннішою. Шанси на те, що є 1 в 100.
Стратегія вибору станції виглядає так: Виберіть деяке число,\(K < N\) де ви відхиляєте (проїжджаєте) станції від 1 до K, а потім виберіть першу станцію, яка має ціну нижчу за найнижчу з K станцій, які ви відхилили.
Можливо, K = 50 - правильна відповідь? Тобто їдьте по станціях 1 до 50, потім подивіться на наступну (51-ю) станцію і якщо вона краще, ніж найнижча з 50 ви проїхали повз, потягніть. Якщо ні, передайте його вгору і розгляньте 52-ю станцію. Якщо це дешевше, ніж попередній 51 (або від 1 до 50, оскільки ми знаємо, що 51-я станція не дешевша за найдешевшу з перших 50), отримайте там газ.
Продовжуйте цей процес, поки ви десь не отримаєте газ, потягнувши на останню (100-ю) станцію, якщо доберетеся до неї (на ній буде табличка з написом «Останній шанс АЗС»).
Ця стратегія зазнає невдачі, якщо найнижча ціна знаходиться в групі K станцій, на яких ви проїхали, тому ви можете вибрати K, щоб бути малим. Але якщо ви виберете K занадто малий, ви отримаєте лише кілька цін, і перша станція з ціною нижче найнижчої з K станцій навряд чи дасть вам найнижчу ціну.
Отже, K = 3, ймовірно, не буде працювати добре, тому що ви, ймовірно, не отримаєте супер низьку ціну в наборі всього три, так що ви, ймовірно, не будете в кінцевому підсумку вибрати найнижчу ціну. Наприклад, скажімо, перші три станції займають 41, 27 і 90 місце. Тоді, як тільки ви побачите станцію краще, ніж 27, ви потягнете туди. Це може бути 1, але з 26 можливостями, це навряд чи.
З іншого боку, високе значення K, скажімо, 98, страждає від того, що найнижча цінова станція, ймовірно, знаходиться в цій групі, і ви вже відкинули її! Так, ця проблема, безумовно, складна.
Модель послідовного пошуку може бути використана набагато більше, ніж покупка газу має надзвичайно широку застосовність і, в математиці, вона відома як оптимальна зупинка. При прийомі на роботу це називається проблемою секретаря. Фірма вибирає перших K претендентів, співбесіди та відхиляє їх, а потім вибирає наступного заявника, який краще, ніж кращий з K заявників. Це також стосується багатьох інших областей, включаючи пошук шлюбу в Інтернеті для Кеплера оптимальної зупинки, щоб побачити, як знаменитий астроном вибрав свою дружину.
КРОК Відкрийте книгу Excel SequentialSearch.xls і прочитайте Введення аркуша, а потім перейдіть до аркуша установки.
Колонка А має 100 станцій, що ранжуються від 1 до 100. Найнижча ціна станції - 1, а найвища ціна станції - 100.
КРОК Натисніть кнопку. Вона перетасовує станції, випадковим чином розподіляючи їх по дорозі, по якій ви їдете в колонці D.
Cell B7 повідомляє, де знаходиться станція з найнижчою ціною (#1). Стовпці C і D повідомляють про розташування кожної станції. Колонка D змінюється щоразу, коли ви натискаєте кнопку, оскільки станції перемішуються.
Клітинка F2 встановлює значення K. Це змінна вибору в цій задачі. Наша мета полягає в тому, щоб визначити значення K, яке максимізує ймовірність того, що ми отримаємо станцію з найнижчою ціною.
На відкритті К = 10. Ми проходимо станції 1 до 10, а потім візьмемо наступну станцію, яка краще, ніж найкраща з 10 станцій, які ми відхилили.
КРОК Натисніть кнопку. Це перестановки станцій і малює межу в стовпці D для комірки на K-й станції.
Cell F5 повідомляє про найкращу з K станцій (які були відхилені). Cell F7 відображає станцію, на якій ви опинилися.
КРОК Прокрутіть вниз, щоб зрозуміти, чому ви опинилися на цій станції і прочитали текст на аркуші.
Cell F7 завжди відображає першу станцію, яка краща (нижча), ніж найкраща з K станцій у комірці F5.
КРОК. Повторно натискаємо кнопку. Після кожного кліка дивіться, як ви це зробили. Чи є 10 хорошим вибором для K?
Визначення хорошого вибору в цьому випадку - це таке, яке має високу ймовірність дати нам найдешевшу станцію. Наша мета - максимізувати шанси отримати найдешевшу станцію. Ми могли б мати іншу мету, наприклад, мінімізувати середню сплачену ціну, але це була б інша проблема оптимізації. Для класичного варіанту оптимальної проблеми зупинки ми рахуємо успіх лише тоді, коли знаходимо найдешевшу станцію.
КРОКЗмініть K на 60 (в F2) і кілька разів натисніть кнопку. Чи 60 краще, ніж 10?
На це важко відповісти за допомогою листа налаштування. Вам доведеться неодноразово натискати кнопку і відстежувати відсоток часу, який ви отримали найдешевшу станцію. Це зажадає багато терпіння і часу нудно натискати і записувати результат. На щастя, є кращий спосіб.
Рішення задачі за допомогою моделювання Монте-Карло
Лист налаштування є хорошим способом зрозуміти проблему, але він не корисний для з'ясування оптимального значення K. Потрібен спосіб швидко, багаторазово вибірка і запис результату. Це те, що робить лист McSim.
КРОК. Приступаємо до листа McSim і переглядаємо його.
З N = 100 (ми можемо змінити цей параметр пізніше), ми встановлюємо значення K (в осередку D7) і запускаємо моделювання Монте-Карло, щоб отримати приблизні шанси отримати кращу станцію (повідомляється в осередку H7).
На відміну від надбудови McSim, використовуваної в попередньому розділі, це моделювання Монте-Карло жорстко підключено до цієї книги. Таким чином, він надзвичайно швидкий.
КРОК З N = 100 і K = 10 натисніть кнопку. Кількість повторень за замовчуванням становить 50 000, що здається високим, але комп'ютер може робити сотні тисяч повторень за лічені секунди.
На малюнку 7.8 показані результати. Вибір K = 10 дає нам найкращу станцію приблизно 23,4% часу. Ваші результати будуть трохи відрізнятися.
Малюнок 7.8: Результати моделювання Монте-Карло.
Джерело: SequentialSearch.xls! МакСім
Зверніть увагу, що ми використовуємо моделювання Монте-Карло, щоб наблизити точну відповідь. Моделювання Монте-Карло не може дати нам точної відповіді. Збільшуючи кількість повторень, ми покращуємо наближення, стаючи все ближче і ближче, але ми ніколи не можемо отримати точну правду з моделюванням. Відповідь, яку він дає, залежить від фактичних результатів у цьому конкретному запуску. Єдиний спосіб моделювання дасть точну відповідь, якби вона була заснована на нескінченній кількості повторень.
Чи можемо ми зробити краще, ніж отримати найкращу станцію близько 23% часу?
Ми можемо відповісти на це питання, вивчивши, як шанси отримати найнижчу ціну варіюються від K. Змінюючи значення K і запустивши моделювання Монте-Карло, ми можемо оцінити продуктивність різних значень K.
КРОК Вивчіть різні значення K і заповніть таблицю в осередках J3: M10.
Як тільки ви зробите перший запис в таблиці, K = 20, ви бачите, що він б'є K = 10.
КРОК Використовуйте дані в заповненій таблиці, щоб створити діаграму шансів отримати найнижчу цінову станцію як функцію K. Використовуйте кнопку під столом, щоб перевірити свою роботу.
Що ви робите висновок з цього аналізу?
Однією з проблем моделювання Монте-Карло є мінливість результатів. Кожен пробіг дає різні відповіді, оскільки кожен пробіг є наближенням до точної відповіді на основі реалізованих результатів. Таким чином, здається досить зрозумілим, що оптимальне значення K становить від 30 до 40, але за допомогою моделювання знайти точну відповідь важко.
На малюнку 7.9 відображені результати серії експериментів Монте-Карло. Зверніть увагу, що ми подвоїли кількість повторень, щоб збільшити роздільну здатність. Кращим значенням К видається 36, але гучність в результатах моделювання унеможливлює визначення відповіді.
Малюнок 7.9: Збільшення масштабу на значення оптимального K.
Джерело: SequentialSearch.xls! Відповіді
За допомогою моделювання Монте-Карло ми можемо продовжувати збільшувати кількість повторень, щоб покращити наближення.
КРОК Перейдіть до листа відповідей, щоб побачити більше результатів моделювання.
Лист відповідей показує, що навіть 1 000 000 повторень недостатньо, щоб остаточно дати нам правильну відповідь. Моделювання має важкий час розрізнення між значенням зупинки K 36 або 37.
Точне рішення
Цю проблему можна вирішити аналітичним шляхом. Рішення реалізовано в Excel. Детальніше див. Цитування Фергюсона в кінці цього розділу.
КРОК Перейдіть до аналітичного аркуша, щоб побачити точну ймовірність отримання найдешевшої станції для заданого зразка розміром K від N станцій від 5 до 100.
Наприклад, осередок G10 відображає 32,74%. Це означає, що у вас є 32.74% ймовірність отримати найдешевшу станцію з 10 станцій, якщо ви їдете на перших шести станціях, а потім вибираєте наступну станцію, яка має ціну нижчу, ніж найдешевша з K станцій, на яких ви проїхали.
Для N = 10, є K = 6 найкращим рішенням?
Ні. Імовірність вибору найдешевшої станції підвищується, якщо вибрати K = 5. Вибір 3 та 4 близький, але очевидно, що оптимальний K = 3 (з ймовірністю 39,87% отримати найдешевшу станцію) є найкращим вибором.
У прикладі, над яким ми працювали, ми мали N = 100. Моделювання Монте-Карло показав оптимальну K навколо 36 або 37, але у нас виникли проблеми з пошуком точної правильної відповіді.
КРОК Прокрутіть вниз, щоб побачити ймовірності для N = 100. Натисніть на осередки AL100 і AM100, щоб побачити точні значення. Дисплей було округлено до двох десяткових знаків (у відсотках), але обчислення точні до більшої кількості десяткових знаків.
K * = 37 просто ледь вибиває K = 36. Той факт, що вони майже дають точно такі ж шанси отримати найнижчу ціну, пояснює, чому ми мали так багато проблем з масштабуванням правильної відповіді з моделюванням Монте-Карло.
Можна показати (див. Джерело Фергюсона в розділі References), що оптимальним є K\(\frac{N}{e}\), що дає ймовірність знайти найдешевшу станцію\(\frac{1}{e}\). Для N = 100,\(\frac{N}{e} \approx 36.7879\).
Якби K була безперервною ендогенною змінною,\(\frac{N}{e}\) було б оптимальним рішенням. Але це не так, тому точна, правильна відповідь - пройти перші 37 станцій, а потім взяти першу з нижчою ціною, ніж найнижча ціна станцій 1 до 37.
Загадка, чому трансцендентне число е, основа природних логарифмів, відіграє певну роль у розв'язанні.
На малюнку 7.10 показано, що, як N піднімається, так і оптимальний K. Яка пружність тут розглядається?
Відповіддю є N пружність K. Від N = 50 до 100 - це 100% -ний приріст. Що відбувається з оптимальним K? Він йде від 18 до 37, тому трохи більше 100%. Еластичність трохи більше одиниці. Якщо використовувати безперервний варіант K, то K точно також подвоюється і N пружність K рівно одна.
Уроки послідовного пошуку
На відміну від моделі пошуку фіксованого зразка (де ви отримуєте набір цін і вибираєте найкращу), модель послідовного пошуку говорить, що ви малюєте зразки спостережень один за одним. Це може стосуватися рішення про вибір АЗС. Коли ви їдете по дорозі, ви вирішуєте, чи потрібно ввійти і отримати газ на станції X або пройти цю станцію і перейти до станції Y.
Зіткнувшись з дисперсією цін, водій, який вирішує, де взяти газ, може бути змодельований як рішення моделі послідовного пошуку. Хоча можуть бути й інші цілі (наприклад, отримання найнижчої середньої ціни), метою може бути максимізація шансів отримати найнижчу ціну. Ми виявили, що як N піднімається, так і оптимальний K. Чим більше станцій, тим більше водіння ви повинні зробити, перш ніж вибрати станцію.
Як і модель пошуку фіксованого зразка, модель послідовного пошуку не має жодної взаємодії між фірмами та споживачами. Наведено цінову дисперсію і модель використовується для аналізу того, як споживачі реагують у заданому середовищі.
У дні до Інтернету та смартфонів вирішити, де взяти газ, було досить складним завданням. Водій, що проходить знаки з цінами (наприклад, рис. 7.7) був досить точним відображенням навколишнього середовища. Там не було карт Google або додатків, що відображають ціни навколо вас. Однак зверніть увагу, що Закон однієї ціни ще не поширюється на ціни на газ.
Фергюсон зазначає, що наша модель послідовного пошуку (яку математики називають проблемою секретаря) є частиною класу задач скінченного горизонту. «Існує велика література з цієї проблеми, і одна книга «Проблеми найкращого відбору (російською мовою) Березовського і Гнідіна (1984) присвячена виключно їй» (Фергюсон, глава 2).
Фіксовані зразки та послідовні моделі пошуку є лише вершиною айсберга. Існує величезна література та багато застосувань в економіці пошуку, економіці інформації та економіці невизначеності.
Вправи
Використовуйте результати в аналітичному аркуші для обчислення N пружності K* від N = 10 до 11. Покажіть свою роботу.
Використовуйте результати в аналітичному аркуші, щоб намалювати діаграму K* у функції N. Скопіюйте та вставте графік у документ Word.
Виконайте моделювання Монте-Карло, яке підтримує одну з комбінацій N - K * в аналітичному аркуші. Сфотографуйте результати моделювання та вставте їх у документ Word.
Поясніть, чому моделювання Монте-Карло не вдалося точно повторити відсоток разів найнижча ціна станції була знайдена.
Посилання
Епіграф взято зі сторінок 115 та 116 Дж. Макколла, «Економіка інформації та пошуку роботи», «Квартальний економічний журнал», том 84, № 1 (лютий 1970), с. 113—126, www.jstor.org/stable/1879403. Ця стаття показує, що послідовний пошук (з відкликанням) домінує над фіксованим пошуком зразків. Докладніше про цей момент див. Роберт Файнберг та Вільям Джонсон, «Перевага послідовного пошуку: розрахунок», Південний економічний журнал, Том 43, № 4 (квітень 1977), стор. 1594—1598, www.jstor.org/stable/i243526.
Томас Фергюсон, Оптимальна зупинка та додатки вільно доступні в Інтернеті за адресою www.math.ucla.edu/ tom/Stopping/Contents.html. Фергюсон пропонує технічну, математичну презентацію теорії пошуку.
Маккенна, «Економіка невизначеності» (Нью-Йорк: Oxford University Press, 1986), є стислим, нетехнічним вступом до недосконалих інформаційних моделей.
Джон Аллен Паулос, Beyond Numeracy (Нью-Йорк: Альфред А. Кнопф, 1991), стор. 64, обговорює оптимальну проблему інтерв'ю з легким, інтуїтивним стилем.
Малюнок 7.7: Вирішуємо, де купити газ.
кнопку. Вона перетасовує станції, випадковим чином розподіляючи їх по дорозі, по якій ви їдете в колонці D.
кнопку. Це перестановки станцій і малює межу в стовпці D для комірки на K-й станції.
натискаємо кнопку. Після кожного кліка дивіться, як ви це зробили. Чи є 10 хорошим вибором для K?
кнопку. Кількість повторень за замовчуванням становить 50 000, що здається високим, але комп'ютер може робити сотні тисяч повторень за лічені секунди.
