Байесовская оптимальная цена - Bayesian-optimal pricing

Байесовская оптимальная цена (Ценообразование BO) - это своего рода алгоритмическое ценообразование в котором продавец определяет цены продажи на основе вероятностных допущений относительно оценок покупателей. Это простой вид Байесовский оптимальный механизм, в котором цена определяется заранее без сбора реальных заявок покупателей.

Отдельный товар и один покупатель

В простейшем случае у продавца есть один товар для продажи (с нулевой стоимостью) и один потенциальный покупатель. Самая высокая цена, которую покупатель готов заплатить за товар, называется оценка покупателя. Продавец хотел бы установить цену точно по оценке покупателя. К сожалению, продавец не знает оценки покупателя. В байесовской модели предполагается, что оценка покупателя случайная переменная взяты из известного распределения вероятностей.

Предположим, что кумулятивная функция распределения покупателя ${\displaystyle F(v)}$, определяемая как вероятность того, что оценка продавца меньше, чем ${\displaystyle v}$. Тогда, если цена установлена ​​на ${\displaystyle p}$, то ожидаемое значение от выручки продавца составляет:^[1]

${\displaystyle Rev(p)=p\cdot (1-F(p))}$

потому что вероятность того, что покупатель захочет купить товар, равна ${\displaystyle 1-F(p)}$, и если это произойдет, выручка продавца составит ${\displaystyle p}$.

Продавец хочет найти цену, которая максимизирует ${\displaystyle Rev(p)}$. Условие первого порядка, что оптимальная цена ${\displaystyle p^{*}}$ должен удовлетворять, это:

${\displaystyle p^{*}={1-F(p^{*}) \over f(p^{*})}}$

