Аукцион в долларах

Аукцион в долларах - игра без нуля, впервые представленная Мартином Шубиком в 1971 году. В игре игроки выставляют ставки на купюру в один доллар. После того, как игрок делает ставку, каждый другой игрок может принять решение сделать ставку выше, чем предыдущий участник. Аукцион заканчивается, когда больше никто из игроков не решает сделать ставку. Самый высокий претендент получает одну долларовую купюру, однако, в отличие от типичного аукциона, как самый высокий, так и второй по величине претендент отдают свою ставку аукционеру.

Стохастическая модель

Можно смоделировать игры, подобные долларовому аукциону, используя стохастическую модель. Состояние (текущая ставка и количество активных игроков) может быть смоделировано с помощью марковских процессов, и поэтому можно ожидать, что результаты ( рыночное значение) будут иметь четко определенную статистику. Результаты получены из условного распределения, и поэтому долларовый аукцион идеально подходит для анализа Монте-Карло. На рыночное значение влияют следующие факторы:

В этом примере следующий алгоритм определяет, какие действия принимают игроки (торги или выбытие) в зависимости от состояния.

Вспомогательная функция dollarAuction моделирует аукцион в долларах. Для просмотра кода смотрите dollarAuction.m. Функция принимает три входов: nPlayers, incr, и dropoutRate. Установите каждое из значений.

nPlayers = 20;
incr = 0.05;
dropoutRate = 0.01;

Запустите случайный сценарий путем выполнения dollarAuction функция. Сохраните выходы bids и dropouts.

[bids,dropouts] = dollarAuction(nPlayers,incr,dropoutRate);

Когда игра продолжается, некоторые игроки размещают заявки, а некоторые выбывают. Если ставка превышает 1, игроки блокируются в «войне торгов», пока не останется только один игрок.

Таблица dropouts содержит две переменные: Player, уникальный номер, присвоенный каждому игроку; Epoch, раунд торгов, когда Player выпал. Использование findgroups для группирования dropouts.Epoch, и использовать splitapply чтобы получить количество игроков, которые выбывают в каждом из уникальных раундов в dropouts.Epoch.

[G,epochs] = findgroups(dropouts.Epoch);
numberDropouts = splitapply(@numel,dropouts.Epoch,G);

Изначально отсева нет. Добавить эту информацию в epochs и numberDropouts путем предварительной обработки 1 и 0.

epochs = [1;epochs];
numberDropouts = [0;numberDropouts];

Использование nPlayers и cumsum вычислить количество игроков, оставшихся от numberDropouts. Рассчитать ставки можно используя incr и epochs. Использование stairs для построения графика предложения с учетом совокупной суммы numberDropouts.

playersRemaining = nPlayers - cumsum(numberDropouts);
stairs(incr*epochs,playersRemaining)
xlabel('Bid')
ylabel('Number of players remaining')

Оценка рыночного значения с использованием методов Монте-Карло

Можно оценить рыночную стоимость счета-фактуры со значением origValue при помощи методов Монте-Карло. Здесь вы производите модель Monte-Carlo и сравниваете скорость с и без Parallel Computing Toolbox. Установите количество испытаний nTrials используется для случайной выборки результатов.

nTrials = 10000;

Можно выборить возможные результаты путем выполнения вспомогательной функции dollarAuction несколько раз. Использование for-цикл для производства nTrials выборки, хранящие последнюю ставку из каждого испытания в B. Каждый раз, когда вы запускаете dollarAuction функция, вы получаете различные результаты. Однако, когда вы запускаете функцию много раз, результаты, которые вы получаете из всех запусков, будут иметь четко определенную статистику.

Запишите время, необходимое для вычисления nTrials симуляции. Чтобы уменьшить статистический шум за истекшее время, повторите этот процесс пять раз, затем возьмите минимальное истекшее время.

t = zeros(1,5);
for j = 1:5
    tic
    B = zeros(1,nTrials);
    for i = 1:nTrials
        bids = dollarAuction(nPlayers,incr,dropoutRate);
        B(i) = bids.Bid(end);
    end
    t(j) = toc;
end
forTime = min(t)

forTime = 21.4323

Использование histogram для построения гистограммы окончательных предложений B. Использование xline наложение графика на исходное значение (один доллар) и среднюю рыночную стоимость, заданную mean.

histogram(B);
origLine = xline(1,'k','LineWidth',3);
marketLine = xline(mean(B),'k--','LineWidth',3);
xlabel('Market value')
ylabel('Frequency')
legend([origLine, marketLine],{'Original value','Market value'},'Location','NorthEast')

