D 2018

Combinatorial Auctions and Duality Theory

MAJOVSKÁ, Renata and Petr FIALA

Basic information

Original name

Combinatorial Auctions and Duality Theory

Authors

MAJOVSKÁ, Renata (203 Czech Republic, guarantor, belonging to the institution) and Petr FIALA (203 Czech Republic)

Edition

1. vyd. Bratislava, QUANTITATIVE METHODS IN ECONOMICS Multiple Criteria Decision Making XIX, p. 223-229, 7 pp. 2018

Publisher

University of Economics, Bratislava

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

50204 Business and management

Country of publisher

Slovakia

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

References:

Sborník z konference

RIV identification code

RIV/04274644:_____/18:#0000367

Organization unit

University of Finance and Administration

ISBN

978-80-89962-07-5

UT WoS

000455265500029

Keywords (in Czech)

combinatorial auction; duality theory; iterative approach; primal-dual algorithm;

Keywords in English

combinatorial auction; duality theory; iterative approach; primal-dual algorithm;

Tags

AR 2018-2019, cervenec_2019_o, RIV_2019, WOS, xD1_překvalifikování, xD2

Tags

International impact, Reviewed
Změněno: 22/3/2019 10:33, Ing. Dominika Moravcová

Abstract

ORIG CZ

V originále

Combinatorial auctions are those auctions in which bidders can place bids on combinations of items. Solving of combinatorial auctions can be modeled by linear programming problems with using of duality theory. The paper is devoted to analyzing an iterative approach to solving combinatorial auctions. In the iterative approach, there are multiple rounds of bidding and allocation and the problem is solved in an iterative and incremental way. There is a connection between efficient auctions and duality theory. The primal-dual algorithm can be taken as a decentralized and dynamic method of determine the pricing equilibrium. A primaldual algorithm usually maintains a feasible dual solution and tries to compute a primal solution that is both feasible and satisfies the complementary slackness conditions. If such a solution is found, the algorithm terminates. Otherwise the dual solution is updated towards optimality and the algorithm continues with the next iteration. Several auction formats based on the primal-dual approach have been proposed.

In Czech

Kombinované aukce jsou aukce, ve kterých mohou uchazeči zadávat nabídky na kombinace položek. Řešení kombinačních aukcí lze modelovat pomocí lineárních programovacích problémů s využitím teorie duality. Příspěvek je věnován analýze iterativního přístupu k řešení kombinatorických aukcí. V iterativním přístupu existuje více kol nabízení a přidělování a problém je řešen iterativním a inkrementálním způsobem. Existuje spojení mezi účinnými aukcemi a teorií duality. Primární duální algoritmus lze považovat za decentralizovanou a dynamickou metodu stanovení cenové rovnováhy. Primaldual algoritmus obvykle udržuje proveditelné duální řešení a snaží se vypočítat primární řešení, které je jak proveditelné, tak splňuje podmínky doplňkové vůle. Pokud je takové řešení nalezeno, algoritmus se ukončí. V opačném případě je duální řešení aktualizováno na optimálnost a algoritmus pokračuje další iterací. Bylo navrženo několik aukčních formátů, které jsou založeny na přístupu dvojího druhu.
Displayed: 31/10/2024 22:44