куда ${\displaystyle f(p)=F'(p)=}$ то функция плотности вероятности.

Например, если распределение вероятностей оценки покупателя однородно в ${\displaystyle [a,a+d]}$, тогда ${\displaystyle F(v)=(v-a)/d}$ и ${\displaystyle f(v)=1/d}$ (в ${\displaystyle [a,a+d]}$). Условие первого порядка: ${\displaystyle p^{*}=(a+d-p^{*})}$ что подразумевает ${\displaystyle p^{*}=(a+d)/2}$. Это оптимальная цена, только если она находится в диапазоне ${\displaystyle [a,a+d]}$ (т.е. когда ${\displaystyle a\leq d}$В противном случае (когда ${\displaystyle a\geq d}$) оптимальная цена ${\displaystyle p^{*}=a}$.

Эта оптимальная цена имеет альтернативную интерпретацию: это решение уравнения:

${\displaystyle w(p^{*})=0}$

куда ${\displaystyle w}$ это виртуальная оценка агента. Таким образом, в этом случае цена BO эквивалентна цене Байесовский оптимальный механизм, который представляет собой аукцион с резервной ценой ${\displaystyle p^{*}}$.

Один товар и много покупателей

В этом случае у продавца есть один предмет для продажи (с нулевой стоимостью), и есть несколько потенциальных покупателей, оценки которых представляют собой случайный вектор, взятый из некоторого известного распределения вероятностей. Здесь на ум приходят разные способы ценообразования:^[2]

• Симметричные цены: продавец устанавливает единую цену на товар. Если один или несколько покупателей соглашаются с этой ценой, то один из них выбирается произвольно.
• дискриминационные цены: продавец устанавливает разную цену для каждого покупателя. Если один или несколько покупателей соглашаются с этой ценой, то выбирается покупатель, который согласился на самую высокую цену. Дискриминационное ценообразование может осуществляться последовательно, упорядочивая цены в порядке убывания и отдавая товар первому покупателю, который принимает предложенную ему цену.

В настройке с несколькими покупателями цена BO больше не эквивалентна БО аукцион: при ценообразовании продавец должен определить цену заранее, в то время как на аукционе продавец может определить цену на основе ставок агентов. Конкуренция между покупателями может позволить аукционисту поднять цену. Следовательно, теоретически продавец может получить более высокий доход на аукционе.

Пример.^[3] Есть два покупателя, оценки которых равномерно распределены в диапазоне ${\displaystyle [\$100,\$200]}$.

• Аукцион BO - это Викри аукцион с начальной ценой $ 100 (= обратная виртуальная оценка 0). Ожидаемая выручка - 133 доллара.
• Дискриминационная схема ценообразования BO заключается в том, чтобы предложить одному агенту цену в 150 долларов, а другому агенту - 100 долларов. Его ожидаемый доход составляет 0,5 * 150 + 0,5 * 100 = 125 долларов США.

Однако на практике аукцион является более сложным для покупателей, поскольку он требует от них заранее объявить свою оценку. Сложность процесса аукциона может отпугнуть покупателей и, в конечном итоге, привести к потере дохода.^[4][5] Поэтому интересно сравнить оптимальную выручку от ценообразования с оптимальной выручкой от аукциона, чтобы увидеть, какой доход теряет продавец, используя более простой механизм.

Покупатели с независимыми и одинаковыми оценками

Блюмрозен и Холенштейн^[2] изучите особый случай, когда оценки покупателей представляют собой случайные величины, полученные независимо от того же распределения вероятностей. Они показывают, что, когда распределение оценок покупателей ограниченная поддержка, БО-ценообразование и БО-аукцион сходятся к одному и тому же доходу. Скорость сходимости асимптотически одинакова, когда дискриминационные цены разрешены, и медленнее на логарифмический коэффициент, когда необходимо использовать симметричные цены. Например, когда распределение равномерно в [0,1] и есть ${\displaystyle n}$ потенциальные покупатели:

• выручка аукциона БО (a Викри аукцион с резервной ценой, определяемой распределением вероятностей) ${\displaystyle 1-2/n}$;
• доход от дискриминационного ценообразования БО составляет ${\displaystyle 1-4/n}$;
• доход от симметричного ценообразования БО составляет ${\displaystyle 1-\log(n)/n}$.

Напротив, когда распределение оценок покупателей неограниченная поддержкаценообразование БО и аукцион БО могут не привести к одинаковому доходу. Например, когда cdf ${\displaystyle F(x)=1-1/x^{2}}$:

• выручка аукциона БО составляет ${\displaystyle .88{\sqrt {n}}}$;
• доход от дискриминационного ценообразования БО составляет ${\displaystyle .7{\sqrt {n}}}$;
• доход от симметричного ценообразования БО составляет ${\displaystyle .64{\sqrt {n}}}$.

Покупатели с независимыми и разными оценками

Чавла и Хартлайн, Малек и Сиван^[3] изучить обстановку, в которой оценки покупателей представляют собой случайные величины, полученные независимо от различных распределений вероятностей. Более того, существуют ограничения на набор агентов, которые могут обслуживаться вместе (например, количество единиц ограничено). Они рассматривают два типа дискриминационных схем ценообразования:

• В механизм ценообразования без учета заказов (OPM) разработчик механизма определяет цену для каждого агента. Агенты приходят в произвольном порядке. Гарантии механизма относятся к наихудшему (состязательному) порядку агентов, определяемому после составления оценок агентов.
• В последовательный механизм ценообразования (SPM) разработчик механизма определяет как цену для каждого агента, так и порядок для агентов. Механизм перебирает агентов в заранее определенном порядке. Если текущий агент может обслуживаться вместе с ранее обслуженными агентами (в соответствии с ограничениями), то ему предлагается его личная цена, и он может либо принять ее, либо оставить ее.

Их общая схема расчета цен такова:

• Для каждого агента ${\displaystyle j}$вычислить вероятность ${\displaystyle q_{j}}$ с которым механизм БО (механизм Майерсона) служит агенту ${\displaystyle j}$. Это можно рассчитать либо аналитически, либо путем моделирования.
• Цена для агента ${\displaystyle j}$ является ${\displaystyle p_{j}:=F_{j}^{-1}(1-C\cdot q_{j})}$, куда ${\displaystyle C}$ является константой (1, 1/2 или 1/3, в зависимости от настройки). Другими словами, цена ${\displaystyle p_{j}}$ удовлетворяет следующему условию:

Prob [оценка агента ${\displaystyle j}$ по крайней мере ${\displaystyle p_{j}}$] = ${\displaystyle C\times }$ Вероятно [механизм БО обслуживает агента ${\displaystyle j}$].

Если ${\displaystyle C=1}$ тогда предельная вероятность того, что агент обслуживается SPM, равна предельной вероятности того, что он обслуживается аукционом BO.

Коэффициенты аппроксимации, получаемые с помощью OPM, зависят от структуры ограничений:^[3]:318

• униформа матроид или же раздел matroid ограничения - 2 (т. е. доход от BO OPM составляет не менее 1/2 дохода от аукциона Myerson BO).
• графический матроид - 3
• Пересечение двух матроиды разделов - 6.75
• Пересечение графического матроида и матроида перегородок - 10,66
• Общий матроид с ранг матроидов ${\displaystyle k}$ - ${\displaystyle O(\log(k))}$

Кроме того, они показывают две нижние границы:

• OPM не может гарантировать более 1/2 выручки от аукциона BO, даже при настройке отдельных позиций.
• OPM не может гарантировать больше, чем ${\displaystyle O({\log \log {n}/\log {n}})}$ доход от аукциона BO при наличии нематроидного ограничения, закрытого сверху вниз.

Коэффициенты аппроксимации, получаемые с помощью SPM, естественно, лучше:

• Унифицированный матроид, матроид перегородок - e / (e-1) ≅ 1.58
• Общий матроид - 2
• Пересечение двух матроидов - 3

Нижняя оценка (доказана ^[2]) составляет примерно 1,25.

Ян^[6] объясняет успех подхода последовательного ценообразования, основанного на концепции корреляционный разрыв, следующим образом. Выручка механизма связана с установленной функцией ${\displaystyle f}$. Например, на аукционе k единиц функция ${\displaystyle f(S)=\min(|S|,k)}$

• Выручка аукциона БО не превышает ${\displaystyle f(Winners)\cdot Price}$, где «Победители» - множество из k агентов с наивысшими оценками.
• Доход BO SPM не менее ${\displaystyle f(Demand)\cdot Price}$, где «Спрос» - это совокупность агентов, оценка которых выше цены.

И «Победители», и «Спрос» - это случайные множества, определяемые оценками агентов. Более того, тщательно установив цену, можно гарантировать, что каждый агент ${\displaystyle j}$ имеет такую ​​же вероятность ${\displaystyle q_{j}}$ быть в «победителях» и быть «востребованным». Однако в «Победителях» существует высокая корреляция между разными агентами (если один агент выигрывает, больше вероятность того, что другие агенты проигрывают), в то время как в «Спросе» агенты независимы. Следовательно корреляционный разрыв - это верхний предел потери производительности при использовании BO SPM вместо аукциона BO. Это дает следующие коэффициенты приближения:

• Общий матроид - ${\displaystyle e/(e-1)}$
• k-единиц аукционов (подслучай общих матроидов) - ${\displaystyle 1/(1-1/{\sqrt {2\pi k}})}$
• p-независимые системы множеств (обобщение пересечения ${\displaystyle p}$ матроиды) - ${\displaystyle p+1}$.

Разные товары и один покупатель единичного спроса

В этой настройке у продавца есть несколько разных предметов для продажи (например, автомобили разных моделей). Есть один потенциальный покупатель, которого интересует отдельный товар (например, одна машина). У покупателя своя оценка для каждого типа позиции (т. Е. У него есть вектор оценки). Учитывая объявленные цены, покупатель покупает предмет, который дает ему наибольшую чистую полезность (оценка за вычетом цены).

Вектор оценки покупателя - это случайный вектор из многомерного распределения вероятностей. Продавец хочет вычислить вектор цен (цену за товар), который принесет ему наибольший ожидаемый доход.

Чавла, Хартлайн и Кляйнберг^[7] изучите случай, когда оценки покупателя различных товаров являются независимыми случайными величинами. Они показывают, что:

• Доход от ценообразования на единицу спроса BO, когда есть ${\displaystyle n}$ item-types - это не более чем доход от аукциона по продаже отдельных предметов BO, когда есть ${\displaystyle n}$ потенциальные покупатели.
• Когда покупатель оценивает разные товары независимо от одно и тоже распределение, ценообразование BO на единицу потребления, в котором используется одно и тоже цена на все предметы составляет не менее 1 / 2,17 выручки от аукциона по продаже отдельных предметов.^[8]
• Когда оценки покупателя являются независимыми, основаны на разных распределениях, ценообразование на основе спроса на единицу продукции, использующее те же самые виртуальная цена (на основе виртуальные оценки ) составляет не менее 1/3 выручки от аукциона по продаже отдельных предметов БО.

Также они рассматривают вычислительную задачу расчета оптимальной цены. Основная задача - рассчитать ${\displaystyle w^{-1}}$, инверсия виртуальной оценочной функции.

• За дискретный и регулярный распределения оценки, существует 3-аппроксимация за полиномиальное время.
• За непрерывный и регулярный Распределение оценок (доступно через оракул) существует полиномиальное (3 + ε) -аппроксимация с большой вероятностью, и более быстрое (6 + ε) -приближение с вероятностью 1.

Разные товары и множество покупателей единичного спроса

В этой настройке есть разные типы элементов. У каждого покупателя разные оценки разных предметов, и каждый покупатель хочет не более одного предмета. Более того, существуют заранее заданные ограничения на набор пар покупатель-товар, которые могут быть распределены вместе (например: каждый товар может быть назначен не более чем одному покупателю; каждый покупатель может получить не более одного товара и т. Д.).

Чавла, Хартлайн, Малек и Сиван^[3] изучите два вида дискриминационных схем ценообразования:

• В последовательный механизм ценообразования (SPM) разработчик механизма определяет цену для каждой пары покупатель-товар и порядок заказов для пар покупатель-товар. Механизм перебирает пары покупатель-товар в заранее определенном порядке. Если текущая пара покупатель-товар возможна, покупателю предлагается товар по заранее определенной цене, и он может либо взять его, либо оставить.
• В механизм ценообразования без учета заказов (OPM) разработчик механизма определяет цену для каждой пары покупатель-товар. Покупатели приходят в произвольном порядке, который может быть определен на основе состязательности после составления оценок агентов.

Механизм последовательного ценообразования, как правило, не правдивый механизм, поскольку агент может принять решение отклонить хорошее предложение в надежде получить более выгодное предложение позже. Это справедливо только тогда, когда для каждого покупателя пары покупатель-товар для этого покупателя заказываются в порядке убывания чистой полезности. Тогда покупателю всегда лучше принять первое предложение (если его чистая полезность положительна). Частным случаем такой ситуации является однопараметрическая установка: для каждого покупателя есть только одна пара покупатель-товар (например, есть один товар для продажи).

Каждой настройке с несколькими параметрами соответствует настройка с одним параметром, в которой каждая пара покупатель-товар считается независимым агентом. При настройке с одним параметром конкуренция выше (поскольку агенты одного и того же покупателя конкурируют друг с другом). Следовательно, доход BO в настройке с одним параметром является верхней границей дохода BO в настройке с несколькими параметрами. Следовательно, если OPM является р-приближение к оптимальному механизму для однопараметрической настройки, то это тоже р-приближение к соответствующей многопараметрической настройке.^[3] Видеть над для коэффициентов аппроксимации OPM в различных настройках.

См. Главу 7 «Многомерное приближение» в ^[9]:124 Больше подробностей.

Многие покупатели и продавцы, пользующиеся единичным спросом

Недавно схема SPM была расширена до двойной аукцион установка, где есть и покупатели, и продавцы. Расширенный механизм называется 2SPM. Он параметризован заказом покупателей, заказом продавцов и матрицей цен - ценой для каждой пары покупатель-продавец. Цены предлагаются покупателям и продавцам, которые могут принять или отклонить предложение. Коэффициент приближения составляет от 3 до 16, в зависимости от настройки.^[10]

Смотрите также

• Монопольное ценообразование

Рекомендации

1. Тим Рафгарден (2013). «Аукционы с максимальным доходом» (PDF). Получено 19 июля 2016.
2. Блюмрозен, Лиад; Холенштейн, Томас (2008). «Объявленные цены против переговоров». Материалы 9-й конференции ACM по электронной коммерции - EC '08. п. 49. CiteSeerX  10.1.1.221.9912. Дои:10.1145/1386790.1386801. ISBN  9781605581699.
3. Чавла, Шучи; Хартлайн, Джейсон Д .; Malec, David L .; Сиван, Баласубраманян (2010). «Разработка многопараметрического механизма и последовательное размещение цен». Материалы 42-го симпозиума ACM по теории вычислений - STOC '10. п. 311. arXiv:0907.2435. Дои:10.1145/1806689.1806733. ISBN  9781450300506.
4. Ausubel, Lawrence M .; Милгром, Пол (2005). "Прекрасный, но одинокий аукцион Викри". Комбинаторные аукционы. п. 17. Дои:10.7551 / mitpress / 9780262033428.003.0002. ISBN  9780262033428.
5. Кэтрин Холахан (3 июня 2008 г.). "Аукционы на eBay: умирающая порода". Получено 1 июля 2016.
6. Ян, Цици (2011). «Дизайн механизмов с помощью корреляционного разрыва». Материалы двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. п. 710. arXiv:1008.1843. Дои:10.1137/1.9781611973082.56. ISBN  978-0-89871-993-2.
7. Чавла, Шучи; Хартлайн, Джейсон Д .; Клейнберг, Роберт (2007). «Алгоритмическое ценообразование с помощью виртуальных оценок». Материалы 8-й конференции ACM по электронной коммерции - EC '07. п. 243. arXiv:0808.1671. Дои:10.1145/1250910.1250946. ISBN  9781595936530.
8. Единая цена не обязательно является оптимальной. Например, предположим, что есть два элемента, каждый со значением, независимо равным 1 с вероятностью 2/3 и 2 с вероятностью 1/3. Тогда векторы цен (1,2) и (2,1) являются оптимальными, но векторы цен (1,1) и (2,2) являются субоптимальными.
9. Джейсон Д. Хартлайн (2012). Приближение в экономическом дизайне (PDF).^{[постоянная мертвая ссылка ]}
10. Колини-Бальдески, Риккардо; Кейзер, Барт де; Леонарди, Стефано; Турчетта, Стефано (2016). «Приблизительно эффективные двойные аукционы с сильным бюджетным балансом». Материалы двадцать седьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. п. 1424. Дои:10.1137 / 1.9781611974331.ch98. ISBN  978-1-61197-433-1.