Бюджетно-аддитивная оценка - Википедия - Budget-additive valuation

В экономика, а бюджетно-аддитивная оценка это своего рода вспомогательная функция. Это соответствует человеку, который, получив набор предметов, оценивает их следующим образом:[1]

  • По каждому пункту j, есть фиксированное значение vj.
  • Также есть фиксированный бюджет B.
  • Значение набора элементов - это минимум между B и суммой значений элементов в наборе.

Бюджетно-аддитивные оценки полезны при исследовании он-лайн реклама,[2][3][4] комбинаторные аукционы,[5][6] распределение ресурсов,[7][8][9][10][11] и рыночное равновесие.[12][13][14][15]

Отношение к другим видам оценок

Каждый аддитивная оценка представляет собой частный случай оценки с добавлением бюджета, в которой бюджет бесконечен. Каждая оценка с добавлением бюджета - это субмодульная оценка.

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

  1. ^ Гарг, Джугал; Хофер, Мартин; Мельхорн, Курт (январь 2018 г.), «Приближение социального благосостояния по Нэшу с помощью бюджетных оценок», Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, Общество промышленной и прикладной математики, стр. 2326–2340, Дои:10.1137/1.9781611975031.150, ISBN  978-1-61197-503-1, S2CID  1282865
  2. ^ Мехта, Араньяк (2013-10-16). «Онлайн-сопоставление и размещение рекламы». Основы и тенденции теоретической информатики. 8 (4): 265–368. Дои:10.1561/0400000057. ISSN  1551-305X.
  3. ^ Мехта, Араньяк; Сабери, Амин; Вазирани, Умеш; Вазирани, Виджай (01.10.2007). "AdWords и обобщенное соответствие в Интернете". Журнал ACM. 54 (5): 22 – es. Дои:10.1145/1284320.1284321. ISSN  0004-5411.
  4. ^ Бухбиндер, Нив; Джайн, Камаль; Наор, Иосиф (Сеффи), «Онлайн-алгоритмы Primal-Dual для максимизации дохода от рекламных аукционов», Алгоритмы - ESA 2007, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 253–264, ISBN  978-3-540-75519-7, получено 2020-09-03
  5. ^ Анделман, Нир; Мансур, Ишай (2004). Хагеруп, Торбен; Катаянен, Юрки (ред.). «Аукционы с ограничениями бюджета». Теория алгоритмов - SWAT 2004. Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 26–38. Дои:10.1007/978-3-540-27810-8_4. ISBN  978-3-540-27810-8.
  6. ^ Бухфюрер, Дэйв; Дугми, Шаддин; Фу, Ху; Клейнберг, Роберт; Моссель, Эльханан; Пападимитриу, Христос; Шапира, Майкл; Певец Ярон; Уманс, Крис (17 января 2010 г.), «Неприближаемость для комбинаторных аукционов на основе VCG», Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2010 г., Proceedings, Society for Industrial and Applied Mathematics, pp. 518–536, Дои:10.1137/1.9781611973075.45, ISBN  978-0-89871-701-3, получено 2020-09-03
  7. ^ Азар, Йоси; Бирнбаум, Бенджамин; Карлин, Анна Р .; Матье, Клэр; Нгуен, К. Тач (2008). Ацето, Лука; Дамгард, Иван; Голдберг, Лесли Энн; Halldórsson, Magnús M .; Ингольфсдоттир, Анна; Валукевич, Игорь (ред.). «Улучшенные алгоритмы аппроксимации для бюджетных ассигнований». Автоматы, языки и программирование. Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 186–197. Дои:10.1007/978-3-540-70575-8_16. ISBN  978-3-540-70575-8.
  8. ^ Чакрабарти, Дипарнаб; Гоэль, Гаган (01.10.2008). «О приближаемости бюджетных ассигнований и улучшенных нижних границах для субмодульной максимизации благосостояния и разрыва». 2008 49-й ежегодный симпозиум IEEE по основам компьютерных наук. IEEE. Дои:10.1109 / focs.2008.47. ISBN  978-0-7695-3436-7.
  9. ^ Калайцис, Христос (21 декабря 2015 г.). «Гарантия улучшенной аппроксимации для задачи о максимальном распределении бюджетных средств». Материалы двадцать седьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. Дои:10.1137 / 1.9781611974331.ch74. ISBN  978-1-61197-433-1.
  10. ^ Шринивасан, Аравинд (2008). Гоэль, Ашиш; Янсен, Клаус; Rolim, José D. P .; Рубинфельд, Ронитт (ред.). «Бюджетные ассигнования в условиях полной информации». Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы. Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 247–253. Дои:10.1007/978-3-540-85363-3_20. ISBN  978-3-540-85363-3.
  11. ^ Деванур, Нихил Р .; Джайн, Камаль; Сиван, Баласубраманян; Уилкенс, Кристофер А. (12 января 2019 г.). «Практически оптимальные онлайн-алгоритмы и алгоритмы быстрого приближения для задач распределения ресурсов». Журнал ACM. 66 (1): 1–41. Дои:10.1145/3284177. ISSN  0004-5411.
  12. ^ Фельдман, Михал; Гравин, Ник; Люсьер, Брендан (01.01.2016). «Комбинаторное вальрасово равновесие». SIAM Журнал по вычислениям. 45 (1): 29–48. Дои:10.1137 / 13094339X. ISSN  0097-5397.
  13. ^ Roughgarden, Тим; Талгам-Коэн, Инбал (15.06.2015). «Зачем ценам нужны алгоритмы». Труды шестнадцатой конференции ACM по экономике и вычислениям. EC '15. Портленд, Орегон, США: Ассоциация вычислительной техники: 19–36. Дои:10.1145/2764468.2764515. ISBN  978-1-4503-3410-5.
  14. ^ Гарг, Джугал; Хофер, Мартин; Бэй, Сяохуэй; Мельхорн, Курт (2016). «Вычисление равновесия на рынках с дополнительными бюджетами коммунальных услуг». Дои:10.4230 / LIPIcs.ESA.2016.8. Цитировать журнал требует | журнал = (помощь)
  15. ^ Коул, Ричард; Деванур, Нихил; Гкацелис, Василис; Джайн, Камаль; Май, Тунг; Вазирани, Виджай В .; Язданбод, Садра (20.06.2017). «Выпуклая двойственность программ, рынки Фишера и социальное обеспечение Нэша». Труды конференции ACM по экономике и вычислениям 2017 г.. Нью-Йорк, Нью-Йорк, США: ACM. Дои:10.1145/3033274.3085109. ISBN  978-1-4503-4527-9.

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