При заданных алгоритме и входных параметрах средняя рыночная стоимость больше исходного значения.

Использование parfor-цикл для оценки рыночного значения

Вы можете использовать Parallel Computing Toolbox, чтобы легко ускорить код Монте-Карло. Сначала создайте параллельный пул с четырьмя рабочими, использующими 'local' профиль.

p = parpool('local',4);

Starting parallel pool (parpool) using the 'local' profile ...
Connected to the parallel pool (number of workers: 4).

Замените for-цикл с parfor-цикл. Запишите время, необходимое для вычисления nTrials симуляции. Чтобы уменьшить статистический шум за истекшее время, повторите этот процесс 5 раз, затем возьмите минимальное истекшее время.

t = zeros(1,5);
for j = 1:5
    tic
    parfor i = 1:nTrials
        bids = dollarAuction(nPlayers,incr,dropoutRate);
        B(i) = bids.Bid(end);
    end
    t(j) = toc;
end
parforTime = min(t)

parforTime = 5.9174

С четырьмя рабочими результаты указывают, что код может запускаться в три раза быстрее, когда вы используете parfor-цикл.

Получите воспроизводимые результаты со случайными числами в parfor- циклы

Когда вы генерируете случайные числа в parfor-loop, каждый запуск цикла может привести к различным результатам. Чтобы создать воспроизводимые результаты, каждая итерация цикла должна иметь детерминированное состояние для генератора случайных чисел. Для получения дополнительной информации см. Раздел «Повторение случайных чисел в циклах parfor».

Вспомогательная функция dollarAuctionStream принимает четвертый аргумент, s. Эта поддерживающая функция использует указанный поток, чтобы получить случайные числа. Для просмотра кода смотрите dollarAuctionStream.m.

Когда вы создаете поток, субпотоки этого потока являются статистически независимыми. Для получения дополнительной информации смотрите RandStream. Чтобы убедиться, что ваш код каждый раз производит одинаковое распределение результатов, создайте поток генератора случайных чисел в каждой итерации цикла, затем установите Substream свойство индексу цикла. Замените dollarAuction с dollarAuctionStream, затем используйте s чтобы запустить dollarAuctionStream на работника.

Запишите время, необходимое для вычисления nTrials симуляции. Чтобы уменьшить статистический шум за истекшее время, повторите этот процесс пять раз, затем возьмите минимальное истекшее время.

t = zeros(1,5);
for j = 1:5
    tic
    parfor i = 1:nTrials
        s = RandStream('Threefry');
        s.Substream = i;
        bids = dollarAuctionStream(nPlayers,incr,dropoutRate,s);
        B(i) = bids.Bid(end);
    end
    t(j) = toc;
end
parforTime = min(t)

parforTime = 8.7355

Масштабирование с рабочего стола на кластер

Вы можете масштабировать свой код от рабочего стола до кластера с большим количеством работников. Дополнительные сведения о масштабировании с рабочего стола на кластер см. в разделе Шкале с рабочего стола на кластер.

Использование delete для завершения работы существующего параллельного пула.

delete(p);

Вычислите вспомогательную функцию dollarAuctionStream в parfor-цикл. Запустите ту же parfor-цикл с различными числами работников и запись истекшего времени. Чтобы уменьшить статистический шум за истекшее время, запустите parfor-цикл пять раз, затем взять минимальное истекшее время. Запишите минимальное время в массиве elapsedTimes. В следующем коде замените MyCluster с именем профиля кластера.

workers = [1 2 4 8 16 32];
elapsedTimes = zeros(1,numel(workers));

% Create a pool using the 'MyCluster' cluster profile
p = parpool('MyCluster', 32);

Starting parallel pool (parpool) using the 'MyCluster' profile ...
Connected to the parallel pool (number of workers: 32).

for k = 1:numel(workers)    
    t = zeros(1,5);
    for j = 1:5
        tic
        parfor (i = 1:nTrials, workers(k))
            s = RandStream('Threefry');
            s.Substream = i;
            bids = dollarAuctionStream(nPlayers,incr,dropoutRate,s);
            B(i) = bids.Bid(end);
        end
        t(j) = toc;
    end
    
    elapsedTimes(k) = min(t);
end

Analyzing and transferring files to the workers ...done.

Вычислите вычислительное ускорение путем деления elapsedTimes(1) по временам в elapsedTimes. Исследуйте сильное масштабирование путем построения графика скорости относительно количества работников.

speedup = elapsedTimes(1) ./ elapsedTimes;
plot(workers,speedup)
xlabel('Number of workers')
ylabel('Computational speedup')

Вычислительная скорость увеличивается с количеством работников.