Advanced search
Start date

Algorithms for Winner determination and Precification problems in combinatorial Auctions

Grant number: 12/08222-0
Support Opportunities:Scholarships abroad - Research Internship - Doctorate
Effective date (Start): November 01, 2012
Effective date (End): October 31, 2013
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Flávio Keidi Miyazawa
Grantee:Carlos Eduardo de Andrade
Supervisor: Mauricio G. C. Resende
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Research place: AT&T Labs Research, United States  
Associated to the scholarship:10/05233-5 - Evolutionary algorithms for some problems in telecommunications, BP.DR


Auctions are considered the most general way to allocate and to pricing of goods and services when it is not know the real value of them. Traditionally in an auction, it is negotiated a item or group of items where the agents involved, known as bidders, can only submit bids on one item or a package of items. This type of trading may not lead to economic efficiency of the market because the bidders may not be able to express their preferences completely. To work around this issue, the combinatorial auctions allow bidders to submit multiple bids for different subsets of items, not necessarily disjoint, and thus can express complementarity and substitutability among the items they want. The challenges of these types of auctions are the size of instances that are usually exponential in the number of bids made, and the winner determination problem that is NP-hard (even with a polynomial input), which requires a large computational effort. We are interested in the recent strategies to address these problems, such as specialized exact algorithms and heuristics that can ensure desirable economic properties, such as certain euiqlibria and fair pricing. For this, we propose the research and development of exact methods and heuristics, discussion and comparison with recent results from the literature, as well as computational experiments to prove the effectiveness and efficiency of the methods. (AU)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
ANDRADE, CARLOS E.; RESENDE, MAURICIO G. C.; ZHANG, WEIYI; SINHA, RAKESH K.; REICHMANN, KENNETH C.; DOVERSPIKE, ROBERT D.; MIYAZAWA, FLAVIO K.. A biased random-key genetic algorithm for wireless backhaul network design. APPLIED SOFT COMPUTING, v. 33, p. 150-169, . (12/08222-0, 10/05233-5)
DE ANDRADE, CARLOS EDUARDO; TOSO, RODRIGO FRANCO; RESENDE, MAURICIO G. C.; MIYAZAWA, FLAVIO KEIDI. Biased Random-Key Genetic Algorithms for theWinner Determination Problem in Combinatorial Auctions. EVOLUTIONARY COMPUTATION, v. 23, n. 2, p. 279-307, . (12/08222-0, 10/05233-5)

Please report errors in scientific publications list by writing to: