Multiagent modeling of sequential multiunit japanese auctions

Features of modeling of auctions are investigated from the point of view of simulation (multiagent) modeling. The characteristic of auctions as object of modeling is resulted. Statement of a task carries out and the method of construction of the mechanism of carrying out of sequential multiunit japa...

Full description

Saved in:

Bibliographic Details
Date:	2018
Main Author:	Yalovets, A.L.
Format:	Article
Language:	Ukrainian
Published:	PROBLEMS IN PROGRAMMING 2018
Subjects:	modeling japanese auction mechanism design agent dominant strategies UDC 004.942+519.837.2
Online Access:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/173
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Problems in programming
Download file:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-173
record_format	ojs
resource_txt_mv	ppisoftskievua/00/b17466998b12ca3ebe9b9839dbe88c00.pdf
spelling	pp_isofts_kiev_ua-article-1732025-11-16T14:46:27Z Multiagent modeling of sequential multiunit japanese auctions Мультиагентное моделирование последовательных многоэлементных японских аукционов Мультиагентне моделювання послідовних багатоелементних японських аукціонів Yalovets, A.L. modeling; japanese auction; mechanism design; agent; dominant strategies UDC 004.942+519.837.2 моделирование; японский аукцион; дизайн механизма; агент; доминирующие стратегии УДК 004.942+519.837.2 моделювання; японський аукціон; дизайн механізму; агент; домінуючі стратегії УДК 004.942+519.837.2 Features of modeling of auctions are investigated from the point of view of simulation (multiagent) modeling. The characteristic of auctions as object of modeling is resulted. Statement of a task carries out and the method of construction of the mechanism of carrying out of sequential multiunit japanese auctions, which provides use by agents of dominant strategies is offered and allows to construct optimal auction. Efficiency of the suggested method experimentally proves to be true.Prombles in programming 2016; 1: 129-137 Исследуются особенности моделирования аукционов с точки зрения имитационного (мультиагентного) моделирования. Приводится характеристика аукционов как объекта моделирования. Выполняется постановка задачи и предлагается метод построения механизма проведения последовательных многоэлементных японских аукционов, который обеспечивает использование агентами доминирующих стратегий и позволяет построить оптимальный аукцион. Экспериментально подтверждается эффективность предложенного метода.Prombles in programming 2016; 1: 129-137 Досліджуються особливості моделювання аукціонів з точки зору імітаційного (мультиагентного) моделювання. Наводиться характеристика аукціонів як об’єкта моделювання. Виконується постановка задачі та пропонується метод побудови механізму проведення послідовних багатоелементних японських аукціонів, який забезпечує використання агентами домінуючих стратегій та дозволяє побудувати оптимальний аукціон. Експериментально підтверджується ефективність запропонованого метода.Prombles in programming 2016; 1: 129-137 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2018-11-21 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/173 10.15407/pp2016.01.129 PROBLEMS IN PROGRAMMING; No 1 (2016); 129-137 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2016); 129-137 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2016); 129-137 1727-4907 10.15407/pp2016.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/173/168 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-11-16T14:46:27Z
collection	OJS
language	Ukrainian
topic	modeling japanese auction mechanism design agent dominant strategies UDC 004.942+519.837.2
spellingShingle	modeling japanese auction mechanism design agent dominant strategies UDC 004.942+519.837.2 Yalovets, A.L. Multiagent modeling of sequential multiunit japanese auctions
topic_facet	modeling japanese auction mechanism design agent dominant strategies UDC 004.942+519.837.2 моделирование японский аукцион дизайн механизма агент доминирующие стратегии УДК 004.942+519.837.2 моделювання японський аукціон дизайн механізму агент домінуючі стратегії УДК 004.942+519.837.2
format	Article
author	Yalovets, A.L.
author_facet	Yalovets, A.L.
author_sort	Yalovets, A.L.
title	Multiagent modeling of sequential multiunit japanese auctions
title_short	Multiagent modeling of sequential multiunit japanese auctions
title_full	Multiagent modeling of sequential multiunit japanese auctions
title_fullStr	Multiagent modeling of sequential multiunit japanese auctions
title_full_unstemmed	Multiagent modeling of sequential multiunit japanese auctions
title_sort	multiagent modeling of sequential multiunit japanese auctions
title_alt	Мультиагентное моделирование последовательных многоэлементных японских аукционов Мультиагентне моделювання послідовних багатоелементних японських аукціонів
description	Features of modeling of auctions are investigated from the point of view of simulation (multiagent) modeling. The characteristic of auctions as object of modeling is resulted. Statement of a task carries out and the method of construction of the mechanism of carrying out of sequential multiunit japanese auctions, which provides use by agents of dominant strategies is offered and allows to construct optimal auction. Efficiency of the suggested method experimentally proves to be true.Prombles in programming 2016; 1: 129-137
publisher	PROBLEMS IN PROGRAMMING
publishDate	2018
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/173
work_keys_str_mv	AT yalovetsal multiagentmodelingofsequentialmultiunitjapaneseauctions AT yalovetsal mulʹtiagentnoemodelirovanieposledovatelʹnyhmnogoélementnyhâponskihaukcionov AT yalovetsal mulʹtiagentnemodelûvannâposlídovnihbagatoelementnihâponsʹkihaukcíonív
first_indexed	2025-11-17T02:17:40Z
last_indexed	2025-11-17T02:17:40Z
_version_	1849092708173348864
fulltext	Математичне моделювання об’єктів та процесів © А.Л. Яловець, 2016 ISSN 1727-4907. Проблеми програмування. 2016. № 1 129 УДК 004.942+519.837.2 А.Л. Яловець МУЛЬТИАГЕНТНЕ МОДЕЛЮВАННЯ ПОСЛІДОВНИХ БАГАТОЕЛЕМЕНТНИХ ЯПОНСЬКИХ АУКЦІОНІВ Досліджуються особливості моделювання аукціонів з точки зору імітаційного (мультиагентного) моде- лювання. Наводиться характеристика аукціонів як об’єкта моделювання. Виконується постановка зада- чі та пропонується метод побудови механізму проведення послідовних багатоелементних японських аукціонів, який забезпечує використання агентами домінуючих стратегій та дозволяє побудувати опти- мальний аукціон. Експериментально підтверджується ефективність запропонованого метода. Ключові слова: моделювання, японський аукціон, дизайн механізму, агент, домінуючі стратегії. Вступ Однією з актуальних проблем, що активно досліджується у світі, є моделю- вання аукціонів. Актуальність цього на- пряму досліджень є наслідком сучасних загальносвітових тенденцій. По-перше, з розвитком Інтернет-технологій з’явилися та поширилися різнорідні on-line аукціони (е-аукціони – наприклад, eBay.com, tcwc.com, iauction.com, klik-klok.com). По-друге, теорія аукціонів, як розділ тео- рії ігор, на сьогоднішній день дала по- штовх багатьом напрямам фундаменталь- них досліджень: від досліджень з розроб- ки методів цінового формування в різних галузях господарства (з урахуванням кон- куренції та монополізації ринків) до дос- ліджень, орієнтованих на нецінові про- блеми розподілу, які в тому числі вклю- чають і так звані «війни на виснаження», дослідження механізмів моделювання яких на сьогодні є вкрай важливим і для України. Зріст інтересу до цих проблем та- кож підтверджується множиною виданих за останні роки книг (наприклад, [1–7]), та присудженням Нобелевської премії з еко- номіки у 1996 та 2007 рр. за результати саме з галузі теорії аукціонів. Зазначимо, що в економіці теорія ігор вивчає функці- онування економічних систем за умов «недосконалого ринку» й ігрові моделі аукціонів, зокрема, є прикладами успіш- ного використання ігрового підходу в економіці. На сьогоднішній день у світі існує два домінуючих підходи щодо викори- стання мультиагентного підходу для моделювання аукціонів: моделювання е-аукціонів та моделювання переговорів у мультиагентних системах на основі аукці- онів. Якщо при моделюванні е-аукціонів [8], як правило, моделюється лише меха- нізм аукціону зі сторони аукціоніста (тоб- то дії покупців не моделюються, а реєст- руються як зовнішні дії), то при моделю- ванні переговорів на основі аукціонів [9, 10], в рамках яких агенти конкурують за ресурси або послуги, відбувається моде- лювання всіх учасників аукціону. Водно- час, незважаючи на існуючі досягнення, за межами досліджень, на наш погляд, за- лишається розгляд мультиагентного мо- делювання аукціонів з точки зору іміта- ційного моделювання динамічних систем. Пропонуванню одного з можливих підхо- дів до такого моделювання аукціонів і присвячено дану статтю. 1. Загальна характеристика аукціонів як об’єкта моделювання 1.1. Загальні відомості про аукці- они та їх сутність. Аукціон (від латинсь- кого auctio – продаж з публічного торгу) – це спосіб продажу деяких товарів за ціна- ми, що встановлюються покупцями за ре- зультатами торгів. Аукціон – це процеду- ра, за результатами якої приймається рі- шення про те, кому передати лот і скільки переможець має заплатити. Учасники по- відомляють про свою готовність платити і указане рішення приймається виключно на основі отриманих сигналів. Всі товари попередньо ділять на ло- ти (стандартні за кількістю та іншим озна- Математичне моделювання об’єктів та процесів 130 кам партії товарів). Лотом може бути і одиничний товар. Кожний лот має свій номер (ідентифікатор), під яким він пред- ставлений на торгах. Продавець в аукціонах може вста- новити резервну і початкову ціни. Резерв- на ціна характеризує цінність товару для продавця. Початкова ціна – це ціна, з якої починається торг. Якщо резервна ціна ого- лошується перед початком аукціону, вона стає початковою ціною. Якщо торги про- водяться з початкової ціни і заключна ціна (ціна продажу) становить значення, менше за резервну ціну, лот знімається з продажу. Організатор аукціону встановлює також крок торгів. Величину кроку торгів доці- льно ув’язувати з початковою ціною, оскі- льки при початковій ціні, близької до вар- тості об’єкта, та великим кроком торгів аукціон може виграти учасник з не самою високою оцінкою об’єкта. Розрізняють два основних критерії якості аукціонної процедури – ефектив- ність та оптимальність. Аукціон називають ефективним, якщо об’єкт достається учас- нику з найвищою оцінкою. Аукціон є оп- тимальним, якщо він максимізує очікува- ний прибуток продавця. 1.2. Типи аукціонів. Обґрунту- вання вибору досліджуваного типу аук- ціону. На сьогоднішній день відомі чотири основних типи аукціонів:  англійський аукціон (відкритий аукціон з підвищенням ціни). Цей тип аук- ціону здійснюється в реальному масштабі часу за безпосередньою участю гравців (усний аукціон) або інтерактивно у відда- леному доступі (за електронними торга- ми). При цьому аукціоніст виходить з ни- зької початкової ціни за лот (деякий товар) та поступово підвищує ціну, в процесі чого претенденти, не спроможні оплатити товар за поточною ціною торгів, вибивають, по- ки єдиний претендент не залишиться, який і виграє (придбає аукціонний товар) за ос- таточною ціною;  голландський аукціон (відкри- тий аукціон зі зниженням ціни). Цей тип аукціону також здійснюється в реальному масштабі часу, але, на відміну від англій- ського аукціону, аукціоніст починає з ви- сокої початкової ціни за лот та поступово знижує її до тих пір, доки деякий претен- дент не буде згоден оплатити ціну лота за поточною ціною торгів. Ця ціна і є остато- чною ціною торгів. Назва даного типу аук- ціону походить від аукціонів, що прово- дяться в Голландії при оптовій торгівлі квітами;  закритий аукціон першої ціни. При цьому типі аукціону кожний з претен- дентів одночасно подає аукціоністу «запе- чатану пропозицію» з вказівкою пропоно- ваної ціни за лот. В свою чергу, аукціоніст, одночасно відкриваючи наявні пропозиції, визначає покупця, яким виявляється той, хто запропонував найвищу ціну. Ця ціна і є остаточною ціною торгів;  закритий аукціон другої ціни (аукціон Вікрі). Цей тип аукціону подібний до аукціону першої ціни і переможцем то- ргів також вважається той покупець, який запропонував найвищу ціну за лот, але пе- реможець платить ціну, яка є другою най- вищою ціною зі всіх пропозицій, що на- дійшли. Даний тип аукціону названий у честь його автора, Нобелевського лауреата Вільяма Вікрі. Традиційно [1] при теоретичному дослідженні аукціонів розглядають різно- вид англійського аукціону, який назива- ється японським аукціоном, та полягає у тому, що ціна за лот підвищується безпе- рервно з постійним ціновим кроком тор- гів, і претенденти, які не спроможні опла- тити лот за поточною ціною, вибувають остаточно. Кожний з претендентів прий- має участь у торгах з початку торгів, жод- ний інший потенційний учасник не може увійти до торгів у процесі їх проведення; жодний претендент не може різко підви- щити ціну шляхом пропонування «підви- щеної ставки». Далі в наших досліджен- нях ми будемо розглядати саме японський аукціон. Для кожного з названих типів аук- ціону можуть існувати різні аспекти розг- ляду, пов’язані з особливостями проведен- ня аукціону. За цією ознакою аукціони можна розподілити на одноелементні (single-unit) та багатоелементні (multi-unit), де під одноелементними розуміються аук- ціони, на яких на протязі досліджуваного Математичне моделювання об’єктів та процесів 131 проміжку часу торгується один неподіль- ний лот (single indivisible unit); відповідно під багатоелементними – аукціони, на яких на протязі досліджуваного проміжку часу торгується багато неподільних лотів. За- значимо [1], що на сьогоднішній день пе- реважна більшість досліджень присвячена одноелементним та багатоелементним ау- кціонам для випадку, коли кожний поку- пець претендує лише на один лот з бага- тьох пропонованих. Для багатоелементного аукціону має значення організація процесу торгівлі. Відповідно до цього існують одночасні (simultaneous) та послідовні (sequential) багатоелементні аукціони, розбіжність між якими випливає з їх назв: якщо одночасні аукціони передбачають одночасний неза- лежний продаж m лотів на різних аукціо- нах, то послідовні аукціони передбачають продаж m лотів на аукціонах, які прово- дяться послідовно в часі (тобто послідовно проводиться m аукціонів). 1.3. Визначення основних власти- востей досліджуваних аукціонів як різ- новиду ігор. Визначимо властивості ігор, які ми будемо розглядати, виходячи з кла- сифікації ігор. Як відомо [11], ігри класи- фікуються наступним чином:  за кількістю гравців: ігри 1; 2; n гравців;  за кількістю стратегій: скінчен- ні та нескінченні ігри. Якщо у гравців скі- нченна кількість стратегій, то така гра є скінченною, в іншому випадку – нескін- ченною;  за характером взаємовідносин між гравцями: кооперативні та некоопера- тивні ігри. В кооперативній грі гравці мо- жуть заключати угоди з метою збільшення своїх виграшів, в некооперативній – ні;  за кількістю ходів: одноходові та багатоходові. Багатоходові поділяють- ся на: ─ позиційні, коли декілька грав- ців послідовно виконують ходи і виграш гравців залежить від стратегії вибору ходів (наприклад, шашки, шахи); ─ стохастичні, коли в грі є ходи, які виконуються випадковим чином та іс- нує ймовірність повернення на попередні позиції; ─ диференційні, коли ходи вико- нуються безперервно і поведінка гравців описується диференційними рівняннями.  за інформованістю гравців: ігри з досконалою та недосконалою інформаці- єю. У грі з досконалою інформацією на кожному кроці гравцям відомо, які ходи були зроблені раніше (наприклад, шашки, шахи). У грі з недосконалою інформацією гравці можуть не знати, в якій позиції вони знаходяться (що відповідає, наприклад, стохастичним іграм). До ігор з недоскона- лою інформацією зводяться ігри з непов- ною інформацією (також відомі як байє- совські ігри). На відміну від ігор з недос- коналою інформацією, де неповна інфор- мованість гравців виникає у процесі гри, в іграх з неповною інформацією неповна ін- формованість деяких гравців виникає ще до початку гри, як наслідок асиметричної інформованості гравців (наприклад, на ау- кціоні покупець знає про якість товару ме- нше, ніж продавець). Отже, ігри, на основі яких ми бу- демо досліджувати проблеми моделюван- ня аукціонів, мають наступні властивості: за кількістю гравців – n гравців; за кількі- стю стратегій – скінченні стратегії; за ха- рактером взаємовідносин між гравцями – некооперативні ігри; за кількістю ходів – багатоходові позиційні; за інформовані- стю гравців – ігри з досконалою та непов- ною інформацією (гравцям відомі попере- дні ходи, але невідомі майбутні ходи ані свої, ані чужі; жодний з гравців не має ін- формації про гроші, наявні в інших грав- ців, та про розподіл їх уподобань щодо товарів, які продаються на аукціоні). При моделюванні аукціонів також вирішується задача дизайну механізму («mechanism design») аукціону [7, 11, 12]. Дизайн механізму – це розділ теорії ігор, в якому вивчаються конфліктні ситуації з вираженою стратегічною поведінкою всіх гравців, щодо яких необхідно визначити правила прийняття рішень та здійснення платежів таким чином, щоби рівноважним став такий наслідок, в якому досягає сво- го максимуму деяка функція соціального вибору. Традиційно в основі дизайну ме- ханізму лежить принцип правдивості Математичне моделювання об’єктів та процесів 132 (truthfulness), який дозволяє обмежитись пошуком тільки такого механізму, який спонукає всіх гравців чесно повідомляти свої типи. Сутність задачі дизайну механізму полягає у наступному: необхідно побуду- вати механізм, в якому той чи інший рівноважний стан системи буде оптима- льним відносно тієї чи іншої мети. В зага- льному випадку у якості мети виступає функція соціального вибору, під якою розуміється функція OTTf n  ...: 1 , яка обирає той чи інший бажаний резуль- тат )(tf при даних типах ),...,( 1 nttt  гра- вців. Тобто функція соціального вибору – це те, що необхідно отримати від механі- зму, який розробляється. Але при цьому кожний гравець буде намагатися викорис- товувати домінуючі стратегії (тобто мак- симізувати власний прибуток), і ці зворо- тні задачі необхідно узгодити. Саме на рішення цієї задачі і націлене поняття ди- зайну механізму. 1.4. Деякі узагальнення. На основі викладеного можна зробити наступні ви- сновки щодо об’єкта моделювання: 1. Як об’єкт моделювання доціль- но вибрати послідовні багатоелементні японські аукціони, в яких кожний покупець може претендувати на k лотів, де mk 1 ; m – загальна кількість лотів (дорівнює кі- лькості аукціонів, що відбудуться). 2. Обраний тип аукціону з точки зору теорії ігор належить до класу некоо- перативних динамічних ігор з досконалою та неповною інформацією. 3. Будемо вважати принцип прав- дивості недіючим, оскільки в реальній дійсності гравці не надають жодної інфор- мації щодо свого типу. З цього випливає задача розробки дизайну механізму аукціо- ну та домінуючих стратегій для гравців (агентів), узгоджуваних з механізмом аук- ціону. 4. При формалізації типу гравця будемо виходити з припущення, що тип відповідає відношенню гравця до ризику. Відомо [12], що гравці (агенти) можуть мати три стани, що описують їх відношен- ня до ризику:  обережний (risk-averse), коли агент готовий заплатити за лот суму, стро- го меншу за ту, яку він запланував запла- тити;  нейтральний до ризику (risk- neutral), коли агент готовий заплатити за лот саме заплановану суму;  ризикований (risk-loving) або не нейтральний до ризику, коли агент готовий заплатити за лот суму, що перевищує за- плановану суму. Для цілей моделювання будемо вва- жати, що тип агента описується двома ста- нами щодо його відношення до ризику: {нейтральний до ризику, ризикований}. 2. Постановка задачі моделювання японського аукціону В пропонованій постановці будемо виходити з припущення, що розглядаються гравці (далі – агенти) одного типу (нейт- ральні до ризику). Будемо також вважати, що резервна та початкова ціни на будь- який лот збігаються. Задамо множини, які описують ос- новні вхідні параметри проведення послі- довного багатоелементного японського аукціону (далі – аукціону): },,1{ nN  – кінцева множина агентів, що приймають участь в аукціоні; },,1{ lL  – кінцева множина ло- тів, які торгуються на аукціоні; LKi  – кінцева множина лотів, у торгах щодо придбання яких приймає участь і-ий агент. Можливо, що  ni KK , де Nni , , ni  ; iR – ресурс (в загальному випадку в грошовому еквіваленті), наявний у і-го агента для придбання лотів множини iK ; )},(,),,{( 11 j i j iiii vkvkV  – кінцева множина пар, у кожній з яких подано пріоритет (суб’єктивна зважена оцінка цінності лота) j iv і-го агента щодо прид- бання відповідного j -го лота i j i Kk  , 10  j iv , 1 1   k j j iv , )( iKcardk  , Ni ; )},(,),,{( 11 mm cpcpU  – кінцева Математичне моделювання об’єктів та процесів 133 множина пар, в кожній з яких подано по- чаткову ціну jp та крок торгів jc щодо продажу відповідного j -го лота множини L (де кожному елементу множини U може бути зіставлений чітко визначений елемент множини L), )()( LcardUcard  . Під максимальним значенням ресу- рсу, виділеного і-им агентом на придбання j -го лота, будемо розуміти параметр j ii j i vRR  . Вважатимемо, що жодному агенту невідомі пріоритети та ресурси інших агентів та подальші дії як свої, так і інших агентів, але йому відомі власні пріоритети і ресурси та попередні дії як свої, так і інших агентів. Кожний агент також воло- діє інформацією про початкові (поточні) ціни на лоти та про учасників торгів і пе- релік лотів, що мають торгуватися на аук- ціоні. Виходячи з названих умов необ- хідно визначити домінуючі стратегії аген- тів та винайти дизайн механізму аукціон- них торгів. Як показано в п. 1.3, побудова механізму має узгоджуватись з викорис- товуваними агентами домінуючими стра- тегіями, в рамках яких кожний з агентів буде намагатися максимізувати власний прибуток. До того ж механізм має дозво- ляти формувати оптимальний аукціон. Для побудови механізму будемо та- кож виходити з наступних передумов: 1. Кожний і-ий агент, зареєстро- ваний як учасник торгів за j-ий лот, має прийняти в торгах фактичну участь та на- магатися зробити свою останню пропози- цію в момент часу t проведення аукціону, коли виконується одна з двох умов: )()( 1tzRctz j j ijj  або j iej Rtz )( (якщо j iej Rtz )( ), де )(tz j – значення ціни за j -ий лот в момент часу t прове- дення аукціону; )( 1tz j – значення ціни за j -ий лот у момент часу 1t , в який була по- дана наступна пропозиція після пропози- ції, що надійшла в момент часу t ; )( ej tz – значення ціни за j -ий лот у момент часу et завершення торгів (ціна, яку платить переможець); jc – крок торгів за j -ий лот; j iR – максимальне значення ресурсу, ви- ділене на придбання j -го лоту будь-яким не і-им агентом, що приймає участь в аук- ціоні. 2. Агенти, які мають більші ресу- рси на лот, вступають у аукціон пізніше, ніж інші агенти. Перша передумова зумовлює необ- хідність автоматичного формування домі- нуючих стратегій агентів у рамках викори- стовуваного механізму проведення аукціо- ну. Друга передумова узагальнює практи- чний досвід проведення аукціонів [6] та впливає на визначення порядку участі аге- нтів в аукціонних торгах. Зауважимо, що прибуток перемож- ця ( i -го агента) в придбанні j -го лота ви- значатиметься як )( ej j i tzR  , а прибуток продавця – як jej ptz )( , де jp – резерв- на (у нас, як показано вище, вона збігаєть- ся з початковою) ціна за j -ий лот. Як наслідок, при побудові механіз- му необхідно вирішити наступну задачу оптимізації (при цьому мають виконува- тись вищезазначені передумови 1, 2): .max)( max,)(   jej ej j i ptz tzR (1) Слід зауважити, що переможець за- цікавлений у мінімізації )( ej tz , а прода- вець, навпаки – в максимізації )( ej tz . Тоб- то побудований механізм має забезпечува- ти врівноваження між цими суперечними намірами учасників аукціону. 3. Метод побудови механізму проведення аукціону Виходячи з наведеної постановки задачі розроблено метод побудови меха- нізму проведення аукціону, який ґрунту- ється на наступних поняттях: мотивація агента, коефіцієнт впевненості агента і коефіцієнт пасивності участі агента в аукціоні. Будемо називати мотивацією і-го агента щодо придбання j -го лота пара- Математичне моделювання об’єктів та процесів 134 метр j iM , що є часткою пріоритету агента щодо j -го лота за відношенням до інших пріоритетів агента: j i j ij i v v M   1 . Цей параметр може тлумачитися як суб’єктивний рівень зацікавленості і-го агента в придбанні j -го лота і є незмінним на всьому протязі торгів за j -ий лот. Як- що 1 j iv (тобто коли 1)( iKcard ), j iM присвоюється значення 1.0. Під коефіцієнтом впевненості і-го агента щодо придбання j -го лота в момент часу t будемо розуміти пара- метр )(tkv j i , який визначається наступним чином: j i j j ij i R tzR tkv )( )(   , де )(tz j – значення ціни за j -ий лот у момент часу t проведення аукціону. Кое- фіцієнт впевненості може тлумачитися як міра спокою і-го агента у момент часу t щодо можливості придбання j -го лота (зі зростом t параметр )(tkv j i зменшується; 1)(0  tkv j i ). У випадку, коли 0)( tkv j i , участь і-го агента в подальшо- му аукціоні щодо придбання j -го лота неможлива (у зв’язку з закінченням ресу- рсу і-го агента). Під коефіцієнтом пасивності участі і-го агента у торгах за j -ий лот у момент часу t будемо розуміти параметр )(tkp j i , який визначається як )()( tkvMtkp j i j i j i  . Коефіцієнт пасивно- сті участі і-го агента може тлумачитись як ступінь його активності щодо придбан- ня j -го лота в момент часу t проведення аукціону; 1)(0  tkp j i . Чим менший цей коефіцієнт, тим вища активність і-го аген- та в аукціоні і тим сильніше його намаган- ня зробити ставку в момент часу t прове- дення аукціону. Метод побудови механізму прове- дення аукціону ґрунтується на визначенні коефіцієнтів пасивності участі для кожно- го агента, який не вибув з аукціону в кож- ний момент виконання ставок за лот та порівнянні значень двох найменших кое- фіцієнтів. Якщо агент, що має найменший коефіцієнт з порівнянних, останнім робив ставку, то обирається інший агент з на- ступним найменшим коефіцієнтом, який і робить ставку за лот. В іншому випадку для виконання ставки обирається агент з найменшим коефіцієнтом. 4. Імітаційне моделювання послідовного багатоелементного японського аукціону Запропонований метод побудови механізму моделювання аукціону реалізо- вано в прототипі мультиагентної системи (МАС) «Аукціонъ». Для реалізації вико- ристано мову логічного програмування PDC Visual Prolog з міркувань необхідно- сті вести і обробляти БД аукціону (Prolog є реляційною мовою) та можливості засо- бами мови описувати логіку поведінки агентів. Засобами МАС «Аукціонъ» забез- печується як процес формування і перег- ляду даних про агентів та про пропоновані лоти, так і власно виконання моделювання аукціону (див. рисунок) на створених та збережених даних. Розглянемо результати мульти- агентного моделювання послідовного ба- гатоелементного японського аукціону (див. таблицю), виконаного засобами МАС «Аукціонъ» на прикладі вхідних да- них, наведених далі, та покажемо, що в рамках запропонованого механізму забез- печується підтримка домінуючих страте- гій агентами та вирішується задача опти- мізації (1). Вхідні дані аукціону: Дані про лоти: Лот 1: початкова ціна – 100; крок торгів – 10; учасники: Агент 1, Агент 2, Агент 3, Агент 4, Агент 6. Лот 2: початкова ціна – 200; крок торгів – 20; учасники: Агент 2, Агент 3, Агент 5. Математичне моделювання об’єктів та процесів 135 Рисунок. Інтерфейс процесу мультиагентного моделювання японського аукціону Лот 3: початкова ціна – 300; крок торгів – 30; учасники: Агент 1, Агент 3, Агент 4, Агент 5, Агент 6. Лот 4: початкова ціна – 400; крок торгів – 40; учасники: Агент 1, Агент 2, Агент 3, Агент 4, Агент 5, Агент 6. Дані про агентів: Агент 1: Ресурс – 6700; розподіл пріоритетів: Лот 1 – 0.3, Лот 3 – 0.4, Лот 4 – 0.3. Агент 2: Ресурс – 3000; розподіл пріоритетів: Лот 1 – 0.4, Лот 2 – 0.35, Лот 4 – 0.25. Агент 3: Ресурс – 9000; розподіл пріоритетів: Лот 1 – 0.33, Лот 2 – 0.27, Лот 3 – 0.25, Лот 4 – 0.15. Агент 4: Ресурс – 10500; розподіл пріоритетів: Лот 1 – 0.15, Лот 3 – 0.5, Лот 4 – 0.35. Агент 5: Ресурс – 8790; розподіл пріоритетів: Лот 2 – 0.45, Лот 3 – 0.25, Лот 4 – 0.3. Агент 6: Ресурс – 6770; розподіл пріоритетів: Лот 1 – 0.35, Лот 3 – 0.45, Лот 4 – 0.2. З таблиці випливає, що стратегії агентів, забезпечувані запропонованим ме- ханізмом проведення аукціону, є доміную- чими, оскільки вони дозволяють максимі- зувати прибуток (для переможця) або на- давати максимально можливу (або близьку до неї) пропозицію (для агентів, що вибули з аукціону). Крім того, запропонований механізм дозволяє реалізувати оптималь- ний аукціон, оскільки він максимізує при- буток продавця. Так, у всіх випадках пе- реможець (і-ий агент) придбав лот за най- нижчою можливою ціною (більшою за по- передню ціну за j-ий лот лише на значення одного кроку торгів), а продавець продав лот за максимально можливу ціну, яка від- повідає вимозі передумови 1 (див. п. 2): j iej Rtz )( , де j iej Rtz )( . Очевидно та- кож, що запропонований механізм задово- льняє умовам (1). Математичне моделювання об’єктів та процесів 136 Таблиця. Результати моделювання послідовного багатоелементного японського аукціону Агенти Дані по лоту Агент 1 Агент 2 Агент 3 Агент 4 Агент 5 Агент 6 Л о т 1 Максимальна кіль- кість ресурсів на лот 2010 1200 2970 1575 – 2369.5 Максимальна ставка, зроблена агентом 2010 1190 2370 1560 – 2360 Порядок вибуття аге- нтів з торгів 3 1 5 2 – 4 Отриманий прибуток – – 600 – – – Л о т 2 Максимальна кіль- кість ресурсів на лот – 1050 2430 – 3955.5 – Максимальна ставка, зроблена агентом – 1020 2400 – 2420 – Порядок вибуття аге- нтів з торгів – 1 2 – 3 – Отриманий прибуток – – – – 1535.5 – Л о т 3 Максимальна кіль- кість ресурсів на лот 2680 – 2250 5250 2197.5 3046.5 Максимальна ставка, зроблена агентом 2640 – 2250 3060 2160 3030 Порядок вибуття аге- нтів з торгів 3 – 2 5 1 4 Отриманий прибуток – – – 2190 – – Л о т 4 Максимальна кіль- кість ресурсів на лот 2010 750 1350 3675 2637 1354 Максимальна ставка, зроблена агентом 2000 680 1280 2640 2600 1320 Порядок вибуття з торгів 4 1 2 6 5 3 Отриманий прибуток – – – 1035 – – Висновки В статті як приклад некооператив- них динамічних ігор з досконалою та неповною інформацією розглянуто послі- довні багатоелементні японські аукціони, для яких поставлено та вирішено задачу побудови механізму проведення аукціо- нів, який узгоджує у собі використання агентами їх домінуючих стратегій та дозволяє сформувати оптимальний аукці- он. Розроблені методи реалізовано в прототипі МАС «Аукціонъ». Виходячи з аналізу сучасного стану досліджень тео- рії аукціонів можна стверджувати, що запропонований підхід до мультиагент- ного моделювання аукціонів є новим, а розроблений метод побудови механізму проведення аукціонів створює передумо- ви для подальших досліджень у напрямку розробки методів незалежного формуван- ня агентами домінуючих стратегій у рамках такого механізму, що в перспек- тиві дозволить формулювати та вирішува- ти задачі моделювання одночасних бага- тоелементних аукціонів як основи для моделювання війн на виснаження для за- гального випадку. 1. Klemperer P. Auctions: Theory and Practice. – Princeton University Press, 2004. – 239 p. Математичне моделювання об’єктів та процесів 137 2. Krishna V. Auction Theory. – Elsevier Inc., 2010. – 323 p. 3. Lusk J.L., Shogren J.F. Experimental Auc- tions. Methods and Applications in Economic and Marketing Research. – Cambridge Uni- versity Press, 2007. – 304 p. 4. Menezes F.M., Monteiro P.K. An Introduc- tion to Auction Theory. – Oxford University Press, 2008. – 184 p. 5. Milgrom P. Putting Auction Theory to Work. – Cambridge University Press, 2004. – 368 p. 6. Mochón A., Sáez Y. Understanding Auctions. – Springer, 2015. – 148 p. 7. Multiagent Systems: Algorithmic, Game- Theoretic, and Logical Foundations/ Shoham Y., Leyton-Brown K. – Cambridge Universi- ty Press, 2008. – 532 p. 8. Jureta I., Kolp M., Faulkner S. Multi-Agent Patterns for Deploying Online Auctions // Selected readings on electronic commerce technologies: contemporary applications / Edited by Hu W.-Ch. – IGI Global, 2009. – P. 130–146. 9. Filzmoser M. Simulation of Automated Negotiation. – Springer-Verlag, 2010. – 248 p. 10. Sierra C., Noriega P. Agent-Mediated Inter- action. From Auctions to Negotiation and Argumentation // Foundations and Applica- tions of Multi-Agent Systems (UKMAS Workshops 1996–2000 Selected Papers). – Springer-Verlag, 2002. – P. 27–48. 11. Писарук Н.Н. Введение в теорию игр. – Минск: БГУ, 2015. – 256 с. 12. Николенко С.И. Теория экономических механизмов. – М.: БИНОМ, 2009. – 207 с. References 1. Klemperer P. Auctions: Theory and Practice. – Princeton University Press, 2004. – 239 p. 2. Krishna V. Auction Theory. – Elsevier Inc., 2010. – 323 p. 3. Lusk J.L., Shogren J.F. Experimental Auctions. Methods and Applications in Economic and Marketing Research. – Cambridge University Press, 2007. – 304 p. 4. Menezes F.M., Monteiro P.K. An Intro- duction to Auction Theory. – Oxford University Press, 2008. – 184 p. 5. Milgrom P. Putting Auction Theory to Work. – Cambridge University Press, 2004. – 368 p. 6. Mochón A., Sáez Y. Understanding Auctions. – Springer, 2015. – 148 p. 7. Multiagent Systems: Algorithmic, Game- Theoretic, and Logical Foundations/ Shoham Y., Leyton-Brown K. – Cambridge University Press, 2008. – 532 p. 8. Jureta I., Kolp M., Faulkner S. Multi-Agent Patterns for Deploying Online Auctions // Selected readings on electronic commerce technologies: contemporary applications / Edited by Hu W.-Ch. – IGI Global, 2009. – P. 130–146. 9. Filzmoser M. Simulation of Automated Negotiation. – Springer-Verlag, 2010. – 248 p. 10. Sierra C., Noriega P. Agent-Mediated Interaction. From Auctions to Negotiation and Argumentation // Foundations and Applications of Multi-Agent Systems (UKMAS Workshops 1996-2000 Selected Papers). – Springer-Verlag, 2002. – P. 27–48. 11. Pisaruk N.N. Introduction to Game Theory. – Minsk: BGU, 2015. – 256 p. (in Russian). 12. Nikolenko S.I. Theory of Economical Mechanisms. – Moscow: BINOM, 2009. – 207 p. (in Russian). Одержано 11.01.2016 Про автора: Яловець Андрій Леонідович, доктор технічних наук, заступник директора інституту. Кількість наукових публікацій в українських виданнях – 100. Кількість наукових публікацій в іноземних виданнях – 5. http://orcid.org/0000-0001-6542-3483 Місце роботи автора: Інститут програмних систем НАН України. 03187, Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 526 15 38. E-mail: yal@isofts.kiev.ua mailto:yal@isofts.kiev.ua

Multiagent modeling of sequential multiunit japanese auctions

Institution

Similar Items