An Ontology for Formalising Agreement Patterns in Auction Markets

Abstract

Knowledge and best practices on auction systems are currently disseminated across the research literature, which limits its access, reuse, evaluation and feedback by practitioners. This article presents a systematic approach to collect this knowledge as design patterns, in order to provide assistance to software developers. An ontology has been dened for formalising design patterns in auction systems, with the aim of improving its searchability by software developers. Finally, a case study illustrates how the proposed pattern ontology provides assistance in the development of a dynamic pricing model for an e-commerce service.

Introduction

Auctions provide a market system model that enable the exchange of resources on the basis of supply and demand. They have proved to be an e ective model for dynamic pricing of resources in di erent scenarios such as electronic commerce [ 1 ], resource allocation [ 2 ], service pricing [ 3 ] or sponsored search pricing [ 4 ].

Nevertheless, software engineers have few available resources that provide them support in the design of auction mechanisms and automatic bidders, since current knowledge and best practices on auctions are disseminated across research publications. It is a good practice to identify the elements of good and reusable designs in auctions, and provide a systematic framework for formalising the experience with these designs. This is precisely the role of design patterns [ 5 ], which describe general reusable solutions to commonly recurring problems in software design. The notion of design patterns was originated in the objectoriented software engineering community and has been widely accepted by this community, having a strong impact on how object-oriented software is designed, implemented and communicated nowadays.

The purpose of this article is to provide a structured and formalised schema for describing design patterns in the eld of agreement technologies and validate it through its application in the domain of auctions.

The rest of the article is organised as follows. Section 2 presents an ontology for describing agreement patterns, in order to provide standard facilities for retrieving patterns based on the user requirements. This agreement patterns ontology has been linked with an auction domain ontology for describing the main concepts of the auction domain, in order to provide a common language for describing the auction patterns. In order to show the applicability of our approach, a case study is developed within section 3. Finally, section 4 summarises the main contributions of this paper and the future research activities. 2

Modeling an Ontology for Auction Patterns Even though design patterns are usually expressed in natural language, several works have proposed its formalisation in order to provide tool support for consulting a pattern catalogue and guide developers in its application. Ontologies [ 6 ] have been considered as a natural formalisation technique that enables an infrastructure for sharing and interconnecting semantically pattern languages in the web. Several works have used ontologies [ 7 ] for formalising both the structure of the patterns [ 8,9 ] (how to apply the pattern) as well as its intention (when to apply the pattern) [ 7,10 ].

This article presents an ontology for formalising the intention of agreement patterns in order to improve its ndability. The ontology is organised into three levels as shown in g. 1 which are detailed below. The rst level de nes an ontology (APO) for agreement patterns (section 2.1), with the aim of facilitating the searchability of the patterns by software developers. A domain ontology (AUTERMS) for the auction domain (section 2.2) provides the common terminology for describing auction patterns. Finally, an ontology (AUPA) has been de ned for describing the auction patterns (section 2.3) . This ontology extends the APO ontology and is described using the AUTERMS ontology. Agreement patterns [ 11 ] provide a way to collect best practices for reaching agreements in a structured way. In this section, the Agreement Patterns Ontology (APO) is introduced in order to catalogue agreement patterns. This catalogue should support developers in choosing a pattern for a given problem.

