A Virtual Property Agency: Electronic Market with Support of Negotiation
Jiuru Hu, Jerome Yen, Alan Chung
jrhu@cs.hku.hk, jyen@sc.cuhk.edu.hk, klchug@cs.hku.hk
Long paper (4 to 10 pages)

To have an efficient and reliable infrastructure is crucial to any electronic market. Most existing electronic markets only provide limited services, such as, communication supports between buyers and sellers, databases to increase the selections, and market information to help estimation of reasonable transaction prices. In this paper, we propose a new electronic market, an Internet-based clearinghouse with a set of agents to support coordination, negotiation, and settlement with both numerical data and textual information. We have developed a Virtual Property Agent for highly uncertain and dynamic markets. Such approach is extremely helpful to markets that have complicated negotiation process or require more expertise, such as, real estate or used car.

KRAFT: Supporting Virtual Organisations through Knowledge Fusion
Alun Preece, Kit Hui and Peter Gray
apreece@csd.abdn.ac.uk
Long paper (4 to 10 pages)

The formation and operation of dynamic and open virtual organisations is a central concern in business-to-business e-commerce. Virtual organisations enable partner companies to develop and manufacture customised products with low costs and rapid delivery. Agent-based architectures are an effective platform for such virtual organisations because they provide mechanisms to allow organisations to advertise their capabilities, exchange rich information, and synchronise workflows at a high-level of abstraction. In this paper, we examine the KRAFT architecture and its features for supporting virtual organisations. In particular, we focus upon KRAFT's use of constraints as a knowledge exchange medium, and show how constraint fusion supports the design of customised products.

A CSP-based Model for Integrated Supply Chains
Rongming Sun, Bei-Tseng (Bill) Chu, Robert Wilhelm, Jian Yao
{rsun, billchu, rgwilhel, jyao}@uncc.edu
Long paper (4 to 10 pages)

Supply Chain Integration is a very important problem for business to business electronic commerce. An integrated supply chain allows businesses to share real-time information and drastically reduce transaction costs. This paper describes our efforts to model the order selection and negotiation process as a multi-agent system based on Constraint Satisfaction Problems (CSP). A negotiating agent can represent each company along the supply chain. The core capabilities of such agents can be modeled as a set of CSPs. These agents can generate a purchase plan to meet the company's demands. Negotiation will be triggered when no satisfactory plan can be found. Strategies are identified to relax some of the constraints to generate counter proposals.

A Limitation of the Generalized Vickrey Auction in Electronic Commerce : Robustness against False-name Bids
Yuko Sakurai, Makoto Yokoo and Shigeo Matsubara
{yuko,yokoo,matsubara}@cslab.kecl.ntt.co.jp
Extended abstract (2 pages)

Electronic Commerce has rapidly grown with the expansion of the Internet. Among these activities, auctions have recently achieved huge popularity, and have become a promising field for applying agent and Artificial Intelligence technologies. Although the Internet provides an infrastructure for much cheaper auctioning with many more sellers and buyers, we must consider the possibility of a new type of cheating, i.e., an agent tries to get some profit by submitting several bids under fictitious names (false-name bids). Although false-name bids are easier to execute than forming collusion, the vulnerability of auction protocols to false-name bids has not been discussed before. In this paper, we examine the robustness of the generalized Vickrey auction (G.V.A.) against false-name bids. The G.V.A. has the best theoretical background among various auction mechanisms, i.e., it has proved to be incentive compatible and be able to achieve a Pareto efficient allocation. We show that false-name bids may be effective, i.e., the G.V.A. loses incentive compatibility under the possibility of false-name bids, when the marginal utility of an item increases or goods are complementary. Moreover, we prove that there exists no single-round sealed-bid auction protocol that simultaneously satisfies individual rationality, Pareto efficiency, and incentive compatibility in all cases if agents can submit false-name bids.

Smart clients: Constraint satisfaction as a paradigm for scaleable intelligent information systems
Marc Torrens i Arnal and Boi Faltings
torrens@lia.di.epfl.ch, faltings@lia.di.epfl.ch
Long paper (4 to 10 pages)

