Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
Change search
Link to record
Permanent link

Direct link
Andersson, Arne
Alternative names
Publications (10 of 28) Show all publications
Andersson, A. & Wilenius, J. (2009). A New Analysis of Revenue in the Combinatorial and Simultaneous Auction.
Open this publication in new window or tab >>A New Analysis of Revenue in the Combinatorial and Simultaneous Auction
2009 (English)Report (Other academic)
Abstract [en]

We prove that in many cases, a first-price sealed-bid combinatorial auction gives higher expected revenue than a sealed-bid simultaneous auction. This is the first theoretical evidence that combinatorial auctions indeed generate higher revenue, which has been a common belief for decades.

We use a model with many bidders and items, where bidders are of two types: (i) single-bidders interested in only one item and (ii) synergy-bidders, each interested in one random combination of items. We provide an upper bound on the expected revenue for simultaneous auctions and a lower bound on combinatorial auctions. Our bounds are parameterized on the number of bidders and items, combination size, and synergy.

We derive an asymptotic result, proving that as the number of bidders approach infinity, expected revenue of the combinatorial auction will be higher than that of the simultaneous auction. We also provide concrete examples where the combinatorial auction is revenue-superior.

Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2009-001
Keywords
combinatorial auction, first-price, equilibrium, strategy, expected revenue, multi-object auction, auction, multiple-item, simulatneous auction, bidding, synergy, synergies, game theory
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-102935 (URN)
Available from: 2009-05-13 Created: 2009-05-13 Last updated: 2018-01-13Bibliographically approved
Carlsson, P. & Andersson, A. (2007). A Flexible Model for Tree-Structured Multi-Commodity Markets. Electronic Commerce Research, 7(1), 69-88
Open this publication in new window or tab >>A Flexible Model for Tree-Structured Multi-Commodity Markets
2007 (English)In: Electronic Commerce Research, ISSN 1389-5753, E-ISSN 1572-9362, Vol. 7, no 1, p. 69-88Article in journal (Refereed) Published
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-92385 (URN)10.1007/s10660-006-0063-Y (DOI)
Available from: 2004-11-22 Created: 2004-11-22 Last updated: 2018-01-13Bibliographically approved
Wilenius, J. & Andersson, A. (2007). Discovering Equilibrium Strategies for a Combinatorial First Price Auction. In: 9th IEEE International Conference on E-Commerce Technology/4th IEEE International Conference on Enterprise Computing, E-Commerce and E-Services. Paper presented at 9th IEEE International Conference on E-Commerce Technology/4th IEEE International Conference on Enterprise Computing, E-Commerce and E-Services Tokyo, JAPAN, JUL 23-26, 2007 (pp. 13-20).
Open this publication in new window or tab >>Discovering Equilibrium Strategies for a Combinatorial First Price Auction
2007 (English)In: 9th IEEE International Conference on E-Commerce Technology/4th IEEE International Conference on Enterprise Computing, E-Commerce and E-Services, 2007, p. 13-20Conference paper, Published paper (Refereed)
Abstract [en]

In this paper the unresolved and fundamental strategy problem of the first price single round sealed bid combinatorial auction is addressed. As a step toward discovering equilibrium strategies, a new heuristic based on simple and intuitive methods is presented. The heuristic is evaluated using two different independently and uniformly distributed valuation models, one very general model where bidders bid on all combinations and one restricted model where bidders bid on one specific combination and single bids on the remaining items. Results yield natural explainable strategies with good characteristics based on comparisons of payoff, revenue and allocative efficiency.

National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-10758 (URN)10.1109/CEC-EEE.2007.41 (DOI)000250044300001 ()978-0-7695-2913-4 (ISBN)
Conference
9th IEEE International Conference on E-Commerce Technology/4th IEEE International Conference on Enterprise Computing, E-Commerce and E-Services Tokyo, JAPAN, JUL 23-26, 2007
Available from: 2008-01-25 Created: 2008-01-25 Last updated: 2018-01-12Bibliographically approved
Andersson, A. & Thorup, M. (2007). Dynamic Ordered Sets with Exponential Search Trees. Journal of the ACM, 54(3), 1236460
Open this publication in new window or tab >>Dynamic Ordered Sets with Exponential Search Trees
2007 (English)In: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 54, no 3, p. 1236460-Article in journal (Refereed) Published
Abstract [en]

We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. This leads to an optimal bound of O(log n/log log n) for searching and updating a dynamic set X of n integer keys in linear space. Searching X for an integer y means finding the maximum key in X which is smaller than or equal to y. This problem is equivalent to the standard text book problem of maintaining an ordered set. The best previous deterministic linear space bound was O(log n/log log n) due to Fredman and Willard from STOC 1990. No better deterministic search bound was known using polynomial space. We also get the following worst-case linear space trade-offs between the number n, the word length W, and the maximal key U < 2W: O(min log log n + log n/logW, log log n log log U/log log log U). These trade-offs are, however, not likely to be optimal. Our results are generalized to finger searching and string searching, providing optimal results for both in terms of n.

