uu.seUppsala universitets publikasjoner
Endre søk
Link to record
Permanent link

Direct link
BETA
Andersson, Arne
Alternativa namn
Publikasjoner (10 av 28) Visa alla publikasjoner
Andersson, A. & Wilenius, J. (2009). A New Analysis of Revenue in the Combinatorial and Simultaneous Auction.
Åpne denne publikasjonen i ny fane eller vindu >>A New Analysis of Revenue in the Combinatorial and Simultaneous Auction
2009 (engelsk)Rapport (Annet vitenskapelig)
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.

Serie
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2009-001
Emneord
combinatorial auction, first-price, equilibrium, strategy, expected revenue, multi-object auction, auction, multiple-item, simulatneous auction, bidding, synergy, synergies, game theory
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-102935 (URN)
Tilgjengelig fra: 2009-05-13 Laget: 2009-05-13 Sist oppdatert: 2018-01-13bibliografisk kontrollert
Carlsson, P. & Andersson, A. (2007). A Flexible Model for Tree-Structured Multi-Commodity Markets. Electronic Commerce Research, 7(1), 69-88
Åpne denne publikasjonen i ny fane eller vindu >>A Flexible Model for Tree-Structured Multi-Commodity Markets
2007 (engelsk)Inngår i: Electronic Commerce Research, ISSN 1389-5753, E-ISSN 1572-9362, Vol. 7, nr 1, s. 69-88Artikkel i tidsskrift (Fagfellevurdert) Published
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-92385 (URN)10.1007/s10660-006-0063-Y (DOI)
Tilgjengelig fra: 2004-11-22 Laget: 2004-11-22 Sist oppdatert: 2018-01-13bibliografisk kontrollert
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).
Åpne denne publikasjonen i ny fane eller vindu >>Discovering Equilibrium Strategies for a Combinatorial First Price Auction
2007 (engelsk)Inngår i: 9th IEEE International Conference on E-Commerce Technology/4th IEEE International Conference on Enterprise Computing, E-Commerce and E-Services, 2007, s. 13-20Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-10758 (URN)10.1109/CEC-EEE.2007.41 (DOI)000250044300001 ()978-0-7695-2913-4 (ISBN)
Konferanse
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
Tilgjengelig fra: 2008-01-25 Laget: 2008-01-25 Sist oppdatert: 2018-01-12bibliografisk kontrollert
Andersson, A. & Thorup, M. (2007). Dynamic Ordered Sets with Exponential Search Trees. Journal of the ACM, 54(3), 1236460
Åpne denne publikasjonen i ny fane eller vindu >>Dynamic Ordered Sets with Exponential Search Trees
2007 (engelsk)Inngår i: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 54, nr 3, s. 1236460-Artikkel i tidsskrift (Fagfellevurdert) 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.

Emneord
algorithms, theory, search trees, ordered lists
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-25631 (URN)10.1145/1236457.1236460 (DOI)000247980500003 ()
Tilgjengelig fra: 2007-04-18 Laget: 2007-04-18 Sist oppdatert: 2018-01-12bibliografisk kontrollert
Karlsson, M., Ygge, F. & Andersson, A. (2007). Market-based Approaches to Optimization. Computational intelligence, 23(1), 92-109
Åpne denne publikasjonen i ny fane eller vindu >>Market-based Approaches to Optimization
2007 (engelsk)Inngår i: Computational intelligence, ISSN 0824-7935, E-ISSN 1467-8640, Vol. 23, nr 1, s. 92-109Artikkel i tidsskrift (Fagfellevurdert) 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.

Emneord
market-oriented programming, market mechanism, agent strategies, market-based optimization, resource allocation problems
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-25684 (URN)10.1111/j.1467-8640.2007.00296.x (DOI)000245923700007 ()
Merknad
Market based optimization, optimization, market based programmingTilgjengelig fra: 2007-04-18 Laget: 2007-04-18 Sist oppdatert: 2018-01-12bibliografisk kontrollert
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).
Åpne denne publikasjonen i ny fane eller vindu >>A Flexible Model for Tree-Sructured Multi-Commodity Markets
2005 (engelsk)Inngår i: CEC 2005: Seventh IEEE International Conference on E-Commerce Technology, 2005, s. 50-58Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

Emneord
multi commodity markets, electronic markets, computational markets, equilibrium markets, resource allocation, power markets, bandwidth markets, computational complexity
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-79117 (URN)0-7695-2277-7 (ISBN)
Tilgjengelig fra: 2006-04-25 Laget: 2006-04-25 Sist oppdatert: 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
Åpne denne publikasjonen i ny fane eller vindu >>An Auction Mechanism for Polynomial-time Execution with Combinatorial Constraints
2005 (engelsk)Inngår i: Proc. 7th International Conference on E-Commerce Technology, Piscataway, NJ: IEEE , 2005, s. 17-24Konferansepaper, Publicerat paper (Fagfellevurdert)
sted, utgiver, år, opplag, sider
Piscataway, NJ: IEEE, 2005
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-78654 (URN)10.1109/ICECT.2005.103 (DOI)0-7695-2277-7 (ISBN)
Tilgjengelig fra: 2007-04-18 Laget: 2007-04-18 Sist oppdatert: 2018-01-13bibliografisk kontrollert
Andersson, A. (2005). Balanced Binary Search Trees. In: Handbook of Data Structures and Applications (pp. 1392). : CRC Press
Åpne denne publikasjonen i ny fane eller vindu >>Balanced Binary Search Trees
2005 (engelsk)Inngår i: Handbook of Data Structures and Applications, CRC Press , 2005, s. 1392-Kapittel i bok, del av antologi (Annet vitenskapelig)
sted, utgiver, år, opplag, sider
CRC Press, 2005
Identifikatorer
urn:nbn:se:uu:diva-25801 (URN)1584884355 (ISBN)
Tilgjengelig fra: 2007-02-13 Laget: 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
Åpne denne publikasjonen i ny fane eller vindu >>Searching and Priority Queues in o(log n) Time
2005 (engelsk)Inngår i: Handbook of Data Structures and Applications, CRC Press , 2005, s. 1392-Kapittel i bok, del av antologi (Annet (populærvitenskap, debatt, mm))
sted, utgiver, år, opplag, sider
CRC Press, 2005
Identifikatorer
urn:nbn:se:uu:diva-25803 (URN)1584884355 (ISBN)
Tilgjengelig fra: 2007-02-13 Laget: 2007-02-13
Carlsson, P., Andersson, A. & Ygge, F. (2003). A Tractable Mechanism for Time Dependent Markets. : Uppsala: Department of Information Technology, Uppsala University
Åpne denne publikasjonen i ny fane eller vindu >>A Tractable Mechanism for Time Dependent Markets
2003 (engelsk)Rapport (Annet vitenskapelig)
sted, utgiver, år, opplag, sider
Uppsala: Department of Information Technology, Uppsala University, 2003
Serie
IT Technical Report 2003-027
Identifikatorer
urn:nbn:se:uu:diva-49011 (URN)
Tilgjengelig fra: 2006-12-27 Laget: 2006-12-27
Organisasjoner