Many information systems are used in a problem solving context. Examples are travel planning systems, catalogs in electronic commerce, or agenda planning systems. They can be made more useful by integrating problem-solving capabilities into the information systems. This poses the challenge of scaleability: when hundreds of users access a server at the same time, it is important to avoid excessive computational load.

We present the concept of smart clients: lightweight problem-solving agents based on constraint satisfaction which can carry out the computation- and communication-intensive tasks on the user's computer. We present an example of an air travel planning system based on this technology.

Real-world Requirements for Natural Language Interfaces
Mallory Selfridge
mal@engr.uconn.edu
Extended abstract (2 pages)

Real-world Requirements for Natural Language Interfaces for E-Commerce Mallory Selfridge Department of Computer Science and Engineering University of Connecticut Storrs, CT 0624

As e-commerce continues to expand, the potential utility of natural language communication with e-commerce applications becomes increasingly apparent. While clickable web pages will continue to support the great majority of e-commerce interactions for some time to come, increasing numbers of on-line customers want to speak with a person. If a natural language interface could successfully assume some of this customer-service burden, requirements for human staff would be reduced. This extended abstract considers several of the issues that must be addressed in order for such natural language interfaces to be deployed in real-world applications

Congregation FOrmation in Information Economies
Christopher H. Brooks and Edmund H. Durfee
chbrooks@umich.edu, durfee@umich.edu
Long paper (4 to 10 pages)

In a large-scale multiagent system, agents that need to interact with other agents are faced with a combinatorially explosive number of potential interactions. One way for agents to deal with this complexity is to form congregations. As in human society, congregations provide a common meeting-place for agents with compatible needs or preferences. We discuss two approaches to inducing congregations to form in a general multiagent system: external mechanisms and internal learning. We then examine a particular multiagent system, an information economy, in more detail, and discuss the relationship between bundling of information goods and the formation of congregations. By viewing the problem of determining the optimal bundling strategy as a problem of congregation formation, new techniques, such as ontological information about consumer preferences and goods, may be brought to bear. We also present some preliminary experimental results regarding both the conditions which lead to optimal congregation formation and the ability of a producer to learn some simple preferences of a congregation.

Congregation Formation in Information Economies
Christopher H. Brooks and Edmund H. Durfee
chbrooks@umich.edu, durfee@umich.edu
Long paper (4 to 10 pages)

In a large-scale multiagent system, agents that need to interact with other agents are faced with a combinatorially explosive number of potential interactions. One way for agents to deal with this complexity is to form congregations. As in human society, congregations provide a common meeting-place for agents with compatible needs or preferences. We discuss two approaches to inducing congregations to form in a general multiagent system: external mechanisms and internal learning. We then examine a particular multiagent system, an information economy, in more detail, and discuss the relationship between bundling of information goods and the formation of congregations. By viewing the problem of determining the optimal bundling strategy as a problem of congregation formation, new techniques, such as ontological information about consumer preferences and goods, may be brought to bear. We also present some preliminary experimental results regarding both the conditions which lead to optimal congregation formation and the ability of a producer to learn some simple preferences of a congregation.

DIVA: Applying Decision Theory to Collaborative Filtering
Hien Nguyen and Peter Haddawy
hien@lombok.cs.uwm.edu, haddawy@cs.uwm.edu
Long paper (4 to 10 pages)

This paper describes DIVA, a decision-theoretic agent for recommending movies that contains a number of novel features. DIVA represents user preferences using pairwise comparisons among items, rather than numeric ratings. It uses a novel similarity measure based on the concept of the probability of conflict between two orderings of items. The system has a rich representation of preference, distinguishing between a user’s general taste in movies and his immediate interests. It takes an incremental approach to preference elicitation in which the user can provide feedback if not satisfied with the recommendation list. We empirically evaluate the performance of the system using the EachMovie collaborative filtering database.

Auctions without Common Knowledge
Sviatoslav Brainov, Tuomas Sandholm
brainov@cs.wustl.edu, sandholm@cs.wustl.edu
Extended abstract (2 pages)