Keywords
algorithms, theory, search trees, ordered lists
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-25631 (URN)10.1145/1236457.1236460 (DOI)000247980500003 ()
Available from: 2007-04-18 Created: 2007-04-18 Last updated: 2018-01-12Bibliographically approved
Karlsson, M., Ygge, F. & Andersson, A. (2007). Market-based Approaches to Optimization. Computational intelligence, 23(1), 92-109
Open this publication in new window or tab >>Market-based Approaches to Optimization
2007 (English)In: Computational intelligence, ISSN 0824-7935, E-ISSN 1467-8640, Vol. 23, no 1, p. 92-109Article in journal (Refereed) Published
Abstract [en]

We present a general discussion of what constitutes a market-oriented approach to optimization. We demonstrate how a general framework can be used to conceptually improve two well-known approaches from the literature, and discuss computational properties of the different approaches. We also show how existing theory could be adjusted to be directly applicable to the theory of the two approaches, thus proving special theory unnecessary. We want to bring out the pedagogical aspects of market mechanisms, to take full advantage of its potential.

Keywords
market-oriented programming, market mechanism, agent strategies, market-based optimization, resource allocation problems
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-25684 (URN)10.1111/j.1467-8640.2007.00296.x (DOI)000245923700007 ()
Note
Market based optimization, optimization, market based programmingAvailable from: 2007-04-18 Created: 2007-04-18 Last updated: 2018-01-12Bibliographically approved
Carlsson, P. & Andersson, A. (2005). A Flexible Model for Tree-Sructured Multi-Commodity Markets. In: CEC 2005: Seventh IEEE International Conference on E-Commerce Technology (pp. 50-58).
Open this publication in new window or tab >>A Flexible Model for Tree-Sructured Multi-Commodity Markets
2005 (English)In: CEC 2005: Seventh IEEE International Conference on E-Commerce Technology, 2005, p. 50-58Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we study tree-structured multi-commodity, multi-unit markets. The concept is a way to handle dependencies between commodities on the market in a tractable way. The winner determination problem of a general combinatorial market is well known to be NP-hard.

It has been shown that on single-unit single-sided combinatorial auctions with tree-structured bundles the problem can be computed in polynomial time. We show that it is possible to extend this to multi-unit double-sided markets. Further it is possible to handle the commodities of a bundle not only as complements but as perfect substitutes too. Under certain conditions the computation time is still polynomial.

Keywords
multi commodity markets, electronic markets, computational markets, equilibrium markets, resource allocation, power markets, bandwidth markets, computational complexity
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-79117 (URN)0-7695-2277-7 (ISBN)
Available from: 2006-04-25 Created: 2006-04-25 Last updated: 2018-01-13
Andersson, A., Holmström, J. & Willman, M. (2005). An Auction Mechanism for Polynomial-time Execution with Combinatorial Constraints. In: Proc. 7th International Conference on E-Commerce Technology (pp. 17-24). Piscataway, NJ: IEEE
Open this publication in new window or tab >>An Auction Mechanism for Polynomial-time Execution with Combinatorial Constraints
2005 (English)In: Proc. 7th International Conference on E-Commerce Technology, Piscataway, NJ: IEEE , 2005, p. 17-24Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Piscataway, NJ: IEEE, 2005
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-78654 (URN)10.1109/ICECT.2005.103 (DOI)0-7695-2277-7 (ISBN)
Available from: 2007-04-18 Created: 2007-04-18 Last updated: 2018-01-13Bibliographically approved
Andersson, A. (2005). Balanced Binary Search Trees. In: Handbook of Data Structures and Applications (pp. 1392). : CRC Press
Open this publication in new window or tab >>Balanced Binary Search Trees
2005 (English)In: Handbook of Data Structures and Applications, CRC Press , 2005, p. 1392-Chapter in book (Other scientific)
Place, publisher, year, edition, pages
CRC Press, 2005
Identifiers
urn:nbn:se:uu:diva-25801 (URN)1584884355 (ISBN)
Available from: 2007-02-13 Created: 2007-02-13
Andersson, A. (2005). Searching and Priority Queues in o(log n) Time. In: Handbook of Data Structures and Applications (pp. 1392). : CRC Press
Open this publication in new window or tab >>Searching and Priority Queues in o(log n) Time
2005 (English)In: Handbook of Data Structures and Applications, CRC Press , 2005, p. 1392-Chapter in book (Other (popular scientific, debate etc.))
Place, publisher, year, edition, pages
CRC Press, 2005
Identifiers
urn:nbn:se:uu:diva-25803 (URN)1584884355 (ISBN)
Available from: 2007-02-13 Created: 2007-02-13
Carlsson, P., Andersson, A. & Ygge, F. (2003). A Tractable Mechanism for Time Dependent Markets. : Uppsala: Department of Information Technology, Uppsala University
Open this publication in new window or tab >>A Tractable Mechanism for Time Dependent Markets
2003 (English)Report (Other scientific)
Place, publisher, year, edition, pages
Uppsala: Department of Information Technology, Uppsala University, 2003
Series
IT Technical Report 2003-027
Identifiers
urn:nbn:se:uu:diva-49011 (URN)
Available from: 2006-12-27 Created: 2006-12-27
Organisations

Search in DiVA

Show all publications