 |
Wolfram Conen
Xonar Gmbh,Velbert, Germany
Conen@gmx.de
Fredj Dridi, Eckhart Köppen
Information Systems and Software Techniques
University of Essen,
Universitätsstraße 9, D-45141 Essen, Germany
{Fredj.Dridi,Eckhart.Koeppen}@uni-essen.de
Published in: Proc. of WETICE2000, IEEE 9th Intl. Workshops on
Enabling Technologies: Infrastructure for Collaborative Enterprises, June 2000.
The approach is based on bundled-goods auctions and allows to achieve a high degree of analysability, economic efficiency and usability. The resource allocation service is implemented in Java based on the exchange of XML messages. The utilized schemata are expressed using XML DTDs as a lowest common denominator. This seems to be an important prerequisite to ensure interoperability with emerging standards in E-commerce whilst it still provides the necessary flexibility to adapt the solution to future needs.
For development and implementation of the allocation service, utilizing (secure) agents seemed to be a natural choice regarding the fact that the cooperating partners are economically autonomous and thus want (1) to keep some of their data/preferences private, (2) want to deploy a secure platform for the exchange of information and the computation of allocation and prices, and should have the freedom to code their needs and strategies into their coordination agents as required. The impact of infrastructure security and application specific trust considerations are briefly discussed, and finally, the key features of the presented resource allocation service are summarized.
The acceleration and automation of procurement processes seems to promise a huge potential to reduce costs and to allow for faster and more flexible exploitation of new market opportunities. It requires some form of standardization of document formats and means of data exchange. In addition, the integration with legacy ERP systems is required to streamline the procurement process and to utilize the benefits of format standardization.
With the advent of intermediaries, business-to-business relations will eventually be able to rely on platforms offering open or closed market services along with support for maintaining electronic catalogs, financial transactions via corporate procurement cards, integration with shipping services or, for example, tax services.
This diversity of services may ultimately allow suppliers to ``plug-in'' their extended ERP system into the infrastructure provided by intermediaries and to exploit the opportunities following from having direct access to a (potentially huge) market of buyers with its largely standardized exchange formats, coordination processes, and additional services.
Here, we denote with coordination processes, or, more precisely, a coordination mechanism, the means by which actual resource allocation decisions are made. For example, this may refer to the bidding, the final assignment of a price to a good and the allocation of the good to a certain customer in an open-cry English auction.
While simple coordination mechanisms such as standard (English, Dutch, sealed first-bid or Vickrey) auction or reverse auction procedures for one or for many uncoupled goods are easy to implement and to analyze with respect to the quality of the allocation decisions, allocation problems that exhibit complementarities are difficult to assess and to solve. However, such problems present an even greater potential for intermediaries to position them self in the B2B-infrastructure market:
We will describe a two-stage sealed-bid auction mechanism to deal with problems exhibiting complementarities below. But first, we will discuss the relevance of complementarities and outline a few application scenarios' calling for the utilization of such a (little more complex) coordination mechanisms.
Complementarities are present whenever the valuation of a good, a service, or an ``opportunity'' depends upon the availability of another good, service, or ``opportunity''. A well-known example is the allocation of start and landing slots to airlines - acquiring a start slot at 9:00 am in Singapore for a flight to Bangkok does not make much sense if there is no slot available for a landing in Bangkok between 11:00 and 12:00 am.1 Interdependent preferences for goods and services can be found nearly everywhere in logistics and production: JIT delivery requires the availability of products and of handling and shipping (and other) resources, manufacturing of components requires input from a variety of suppliers, customer care services consists of various stages (request handling, information generation, maintenance services, handling of returned goods etc.) - and each potential buyer of such complex goods/services wants to buy an optimal combination of the required partial services or goods. A platform for the flexible selling and buying of bundles/sub-bundles of goods and services would enable the participants to fully exploit the economic potential of complex services while preserving an extended possibility for competition (on both sides of the market). If a market for ``components'' exists, buyers may freely and easily exploit the possibility to combine components from a number of suppliers to their best benefit - instead of being forced to wait for the one ``big'' supplier offering just the optimal component configuration. Additionally, the suppliers can offer their goods and services in a way allowing them to exploit the effects of scales of economics or of efficiently combinable products/services.
Unfortunately (as have been mentioned already in the footnote to the slot example), traditional one-good auctions or even parallel, but otherwise independent multi-good auctions fail to deliver high-quality solutions to the economic allocation problem. A simple 2-agents, 2 goods example will demonstrate one of the key issues behind this observation (from [15], the numbers giving the valuations of the agents):
|
|
The optimal solution is to assign both goods to agent 1. However, the price of each individual goods must exceed 2 currency units to exclude agent 2 from the allocation-which in turn would prevent agent 1 from buying both goods because his valuation is below 4.
The solution here: both goods must be sold as a bundle to enable an efficient (i.e. surplus maximizing) solution of the allocation problem. This basic idea, with a lot of non-trivial consequences2, is the base for what follows.
Our prototype implements a two-stage, sealed-bid auction mechanism. In the first stage, each potential buyer and supplier will submit there bids resp. their reserve prices for each combination of goods or services they want to acquire The system will compute an optimal allocation of bundles of goods/services (and, hence, their suppliers) to buyers. The system will compute a price vector for all the bundles that will actually be exchanged between agents and will publish this vector. The vector will be a self-enforcing equilibrium price vector, i.e. each rational agent that solves his own revenue maximization problem will perform the trade that is part of the set of optimal trades - this is a very important fact if the participants are autonomous and can not be forced to accept allocation decisions, as is the case for the markets described here3. In general, the way the overall surplus is distributed among buyers and sellers should be agreed upon by the participants prior to running a market. There is room to minimize or maximize the buyer (or, resp., maximize or minimize the supplier) surplus within the boundaries set by the required equilibrium property. This, in turn, has a key influence on the incentives to (not) behave strategically for the different parties in the auction process. We assume that either the auctioneer announces the distribution quota (e.g. 50/50) or the participants unanimously instruct the auctioneer to distribute the surplus in a specified way.
Now, trade will take place and the efficient solution, i.e. the solution maximizing the sum of individual utilities will be implemented.
A simplified picture of the coordination mechanisms is shown in Figure 1. It looks as follows: Supplier and Buyer (Java agents in our implementation to be plugged into the individual ERP systems) contact a market place that trades goods they are interested to buy or sell based upon an XML [3] description of the market. The buyers submit their valuation for every bundle of goods/services they are interested in. The supplier submit their reservation values for every bundle they are able to supply. All submitted data is transferred as XML documents. After a specific time or after a specific number of bids is received, the coordinator instantiates a market, producing a complete XML description document. This document is passed to the auctioneer.
The auctioneer computes (complex tasks - mostly NP-hard!) the efficient (i.e. maximizing the sum of individual revenues) allocation and prices for the bundles to be exchanged and sends the information about bundling and prices to the buyers/suppliers. Each agent decides which trades he wants to perform and submits this information to the autioneer. The auctioneer informs the trade partners (after a feasibility check) accordingly.
During the auctioning process, the updated market data (bundling and pricing information) can be made available to third parties such as a supervisor to warrant fairness of the auction and neutrality of the auctioneer. These are security issues which are of special importance in an auctioning system. They are discussed below. The market data is published as an XML document, making changes of the supervisor implementation easier. Here, we propose an external supervisor that acts as a trusted third party, possibly offering the service of supervision of several auction sites to customers of these sites.
All information is passed over HTTP [9], implying a client/server architecture for the system.
We will now discuss the reasons that lead us to an XML-, HTTP- and Java-based implementation.
The market setup phase makes heavy use of XML to facilitate the communication between buyer, seller and the market. XML has proven to be a powerful tool for defining information structures and creating conforming documents. This ability is especially important in the scenario presented in this paper. Here, different parties with different needs, vocabularies and information need to communicate. We use XML and XML DTDs to provide a common ground for information exchange. In this context, a number of efforts have been made to create common vocabularies for electronic commerce, most important the Common Business Language (CBL) [7] and Commerce XML (cXML) [1], both XML-based. It is important to note that the usage of one vocabulary or schema for information exchange does not prohibit communication to partners using different schemata. Standards and tools associated with XML address this problem of interoperability, namely XML namespaces [4]. Architectural forms [13] and transformation mechanisms such as XSLT [5] can be used as a bridge between different information sources. Because of the availability of these mechanisms, we chose to implement our own vocabulary based on the characteristics of the presented auction scenario. It will be possible to transform incoming information structured using CBL, cXML or other formats to the structures used by the coordination and auctioning mechanisms.
The second mechanism to assure interoperability is the choice of HTTP as the underlying communication protocol. The different components and parties in the given scenario communicate strictly over HTTP, using GET and PUT requests to forward and request information and POST requests for remote method invocations. This reduces the need for special communication methods since HTTP has become a widely available protocol in many information systems, not at last due to its simplicity.
Going even further than just enabling parties with different information sets to communicate and trade, we open the actual market and auction process to external entities via XML. A first step in this direction has already been mentioned. The instantiated market is made available as an XML document, and the auctioneer relies on XML as an import format for the initial market data. Thus, the presented market setup and auction process implementations can be exchanged with other XML-enabled implementations.
The next step is the representation of the stages of the auction process itself as an XML document. As seen in Figure 1, this could be used to report the progress of the auction to external instances to supervise the fairness of the process or even back to the original parties for adjustments of bids during the auction. Furthermore, a representation of the process could lead to a customization or parameterization of the process by providing a sort of process template document describing characteristics of the underlying auctioning algorithm. This template document would be filled with actual data during the auction. A market place (for different markets) could thus be initialized using such a process description. However, a truly platform independent description of auction algorithms using XML does not seem feasible for complexity reasons. It seems more reasonable to provide building blocks for auctioning algorithms which can be combined and parameterized using process templates.
The actual implementation of the auction algorithms is done in Java which, designed to be a portable programming language, complements the role of XML as a portable data exchange format. Interfacing between the XML data on the one hand and the corresponding Java objects on the other hand can be achieved in a number of ways. It is possible to define XML DTDs that model the structure of Java objects closely, i.e. containing elements for class definitions, instance variables or even methods. Other ways make use of intermediate representations such as IDL to map between objects and transferred information. In contrast to this, we chose a different approach to improve transparency and interoperability. For us, not the Java objects but the information which is passed around is the foremost important component of the system. This requires modeling Java classes after XML DTDs, a task that can be automatized to a certain extent. To generate Java classes from DTDs, we implemented a simple tool called DTD2Java that converts elements declared in a DTD to Java classes with instance variables derived from the content model. Furthermore, serialization code for writing out and reading in XML representations is generated.
It is obvious that such a tool can only cover a subset of the expressibility of DTDs, e.g. mixed content models containing groupings, sequences, alternations and character data cannot be mapped easily to a class definition. We think that this is only a problem when the used DTDs cannot be modified. But even in this case, introducing intermediate DTDs and transformation between documents conforming to these different DTDs is possible using the techniques mentioned above.
In comparison, an interesting approach is taken by Quick [11], where the document structure is described using an intermediate structure definition language expressed in XML. The Java processing of the resulting documents is specified by adding special elements to the structure definition. However, we think that using simple XML DTDs provides for easier interoperability due to the already available tools than using dedicated schema languages which might not be processable in other systems.
The second important part of the implementation besides the interfacing between external and internal representation of the used data is the communications layer. Since we chose HTTP as the communication protocol, several implications for the system architecture arise. A model that provides the needed mechanisms (along with an implementation) is the Active Hypertext Document Model ([14]) which defines a peer-to-peer HTTP-based communications architecture where a combined client/server network node contains active (scripted) XML documents. This can be used to implement the market itself but also the data sinks and sources for the involved parties. We do not make use of the advanced features of the AHDM such as incorporating program fragments in the transferred XML documents, this area is however interesting for further investigation.
Typically, an auction application involves a large number of users, who want to share and grant access to documents (data) in a controlled way. Some of those documents may contain sensitive information and consequently must not be disclosed to every user. In addition, because the auction application uses the Internet as its transport mechanism, it inherits all of the security vulnerabilities of the Internet. As a result, the demand for security services (like authentication, access control, non-repudiation, etc.) has grown rapidly. See [8] for more details.
In general, if an application uses a network (e.g. Internet) as a communication infrastructure without appropriate attention paid to security, several network based security attacks may take place. These security attacks can be divided into two categories [16]: Passive attacks and Active attacks.
Passive attacks may threaten the confidentiality and can take place by intercepting the communication stream between the client and the server. The transmitted data can be eavesdropped (e.g. Bids data may be released) or monitored (e.g. market transactions may be analyzed).
Active attacks can take place by interrupting or modifying the communication stream between the communicating parties. An active attack threatens the availability and integrity of data being transmitted. An active attack may also threaten the confidentiality of identity (masquerading).
Figure 2 describes an architecture built up by the means of security services to shield against security threats and to achieve information security for networked systems like a Web based auction application.
The discussion of the implementation of the required, application-independent security services is well-known nowadays, below, we will briefly discuss the application context specific issues that had to be solved:
As mentioned above the market data is published as an XML document and will be deserialized into Java objects upon entering a Java running environment. Java objects will be also serialized to XML if they should be communicated. Due to this mapping between Java and XML some individual document security information (e.g. digital signature, access control information, etc.) could be unconsidered. Therefore, a special mechanism, which (de)serializes such security information, must be implemented in the next version of our prototype auction application.
The auction-based resource allocation service presented in this paper has the following key features.
We plan to practically deploy the implemented services and open them for public use. Since all communication is based on XML and it is easy to extend the developed DTDs to allow integration of e.g., catalogue data (in the bids) or order processing information (to execute the computed allocation) that are declared in emerging standards such as xCBL, the adoption of such services in common business practice will be possible without too much friction. We hope that the discussion in the workshop will help us to identify further possibilities and necessities. We also hope that our experience in implementing an innovative service in Java/XML might enable us to contribute to the workshop's result.
This document was generated using the LaTeX2HTML translator Version 99.2beta6 (1.42)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 -white -show_section_numbers -no_navigation ca.tex
The translation was initiated by koeppen on 2000-05-18