This paper proves that the revenue equivalence theorem ceases to hold for auctions without common knowledge about the agents' prior beliefs. That is, different auction forms yield different expected revenue. To prove this, an auction game is converted to a Bayesian decision problem with an infinite hierarchy of beliefs. A general solution for such Bayesian decision problems is proposed. The solution is a generalization of the standard Bayesian solution and coincides with it for finite belief trees and for trees representing common knowledge. It is shown how the solution generalizes the frequently used technique of backward induction for infinite belief trees. The solution can be applied to any game with infinite belief trees. Computation of the solution does not rely on approximating the infinite trees with finite ones. The method can be used, for example, to analyze the expected revenue of alternative auction forms.

eMediator: A Next Generation Electronic Commerce Server
Tuomas Sandholm
sandholm@cs.wustl.edu
Long paper (4 to 10 pages)

This paper presents eMediator, a next generation electronic commerce server that demonstrates some ways in which AI, algorithmic support, and game theoretic incentive engineering can jointly improve the efficiency of ecommerce. First, its configurable auction house includes a variety of generalized combinatorial auctions, price setting mechanism, novel bid types, mobile agents, and user support for choosing an auction type. Second, its leveled commitment contract optimizer determines the optimal contract price and decommitting penalties for a variety of leveled commitment contracting protocols, taking into account that rational agents will decommit insincerely in Nash equilibrium. Third, its safe exchange planner enables unenforced anonymous exchanges by dividing the exchange into chunks and sequencing those chunks to be delivered safely in alternation between the buyer and the seller. Each of the three components is based on different types of game theoretic equilibrium analysis, and also required development of new algorithms and GUI designs to make it feasible.

Matchmaker Agents for Electronic Commerce
Eugene C. Freuder and Richard J. Wallace
ecf@cs.unh.edu, rjw@cs.unh.edu
Research statement (2 pages)

Matchmaking agents facititate interaction between customers and vendors. In this work we view Matchmakers as constraint-based solvers. A Matchmaker of this type provides potential solutions ("suggestions") based on partial knowledge, while gaining further information about the problem from the Customer through the latter's evaluation of these suggestions ("corrections"). The dialog between Matchmaker and Customer results in iterative improvement in the quality of the solution presented to the Customer. For example, a used-car Matchmaker might suggest a reliable Toyota Camry, switch to a mini-van when told the Camry was too small because the customer had 12 children, and to a 1965 VW bus when told the customer had already spent most of his money on the children. There are a variety of metrics by which we can evaluate the success of a customer/vendor interaction. For example, the vendor may wish to minimize the time spent with customers to maximize immediate sales volume, or the vendor may wish to maximize the information obtained from customers, to facilitate an ongoing relationship. We have explored different strategies for presenting proposed solutions to the customer, and evaluated these strategies according to different success metrics. Constraint technology provides a natural mechanism for combining customer problem solving with customer profiling. The suggestion/correction mechanism supports a natural interactive dialogue, and allows for upselling. We are combining this work with our expertise in the area of product configuration. Opportunities may exist as well to combine this work with the wider use of constraint technology in enterprise and supply chain management.

Agent Service for Online Auctions
Junling Hu, Daniel Reeves and Hock-Shan Wong
junling@umich.edu,dreeves@umich.edu,hswong@umich.edu
Long paper (4 to 10 pages)

We have designed configurable agents to represent users in online auctions, specifically the Michigan AuctionBot. The agents can be configured, started, and monitored from a web interface. We implemented three types of agents, distinguished by their different ways of using information in the auctions. A competitive agent does not use any information in the auction market. It chooses its actions based on its individual optimization problem. A price modeling agent uses price history as its only information. A bidder-modeling agent uses other agents' bidding histories to predict their next bids and infer the next clearing price. Our experiments suggest that an agent's performance in the auctions depends not only on its bidding strategy, but also on the bidding strategies of others. When all the agents behave strategically they may reach a sub-optimal equilibrium, in which they receive worse payoffs than behaving competitively.

Toward a Declarative Language for Negotiating Executable Contracts
Daniel M. Reeves, Benjamin N. Grosof, Michael P. Wellman, and Hoi Y. Chan
dreeves@umich.edu, grosof@us.ibm.com, wellman@umich.edu, hychan@us.ibm.com
Long paper (4 to 10 pages)