In order to determine the scope of the ontology, the ontology should be able to answer the following competency questions [ 12 ]: { Which design patterns can solve a given problem? { Which design patterns can solve a given problem and are applicable in a given context? { Which design patterns are related to a given domain concept? { Which design patterns are available for a given task?

The proposed ontology is based on the structure of the DPIO ontology[ 7 ]. That ontology describes the relationship between patterns and problem types, which are described by problem constraints. We have extended DPIO by focusing on pattern constraints, instead of problem type constraints.

apo:relatedPattern apo:hasConstraint apo:ProblemType apo:solves apo:Pattern apo:relatedConcept isA isA isA apo:Concept apo:Constraint apo:ArchitecturalPattern apo:OrganisationalPattern

apo:BehavioralPattern

The structure of the APO ontology is depicted in g. 2. The main relationships of the core ontology are described below. A Pattern can solve one or more ProblemTypes and is applicable only if some Constraints are ful lled. A Pattern can be related with other Patterns. Domain Concepts can be related with one or more ProblemTypes and one or more Patterns. Patterns are organised according to the task they solve into: { Organisational Patterns. These patterns collect social structure patterns which de ne the norms, social and interaction model [ 13 ] which form the society as a whole, and which determine, to some varying degree, the actions of the individuals socialised into that structure. { Behavioural Patterns. These patterns collect individual behaviours of the participants in the agreement in order to satisfy a goal. { Architectural Patterns. These patterns describe architectural patterns describing the software architecture of the participants in the agreement. 2.2

The Auction terms Ontology (AUTERMS)

The objective of the Auction Terms Ontology (AUTERMS) is modelling the auction domain in order to provide a common vocabulary for describing auction patterns. Previous work have also proposed ontologies in the negotiation domain [ 14,15,16 ], and have been extended to the auction domain, but we have not found a speci c ontology in the auction domain. We have modelled a basic ontology based mainly on the auction patterns proposed by Re [ 17 ], the research survey on auctions by Parsons et al. [ 1 ] and the ontology for the agent trading competition developed by Wellman [ 18 ]. The core structure of the proposed ontology AUPA is shown in g. 3.

aupa:AuctionHouse aupa:manages

aupa:Auction aupa:registeredUsers aupa:hasBids aupa:auctionType aupa:Bid aupa:offers

aupa:AuctionProtocol aupa:madeBy aupa:offers hasProperty aupa:Participant aupa:Resource

aupa:AuctionProperty

The main concepts of this ontology are AuctionHouse, Auction, Participant, AuctionProtocol and AuctionProperty. Auctions are a negotiation process in which di erent Participants exchange information in the form of O ers in order to obtain a Resource. Those Auctions are placed in di erent AuctionHouses which represents the auctioneer of an Auction. An AuctionHouse has the responsibility of sharing Auction information between di erent Participants following the rules of a speci c AuctionProtocol. An AuctionProtocol represents which AuctionProperties must be meet in a speci c Auction. An AuctionProperty helps to classify an AuctionProtocol in order to nd the most suitable based on the problem constraints. Previous works have also proposed the usage of design patterns in agreement technologies and auctions. Iglesias et al. [ 11 ] propose Agreement Patterns for formalising recurring solutions to agreement problems. Re et. al. [ 17 ] propose auction patterns from an object oriented perspective. In the eld of multiagent systms, Oluyomi [ 19 ] proposes a classi cation scheme for agent oriented patterns which is applied to a relevant number of agent patterns. Jureta et al. [ 20 ] describe three agent oriented patterns in the auction domain.

This article extends the work developed by Iglesias et al. [ 11 ] in order to organise, identify and describe semantically auction patterns as a speci c family of agreement patterns. In order to validate our approach, several patterns have been formalised within this ontology. Fig. 4 shows these patterns grouped by the related Concept in the domain on AUTERMS ontology. In addition, the auction patterns are classi ed in Architectural, Organisational and Behavioural according to the APO Ontology.

The pattern catalogue includes the following patterns: { Organisational: AuctionPattern, English Auction, Dutch Auction, Vickrey

Auction, First Price Sealed Auction { Architectural: Lying Agent [ 21 ], AA Agent [ 22 ], Basic Negotiation Agent [ 19 ] { Behavioural: Proxy Bidding [ 20 ], Sniping, Dispute Resolution [ 20 ], Payment [ 20 ], Fraud Detection [ 20 ], Colussion, Estimate Market Value.

In order to illustrate how auction patterns are described, the pattern Vickrey Auction is described in natural language in table 1, while its semantic description is depicted in g. 5 and g. 6. The ontology has been de ned using the ontology editor Protege [ 23 ]. Thanks to the semantic description, the catalogue can be consulted and ltered according to the user constraints, as described in section 3.

Name

Alias

Keywords

Problem Type

Problem

Context

Solution

Vickrey auction Second-price sealed-bid auction.

Auction, service pricing.

Resource assignation.

Auction of multiple similar resources, or items, in which participants should be encouraged to share their true valuation using incentives.

There are di erent consumers willing to get the resources, and the real value of the resource is not known.

This auction is de ned by the next properties, as seen on g. 5 : { One round: Bids are received in a unique round, which last until all participants have made their o er, or until a speci c time. { Sealed: O ers are not visible, in any mean, to partici

pants, until the auction has nished. { Multiple items per bid: O ers should be for more than a resource, and associated with a price. Only an unique bid per participant. { Second pricing: the highest n bids are awarded the resource and pay a price equal to the n+1 highest amount bid. { Incentive compatibility: Each participant maximizes its expected utility, by revealing their true valuation, as nal price is not dependant on the o er made, but in the last highest o er. Also, in scenarios with different auctioned resources, a preference assignation of resources, will be an incentive to bid as high as possible [ 24 ].

The most important advantage of this auction, is that sellers don't require to have knowledge about buyers willingness to pay. Because of that, this auction is highly suitable in scenarios without that information.

Examples Mobile spectrum assignment[ 1 ], Internet advertising[ 25 ]. Related patterns Sealed auction, Fake bidding.

Table 1: Vickrey Organisational Pattern in Natural Language 3

Case study

In order to illustrate the practical application of agreement patterns, this section describes a case study consisting of the development of an opera ticket selling service. // similar restrictions for # FixedProtocol , # SealedNegotiation , // and # UnidirectinalInformationExchange

An opera thether desires to maximize its bene t from sold tickets, which are sold by di erent online enterntainment ticket selling services. Several strategies for o ering this service are available, such as de ning a xed pricing policy based on position of the seat or dynamic pricing based on an auction protocol. The opera theather desires to explore this second alternative.

In order to evaluate the ontology, we are going to review the competency questions enumerated in section 2.1, translate these consults into formal questions in SPARQL, and evaluate the result set of the queries.

Which design patterns can solve a given problem?. In our case, we are interested in consulting all the organisational patterns that solve the problem Resource Allocation. Fig. 7 shows the corresponding SPARQL query. The result set contains all the Organisational Auction Patterns of the ontology. In a full version of the ontology we could obtain other patterns not related with auctions, such as bargaining.

SELECT DISTINCT ? pattern

WHERE { ? pattern rdfs : s u b C l a s s O f apo : O r g a n i s a t i o n a l P a t t e r n . ? pattern rdfs : s u b C l a s s O f apo : Pattern . ? pattern rdfs : s u b C l a s s O f [ rdf : type owl : R e s t r i c t i o n ; owl : s o m e V a l u e s F r o m apo : R e s o u r c e A l l o c a t i o n ; owl : o n P r o p e r t y apo : solves }

Which design patterns can solve a given problem and are applicable in a given context?. The results of the previous query can be ltered specifying constraints. In our domain, opera seats are auctioned. We can decide whether opera seats are divisible or indivisible. In our case, we can sell all the seats for each opera performances, but each seat can be sold at a di erent price, so we add the constraint DivisibleResource. Fig. 8 shows the corresponding SPARQL query, which would return the Vickrey Auction Pattern.

Which design patterns are related to a given domain concept?. In our domain, we could be interested in which design patterns are related with the Auction House concept as shown in Figre 9.

Which design patterns are available for a given task?. In case we desire to de ne the architecture of a bidder, we can query the Architectural Patterns related with the concept Participant (Fig. 10).

SELECT DISTINCT ? pattern

WHERE { ? pattern rdfs : subClassOf apo : Pattern . ? pattern rdfs : subClassOf apo : OrganisationalPattern . ? pattern rdfs : subClassOf [ rdf : type owl : Restriction ; owl : someValuesFrom apo : ResourceAllocation ; owl : onProperty apo : solves ]. ? pattern rdfs : subClassOf [ rdf : type owl : Restriction ; owl : hasValue apo : DivisibleResources ; owl : onProperty apo : hasConstraint }

Conclusions and future work

Design patterns can contribute to promote knowledge reuse and advance in the eld of agreement technologies, since the expertise of practices is formalised and can be easily shared among practitioners, allowing them to share their experiences and understand better the advantages. limitations and applicability of these patterns.

In this paper, several auction patterns have been identi ed in the research literature and described and classi ed according to a pattern form. In addition, a domain ontology for auctions has been de ned in order to provide automated reasoning on the application of patterns.

Current work is focused on several directions. First, our aim is progressing on the formalisation of the patterns themselves in order to provide and ontologybased design pattern repository as [ 26,27,7 ]. Second, since the targeted users of this research are software developers, our goal is providing at hand support during their development tasks, through the integration of this tool in a standard IDE such as Eclipse or Netbeans. In addition, this paper has presented an initial set of identi ed patterns, and our aim is enlarging this set, analysing available systems and documented practices as well as with the cooperation of other researchers and users.

Acknowledgements

This research has been partly funded by the Spanish Ministry of Science and Innovation through the projects Ingenio Consolider2010 AT Agreement Technologies (CSD2007-0022)), OVAMAH (TIN2009-13839-C03-02) and T2C2 (TIN200806739-C04-03/TSI) as well as the Spanish Ministry of Industry, Tourism and Trade through the project RESULTA (TSI-020301-2009-31). Volume 5421 of Lecture Notes in Computer Science. Springer Berlin / Heidelberg (2009) 318{331 27. Pavlic, L., Hericko, M., Podgorelec, V.: Improving design pattern adoption with Ontology-Based Design Pattern Repository. IEEE (June 2008)

References

1. Parsons , S. , Rodr guez-Aguilar, J.A. , Klein , M. : Auctions and bidding: A guide for computer scientists . 24 ( 2 ) ( August 2004 ) 271 { 287

2. Lin , W.Y. , Lin , G.Y. , Wei , H.Y.: Dynamic Auction Mechanism for Cloud Resource Allocation . IEEE (May 2010 )

3. Szymanski , B.: A Novel Auction Mechanism for Selling Time-Sensitive E -Services. IEEE

4. Asdemir , K. : Bidding patterns in search engine auctions ( 2006 )

5. Gamma , E. , Helm , R. , Johnson, R., Vlissides , J.: Design Patterns: Elements of Resusable Object-Oriented Software . Addison-Wesley Professional ( 1995 )

6. Henninger , S. , Corr^ea, V.: Software pattern communities Current practices and challenges . In: Proceedings of the 14th Conference on Pattern Languages of Programs (PLoP) . (September 2007 ) 2007

7. Kamp meyer, H., Zschaler , S. : Finding the pattern you need: The design pattern intent ontology . Lecture Notes in Computer Science 4735 ( 2007 ) 211

8. Henninger , S. , Ashokkumar , P. : An Ontology-Based Metamodel for Software Patterns . at 18th Int. Conf. on Software Engineering . . . ( 2006 )

9. Montero , S. , D az, P., Aedo , I. : Formalization of web design patterns using ontologies . Lecture Notes In Computer Science ( 2003 ) 179 { 188

10. Harb , D. , Bouhours , C. , Leblanc , H.: Using an Ontology to Suggest Software Design Patterns Integration . Lecture Notes In Computer Science ( 2009 ) 318

11. Iglesias , C.A. , Garijo , Fernandez-Villamor, J.I. , Duran , J.J.: Agreement patterns . In: Proceedings of the CAEPIA09 Workshop on Agreement Technologies(WAT 2009 ), Sevilla, WAT09 - CAEPIA09 (November)

12. Noy , N.F. , McGuinness , D. : Ontology Development 101: A Guide to Creating your First Ontology . Technical Report SMI-2001-0880 , Stanford Medical Informatics, Stanford ( 2001 )

13. Dignum , V. , Vazquez-Salceda , J. , Dignum , F. In: Omni: Introducing social structure, norms and ontologies into agent organizations . Springer-Verlag, New York ( 2005 ) 181 { 198

14. Tamma , V. , Wooldridge , M. , Dickinson , I.: An ontology based approach to automated negotiation . In Padget, J.A. , Shehory , O. , C. Parkes , D. , Sadeh , N.M. , Walsh , W.E., eds.: Agent Mediated Electronic IV. Designing Mechanisms and Systems . AAMAS 2002 Workshop on agent mediated electronic commerce (AMEC IV), held at the AAMAS 02 conference , Bologna, Springer Verlag ( 2002 ) 219 { 237

15. Tamma , V. , Phelps , S. , Dickinson , I. , Wooldridge , M. : Ontologies for supporting negotiation in e-commerce . Engineering Applications of Arti cial Intelligence 18 ( 2 ) ( March 2005 ) 223 { 236

16. Paschke , A. , Kiss , C. , Al-Hunaty , S.: NPL: Negotiation Pattern Language. economics and management ( 2005 )

17. Re , R. , Braga , R. , Masiero , P.: A pattern language for online auctions management . Proceedings of PLoP ( 2001 )

18. Wellman , M. , Wurman , P. , O'Malley , K. , Bangera , R. , Lin , S.d. , Reeves , D. , Walsh , W. : Designing the market game for a trading agent competition . IEEE Internet Computing 5 ( 2 ) ( 2001 ) 43 { 51

19. Oluyomi , A.O. : Patterns and Protocols for Agent-Oriented Software Development . PhD thesis , Faculty of Engineering. University of Melbourne, Australia. (November 01 2006 )

20. Jureta , I. , Kolp , M. , Faulkner , S. , Do , T.T.: Patterns for Agent Oriented e-Bidding Practices . In: Proceedigns of 9th International Conference on Knowledge-Based Intelligent Information and Engineering Systems (KES 2005 ), Part IIKES (2) , Melbourne,Australia ( 2005 ) 814 { 820

21. Koolmanojwong , S. , Jiamthapthaksin , R. , Daengdej , J.: An agent architecture for competitive application environment . Aerospace Conference , 2004 . Proceedings. 2004 IEEE 3079{3089

22. Vytelingum , P. , Cli , D. , Jennings , N.R. : Strategic bidding in continuous double auctions . Arti cial Intelligence 172 ( 14 ) ( 2008 ) 1700 { 1729

23. Stanford Center for Biomedical Informatics Research: Protege ontology editor and knowledge acquisition system . http://protege.stanford.edu/ ( 2006 )

24. Nishino , N. , Fukuya , K. , Ueda , K. : Service Design in Movie Theaters Using Auction Mechanism with Seat Reservations

25. Edelman , B. , Ostrovsky , M. : Strategic bidder behavior in sponsored search auctions . Decision Support Systems 43 ( 1 ) ( 2007 ) 192 { 198

26. Harb , D. , Bouhours , C. , Leblanc , H.: Using an ontology to suggest software design patterns integration . In Chaudron, M., ed.: Models in Software Engineering.