uu.seUppsala universitets publikationer
Ändra sökning
Länk till posten
Permanent länk

Direktlänk
BETA
Andersson, Arne
Alternativa namn
Publikationer (10 of 28) Visa alla publikationer
Andersson, A. & Wilenius, J. (2009). A New Analysis of Revenue in the Combinatorial and Simultaneous Auction.
Öppna denna publikation i ny flik eller fönster >>A New Analysis of Revenue in the Combinatorial and Simultaneous Auction
2009 (Engelska)Rapport (Övrigt vetenskapligt)
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
Nyckelord
combinatorial auction, first-price, equilibrium, strategy, expected revenue, multi-object auction, auction, multiple-item, simulatneous auction, bidding, synergy, synergies, game theory
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-102935 (URN)
Tillgänglig från: 2009-05-13 Skapad: 2009-05-13 Senast uppdaterad: 2018-01-13Bibliografiskt granskad
Carlsson, P. & Andersson, A. (2007). A Flexible Model for Tree-Structured Multi-Commodity Markets. Electronic Commerce Research, 7(1), 69-88
Öppna denna publikation i ny flik eller fönster >>A Flexible Model for Tree-Structured Multi-Commodity Markets
2007 (Engelska)Ingår i: Electronic Commerce Research, ISSN 1389-5753, E-ISSN 1572-9362, Vol. 7, nr 1, s. 69-88Artikel i tidskrift (Refereegranskat) Published
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-92385 (URN)10.1007/s10660-006-0063-Y (DOI)
Tillgänglig från: 2004-11-22 Skapad: 2004-11-22 Senast uppdaterad: 2018-01-13Bibliografiskt granskad
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).
Öppna denna publikation i ny flik eller fönster >>Discovering Equilibrium Strategies for a Combinatorial First Price Auction
2007 (Engelska)Ingå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-20Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-10758 (URN)10.1109/CEC-EEE.2007.41 (DOI)000250044300001 ()978-0-7695-2913-4 (ISBN)
Konferens
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
Tillgänglig från: 2008-01-25 Skapad: 2008-01-25 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
Andersson, A. & Thorup, M. (2007). Dynamic Ordered Sets with Exponential Search Trees. Journal of the ACM, 54(3), 1236460
Öppna denna publikation i ny flik eller fönster >>Dynamic Ordered Sets with Exponential Search Trees
2007 (Engelska)Ingår i: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 54, nr 3, s. 1236460-Artikel i tidskrift (Refereegranskat) 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.

Nyckelord
algorithms, theory, search trees, ordered lists
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-25631 (URN)10.1145/1236457.1236460 (DOI)000247980500003 ()
Tillgänglig från: 2007-04-18 Skapad: 2007-04-18 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
Karlsson, M., Ygge, F. & Andersson, A. (2007). Market-based Approaches to Optimization. Computational intelligence, 23(1), 92-109
Öppna denna publikation i ny flik eller fönster >>Market-based Approaches to Optimization
2007 (Engelska)Ingår i: Computational intelligence, ISSN 0824-7935, E-ISSN 1467-8640, Vol. 23, nr 1, s. 92-109Artikel i tidskrift (Refereegranskat) 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.

Nyckelord
market-oriented programming, market mechanism, agent strategies, market-based optimization, resource allocation problems
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-25684 (URN)10.1111/j.1467-8640.2007.00296.x (DOI)000245923700007 ()
Anmärkning
Market based optimization, optimization, market based programmingTillgänglig från: 2007-04-18 Skapad: 2007-04-18 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
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).
Öppna denna publikation i ny flik eller fönster >>A Flexible Model for Tree-Sructured Multi-Commodity Markets
2005 (Engelska)Ingår i: CEC 2005: Seventh IEEE International Conference on E-Commerce Technology, 2005, s. 50-58Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Nyckelord
multi commodity markets, electronic markets, computational markets, equilibrium markets, resource allocation, power markets, bandwidth markets, computational complexity
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-79117 (URN)0-7695-2277-7 (ISBN)
Tillgänglig från: 2006-04-25 Skapad: 2006-04-25 Senast uppdaterad: 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
Öppna denna publikation i ny flik eller fönster >>An Auction Mechanism for Polynomial-time Execution with Combinatorial Constraints
2005 (Engelska)Ingår i: Proc. 7th International Conference on E-Commerce Technology, Piscataway, NJ: IEEE , 2005, s. 17-24Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
Piscataway, NJ: IEEE, 2005
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-78654 (URN)10.1109/ICECT.2005.103 (DOI)0-7695-2277-7 (ISBN)
Tillgänglig från: 2007-04-18 Skapad: 2007-04-18 Senast uppdaterad: 2018-01-13Bibliografiskt granskad
Andersson, A. (2005). Balanced Binary Search Trees. In: Handbook of Data Structures and Applications (pp. 1392). : CRC Press
Öppna denna publikation i ny flik eller fönster >>Balanced Binary Search Trees
2005 (Engelska)Ingår i: Handbook of Data Structures and Applications, CRC Press , 2005, s. 1392-Kapitel i bok, del av antologi (Övrigt vetenskapligt)
Ort, förlag, år, upplaga, sidor
CRC Press, 2005
Identifikatorer
urn:nbn:se:uu:diva-25801 (URN)1584884355 (ISBN)
Tillgänglig från: 2007-02-13 Skapad: 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
Öppna denna publikation i ny flik eller fönster >>Searching and Priority Queues in o(log n) Time
2005 (Engelska)Ingår i: Handbook of Data Structures and Applications, CRC Press , 2005, s. 1392-Kapitel i bok, del av antologi (Övrig (populärvetenskap, debatt, mm))
Ort, förlag, år, upplaga, sidor
CRC Press, 2005
Identifikatorer
urn:nbn:se:uu:diva-25803 (URN)1584884355 (ISBN)
Tillgänglig från: 2007-02-13 Skapad: 2007-02-13
Carlsson, P., Andersson, A. & Ygge, F. (2003). A Tractable Mechanism for Time Dependent Markets. : Uppsala: Department of Information Technology, Uppsala University
Öppna denna publikation i ny flik eller fönster >>A Tractable Mechanism for Time Dependent Markets
2003 (Engelska)Rapport (Övrigt vetenskapligt)
Ort, förlag, år, upplaga, sidor
Uppsala: Department of Information Technology, Uppsala University, 2003
Serie
IT Technical Report 2003-027
Identifikatorer
urn:nbn:se:uu:diva-49011 (URN)
Tillgänglig från: 2006-12-27 Skapad: 2006-12-27
Organisationer

Sök vidare i DiVA

Visa alla publikationer