Байесово-оптимальное ценообразование

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

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

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

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

Rev(p)=p\cdot (1-F(p))

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

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

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

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

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

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

w(p^{*})=0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вероятность[оценка агента

j

по крайней мере

p_{j}

] =

C\times

Проблема [механизм БО обслуживает агента

j

].

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

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

Ограничения однородного матроида или матроида раздела - 2 (т. е. доход BO OPM составляет как минимум 1/2 дохода аукциона BO Майерсона).
графический матроид - 3
Пересечение двух матроидов разделов - 6,75
Пересечение графического матроида и матроида раздела - 10.66
Общий матроид с рангом матроида $k$ - $O(\log(k))$

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

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

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

Однородный матроид, матроид раздела - e/(e-1) ≅ 1,58
Общий матроид - 2
Пересечение двух матроидов - 3

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

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

Выручка аукциона БО не превышает $f(winners)\cdot Price$ , где «Победители» — это набор из k агентов с наивысшими оценками.
Доход БО СПУ составляет не менее $f(Demand)\cdot Price$ , где «Спрос» — множество агентов, оценка которых выше цены.

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

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

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

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

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

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

Доход от ценообразования на единицу спроса на BO при наличии $n$ Типы предметов — это не более чем доход аукциона отдельных предметов BO, когда есть $n$ потенциальные покупатели.
Когда оценки покупателя различных предметов независимы и основаны на одном и том же распределении, цена за единицу спроса БО, при которой используется одна и та же цена для всех предметов, достигает по крайней мере 1/2,17 дохода от аукциона по единичным предметам БО. ^[8]
Когда оценки покупателя независимы и основаны на различных распределениях, цена спроса на единицу продукции BO, в которой используется одна и та же виртуальная цена (основанная на виртуальных оценках ), достигает как минимум 1/3 дохода от аукциона единичных товаров BO.

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

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

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

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

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

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

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

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

См. главу 7 «Многомерная аппроксимация» в ^[9]^: 124 для более подробной информации.

Многие покупатели и продавцы единичного спроса

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

См. также

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

Ссылки

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

[r13-1] Тим Рафгарден (2013). «Аукционы, максимизирующие доход» (PDF) . Проверено 19 июля 2016 г.

[bh08-2] Jump up to: ^а ^б ^с Блюмрозен, Лиад; Холенштейн, Томас (2008). «Объявленные цены против переговоров». Материалы 9-й конференции ACM по электронной коммерции - EC '08 . п. 49. CiteSeerX 10.1.1.221.9912 . дои : 10.1145/1386790.1386801 . ISBN 9781605581699 .

[chms10-3] Jump up to: ^а ^б ^с ^д ^и Чавла, Сучи ; Хартлайн, Джейсон Д.; Малек, Дэвид Л.; Сиван, Баласубраманян (2010). «Проектирование многопараметрического механизма и последовательное размещение цен». Материалы 42-го симпозиума ACM по теории вычислений - STOC '10 . п. 311. arXiv : 0907.2435 . дои : 10.1145/1806689.1806733 . ISBN 9781450300506 .

[am06-4] Осубель, Лоуренс М.; Милгром, Пол (2005). «Милый, но одинокий аукцион Викри». Комбинаторные аукционы . п. 17. дои : 10.7551/mitpress/9780262033428.003.0002 . ISBN 9780262033428 .

[h08-5] Кэтрин Холахан (3 июня 2008 г.). «Аукционы на eBay: вымирающая порода» . Проверено 1 июля 2016 г.

[y10-6] Ян, Цици (2011). «Проектирование механизма с помощью корреляционного разрыва». Материалы двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . п. 710. arXiv : 1008.1843 . дои : 10.1137/1.9781611973082.56 . ISBN 978-0-89871-993-2 .

[chk07-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) субоптимальны.

[hartline12-9] Джейсон Д. Хартлайн (2012). Приближение в экономическом проектировании (PDF) . ^{[ постоянная мертвая ссылка ]}

[10] Колини-Бальдески, Риккардо; Кейзер, Барт де; Леонарди, Стефано; Турчетта, Стефано (2016). «Приблизительно эффективные двойные аукционы с сильным балансом бюджета». Материалы двадцать седьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . п. 1424. дои : 10.1137/1.9781611974331.ch98 . hdl : 11573/871600 . ISBN 978-1-61197-433-1 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]