We give an approach to automating the negotiation of business contracts. Our goal is to develop a language for both (1.) fully-specified, executable contracts and (2.) partially-specified contracts that are in the midst of being negotiated, including via automated auctions. Our starting point for this language is Courteous Logic Programs (CLP's), a form of logic-based knowledge representation (KR) that is semantically declarative, intuitively natural, computationally tractable, and practically executable. A CLP is suitable in particular to represent a fully-specified executable contract. The basic CLP KR also facilitates modification during negotiation, because it includes prioritized conflict handling features that facilitate modification. Beyond the basic CLP KR, we have developed an initial ontology, and an associated style of representation, to specify additional aspects of a partial contract and of a negotiation process. The initial ontology specifies the set of negotiables and the structure of a contract in terms of its component goods/services and attributes. Specifying the negotiable aspects of a good or service includes specifying its attributes, their possible values, and dependencies/constraints on those attributes. Building upon the representation of these negotiable aspects, we are in current work developing methods to structure negotiations, especially to select and configure auction mechanisms to carry out the negotiation. This work brings together two strands of our previous work on business process automation in electronic commerce: representing business rules shared between enterprises, and configurable auction mechanisms.

A New Internet Agent Scripting Language Using XML
Danny B. Lange, Tom Hill, Mitsuru Oshima
danny@acm.org
Long paper (4 to 10 pages)

Java and other system programming languages are not ideal for software agent development on the Internet. We have found it very challenging to produce reliable yet lightweight agent systems. Even basic agents often require colossal amounts of highly complex code. We are addressing this issue by new agent scripting language and an associated execution environment. Taken together, these two developments provide a number of benefits to agent developers and users. Once the user learns the scripting language, he or she will be able to produce personal and enhanced agents. The scripting language supports rapid development since it allows programming at a much higher level than Java. It makes it easy to manipulate information in the XML format. Since the language is open-ended, it can also be easily extended with new tags written in the Java programming language.

Equilibrium Prices in Bundle Auctions
Peter R. Wurman, Michael P. Wellman
pwurman@umich.edu, wellman@umich.edu
Long paper (4 to 10 pages)

The allocation of discrete, complementary resources is a fundamental problem in economics and of direct interest to e-commerce applications. In this paper we establish that competitive equilibrium bundle prices always exist that support the efficient allocation in discrete resource allocation problems with free disposal. We believe that this is an important step in the quest for a mechanism that performs well in the face of complementary preferences. We present a family of auctions that use this bundle pricing policy, and make some initial observations on several of its members, including the new Ascending k-Bundle auction.

Ontologies for Electronic Commerce
Deborah L. McGuinness
dlm@ksl.stanford.edu
Long paper (4 to 10 pages)

Electronic commerce is exploding - Forrester research projects 25 billion dollars in online spending by the year 2000. As the market segment grows, it has expanded into broader content areas. Broader domains increase the need for thoughtful content organization and browsing support. We promote the trend of using ontologies to support more than just search and also to to enhance browsing and more active "smart" notification services. In this paper, we identify some of the issues with respect to existing ontology-enhanced e-commerce applications, report and discuss findings from our own experiences building and using ontologies for web deployments in general and e-commerce specifically, identify some "low-hanging fruit" applications, and discuss some research directions

Intelligent Decision Support for the e-Supply Chain
Richard Goodwin, Pinar Keskinocak, Sesh Murthy, Frederick Wu, Rama Akkiraju
rgoodwin@watson.ibm.com, keskinocak@watson.ibm.com, murthy@watson.ibm.com
Long paper (4 to 10 pages)

Much of the attention in artificial intelligence (AI) for e-Business has focused on business to consumer transactions. Shopping bots, systems to recommend movies and books based on similar opinions by other users and news filtering agents, are just some examples. However, we feel that AI can have a larger impact on the supply chain that delivers goods and services to the end consumer. Reductions in costs and the pervasiveness of the Internet have encouraged companies to move towards using e-commerce for transactions with their business partners. Companies are willing to invest resource because of the reduced product cycle times and the lower transaction costs that they expect. A result of this movement is that companies can afford to interact with a larger number of trading partners and form project and customer specific partnerships that would have been too costly in the past. To manage a larger and more dynamic set of partnerships and to be able to take advantage of transient opportunities, business users will need decision-support systems to identify and analyze the opportunities in terms of their business objectives. In this paper, we describe our agent-based decision-support framework for creating systems to support trading partners in the e-supply chain. In particular, we will focus on the issues that need to be addressed in order to create a viable and useful decision-support system.

Applying AI to Manufacturing: Linear Order Promising and Production Planning
Yury Smirnov
ysmirnov@calicotech.com
Long paper (4 to 10 pages)

Many vertical industries within Manufacturing have already entered or are about to enter a new era of mass-customization. Customers expect improved level of service, precise price and date quotes for their personalized orders. Internet communications in general and dedicated e-commerce efforts in particular greatly facilitated the process of taking orders and shipping the requested products to anticipating customers. However, precise, scalable and effective Order Promising and Production Planning still constitute serious challenges for manufacturers.

Specialists in Manufacturing Modeling have already identified the deficiencies of the existing approaches that traditionally split production models into Bills of Materials (BOMs) and Routings (E.Goldratt, 90). Whereas Artificial Intelligence (AI) understood long ago the benefit of merging states and actions in a combined planning model, an alternative, constructive solution to the BOM/Routing modeling approach has not been explicitly proposed.

Re-configurable products may lead to an exponential explosion of the number of BOMs, if the standard modeling approach of listing all orderable products is followed. Another complication may come from the existence of alternative routings, which are different production processes (actions) that produce the same inventory items (lead to the same states). A selection of a different route may imply substituting already selected group of inventory items by a different group of items, for example, changing a monitor type for PC may require a different video card, which in its turn may need an upgrade of the power supply module. The above feature is called "kitting" in Manufacturing Modeling.

On one hand, a complicated nature of Manufacturing Modeling and a need to capture the AND/OR-logic in presenting inventory items and alternative routings makes it hard to efficiently derive precise price and date quote (Order Promising) and to construct the entire schedule (Production Planning). On the other hand, customers' expectations and a broad spectrum of orderable products state an urgent need for scalable Order Promising and Production Planning functionalities.

In this paper we introduce novel modeling approach that applies some AI modeling techniques to Manufacturing Modeling, allows to avoid the exponential blow-up for re-configurable products and captures the AND/OR-logic without additional modeling efforts. Furthermore, we state a simple, realistic resource sharing assumption. For the introduced type of models, we construct Order Promising and resource allocation (scheduling) procedures that are linear under the stated assumption for any homogeneous objective function.

Integrating Knowledge-based and Collaborative-filtering Recommender Systems
Robin Burke
burke@ics.uci.edu
Long paper (4 to 10 pages)

Knowledge-based and collaborative-filtering recommender systems facilitate electronic commerce by helping users find appropriate products from large catalogs. This paper discusses the strengths and weaknesses of both techniques and introduces the possibility of a hybrid recommender system that combines the two approaches. An approach is suggested in which knowledge-based techniques are used to bootstrap the collaborative filtering engine while its data pool is small, and the collaborative filter is used as a post-filter for the knowledge-based recommender.

Analysis of the Axiomatic Foundations of Collaborative Filtering
David M. Pennock and Eric Horvitz
dpennock@umich.edu, horvitz@microsoft.com
Long paper (4 to 10 pages)

The growth of Internet commerce has stimulated the use of collaborative filtering (CF) algorithms as recommender systems. Such systems leverage knowledge about the behavior of multiple users to recommend items of interest to individual users. CF methods have been harnessed to make recommendations about such items as web pages, movies, books, and toys. Researchers have proposed several variations of the technology. We take the perspective of CF as a methodology for combining preferences. The preferences predicted for the end user is some function of all of the known preferences for everyone in a database. Social Choice theorists, concerned with the properties of voting methods, have been investigating preference aggregation for decades. At the heart of this body of work is Arrow's result demonstrating the impossibility of combining preferences in a way that satisfies several desirable and innocuous-looking properties. We show that researchers working on CF algorithms often make similar assumptions. We elucidate these assumptions and extend results from Social Choice theory to CF methods. We show that only very restrictive CF functions are consistent with desirable aggregation properties. Finally, we discuss practical implications of these results.

Controlling Supplier Selection in an Automated Purchasing System
Pedro Szekely, Bob Neches, David P. Benjamin, Jinbo Chen, and Craig Milo Rogers
szekely@isi.edu, neches@isi.edu, benjamin@isi.edu, (jinbo, rogers)@isi.edu
Long paper (4 to 10 pages)

We present a system called DEALMAKER that allows users to specify policies that control selection among preferred suppliers in an automated purchasing system. The system gives users control over the automation by providing an expressive language and a convenient, easy-to-use user interface to specify the policies. The interesting and challenging aspect of the problem arises from the context in which the system operates. The end users are contract managers and buyers who are not trained in computers or programming. They enter their new supply contracts and define policy rules to control selection of the best contracts for buying requested parts. They act as their own knowledge engineers, even though the system is expected to have hundreds of rules for hundreds of contracts. The users interact with the system infrequently, perhaps only a few times a month when they begin or modify contracts, or change policies. Along with a moderate turnover rate of users, this makes it crucial that they can easily maintain correct rules with minimal training. In this paper, we describe a rule system and an interactive rule authoring tool designed to address the problems raised by this context. We believe these issues arise in most application domains where rule systems are put in the hands of the end users.

Recommender Systems for E-Commerce: Challenges and Opportunities
Robert Driskill and John Riedl
rdriskill@netperceptions.com, riedl@netperceptions.com
Long paper (4 to 10 pages)

Recommender systems are an AI technology that has become an essential part of business for many E-commerce sites. They serve many types of E-commerce applications, from direct product recommendation for an individual to helping someone find a gift for a third party. In this paper, we provide a brief overview of how recommender systems are being used in E-commerce today, and analyze four key challenges for recommender systems in the future: hybrid data, predictable recommendations, scalability, and incorporation of content. If recommender systems are able to surmount these challenges, they have the potential to become an essential component of doing business in E-commerce.

Insights into the Design of Middle Agent Architectures: The Case of Multi-Agent Information Extraction
C. Curtis Cartmill and Robin Cohen
cccartmill@newlogos.uwaterloo.ca, rcohen@watdragon.uwaterloo.ca
Research statement (2 pages)

This paper describes our work on the acquisition of extraction patterns for an Information Extraction problem. In particular, we introduce a multi-agent architecture, identifying several possible middle agents, to allow agents representing users with similar interests to share knowledge. This research provides general insights into the value of user profiling, intelligent filtering and social responsibility, all of which may be important in e-commerce applications.

xxx
xxx

Position statement (2 pages)

this is a test to see if I can send this document from this site

Electronic Commerce is an Intriguing Domain for AI Learning Theory
Leona F. Fass

Research statement (2 pages)

As a theoretician investigating behavioral modeling and learning we devise gedanken-experiments to analyze those EC systems that we daily employ. For positive EC learning we identify (potentially) successful constructive deployments. These might involve reactive agents with goal-oriented behavior, or the design of cooperating agents and federated agent systems that solve EC problem components (as needed) autonomously or interactively. For adversarial EC learning we describe correctable problems and perils detected in EC systems already deployed. We identify a need for adequate system testing; a need for protection- , back-up- and integrity-preserving-agents; and security, privacy and legal issues that might be alleviated with the development of an appropriate browsing agent and a really smart cookie.

IntelliServe™: Automating Customer Service
Yannick Lallemant & Mark S. Fox
yannick@novator.com, msf@eil.utoronto.ca
Long paper (4 to 10 pages)

As the amount of electronic commerce continues to increase, demand for customer service outstrips the ability of organizations to respond quickly, correctly and profitably. This paper describes IntelliServe™, an Artificial Intelligence approach to automatic message classification and response generation. The goal of automated response generation for customer service is to provide an immediate, relevant, consistent and cost effective response to at least 50% of customer queries. Using adaptable Bayesian techniques, IntelliServe is able to correctly respond to at least 65% of customer comments.

Negotiating Agents for Supply Chain Management
Ye Chen, Yun Peng, Tim Finin, Yannis Labrou, and Scott Cost
yechen@cs.umbc.edu, ypeng@umbc.edu, finin@um, jklabrou, rcost1@cs.umbc.edu
Extended abstract (2 pages)

We discuss a framework for using negotiating agents in a supply chain management system.

Extended abstract (2 pages)