42311875
A buyers integration support system in group buying
In electronic marketplaces, group buyings are seen as an effective form of electronic commerce and a promising field for applying agent technologies. We study decision support systems for buyers in group buying. In group buying, when buyers cooperate with each other, a seller can discount the price of a good. In many existing group buying sites, some sellers deal in the same sort goods or their imitations. Buyers form coalitions for each item on sale. Buyers cannot always purchase goods at a lower price, because buyers' sub-groups are distributed. Buyers need to search hard to find the goods they can purchase. In this paper, we propose a group buying marketplace on the Internet. In our marketplace, buyers can purchase goods at a lower price by forming coalitions. Our system can provide a service that buyers are integrated based on buyers' multi-attribute preferences (utilities). Our system supports buyers' decision making by using the analytic hierarchy process. We propose three methods for group integration. First, buyers trades on simple group buying. Second, all buyers are integrated. Third, some buyers are integrated. Advantages of our market can be described that buyers' multi-attribute utilities are reflected effectively in group integration and buyers can purchase goods at a lower price. Buyers' payments are decided based on their degree of compromise. A successful seller can sell goods in their stock.
39290569
Implementing a proxy agent based writable web for a dynamic information sharing system
In this paper, we propose a Web based information sharing system called the Proxy Agent-based Information Sharing(PAIS).We also developed a writable Web mechanism called Web browser-based Direct Editing (Wedit), that is a major component of PAIS. Wedit enables public users to effectively edit HTML text on an existing Web browser. Since Wedit was developed with conventional technologies, users quickly learn how to use it. PAIS is implemented by using Wedit and a proxy agent. PAIS enables users to share information via Web pages using Wedit. The proxy agent maintainsusers' editing data. The agent autonomously sends its user's modification data to other agents in the same community. In PAIS, certain confidential information in the community is not publicly shared by using the proxy agent.
13087182
A Logic-based Framework for Mobile Intelligent Information Agents
Information agents are computational software systems that provides transparent access to many different information sources in the Internet, and to be able to retrieve, analyze, manipulate, and integrate heterogeneous data and information on demand. Mobile agents are an effective choice for many applications to improve latency and bandwidth of client-server applications and to reduce vulnerability to network disconnection. In this paper, we propose MiLog, a logic-based mobile agent framework for constructing intelligent information agents. In the framework, inference and planning process of an agent is written in a compact logic program. A new generation logic program execution engine provides strong migration capability with reasonable execution speed. The framework has been used to develop a web-based decision support system ’BiddingBot’.
20000085
Toward a Large Scale E-Market: A Greedy and Local Search Based Winner Determination
Combinatorial auction is one of the most popular market mechanisms and it has a huge effect on electronic markets and political strategies. On large scale e-markets, we need a good approximation algorithm for winner determination that is robust for changing the distribution and the number of bids in an auction. We proposed approximate algorithms for combinatorial auctions with massively large number of (more than 100,000) bids. In this paper, we show the robustness of our winner determination algorithms for combinatorial auctions with large number of bids. Experimental results demonstrate that our proposed algorithms are robust on changing the distribution and the number of bids in an auction. Finally, we shortly describe a theoretical limitation about our algorithms that concerns with giving truthfulness of the auction mechanism.
2241033
Multiple negotiations among agents for a distributed meeting scheduler
We present a method for multi-agent negotiation for implementing a distributed meeting scheduler. In the meeting scheduler, an agent negotiates with other agents about making a public schedule by referring user's private schedules and preferences. We propose a new persuasion method for multi-agent negotiation for reflecting private preferences. We call the method multiple negotiations. In order to reach a consensus effectively, we propose an effective preference revision mechanism based on the multi attribute utility theory. We have implemented a distributed meeting scheduler to show how effectively the multiple negotiations can be used. The result shows that the multiple negotiations are effective in supporting group decision-making for scheduling a meeting.
35506309
Scheduling Meetings with Distributed Local Consistency Reinforcement
40835687
Partitioning trees of supply and demand
Assume that a tree T has a number ns of "supply vertices" and all the other vertices are "demand vertices." Each supply vertex is assigned a positive number called a supply, while each demand vertex is assigned a positive number called a demand. One wishes to partition T into exactly ns subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in the subtree. The "partition problem" is a decision problem to ask whether T has such a partition. The "maximum partition problem" is an optimization version of the partition problem. In this paper, we give three algorithms for the problems. The first is a linear-time algorithm for the partition problem. The second is a pseudo-polynomial-time algorithm for the maximum partition problem. The third is a fully polynomial-time approximation scheme (FPTAS) for the maximum partition problem.
43460576
Partitioning graphs of supply and demand
Assume that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive integer, called a supply or a demand. Each demand vertex can receive "power" from at most one supply vertex. One thus wishes to partition G into connected components by deleting edges from G so that each component C has exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in C. If G has no such partition, one wishes to partition G into connected components so that each component C either has no supply vertex or has exactly one supply vertex whose supply is no less than the sum of demands in C, and wishes to maximize the sum of demands in all components with supply vertices. We deal with such a maximization problem, which is NP-hard even for trees and strong NP-hard for general graphs. In this paper, we give a pseudo-polynomial-time algorithm to solve the problem for series-parallel graphs. The algorithm can be easily extended for partial k-trees, that is, graphs with bounded tree-width.
13514702
Partitioning a Multi-weighted Graph to Connected Subgraphs of Almost Uniform Size
Assume that each vertex of a graph G is assigned a constant number q of nonnegative integer weights, and that q pairs of nonnegative integers li and ui, 1 ≤i ≤q, are given. One wishes to partition G into connected components by deleting edges from G so that the total i-th weights of all vertices in each component is at least li and at most ui for each index i, 1 ≤i ≤q. The problem of finding such a “uniform” partition is NP-hard for series-parallel graphs, and is strongly NP-hard for general graphs even for q = 1. In this paper we show that the problem and many variants can be solved in pseudo-polynomial time for series-parallel graphs. Our algorithms for series-parallel graphs can be extended for partial k-trees, that is, graphs with bounded tree-width.
2226240
Partitioning Trees of Supply and Demand
Assume that a tree T has a number ns of "supply vertices" and all the other vertices are "demand vertices." Each supply vertex is assigned a positive number called a supply, while each demand vertex is assigned a positive number called a demand. One wish to partition T into exactly ns subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in the subtree. The "partition problem" is a decision problem to ask whether T has such a partition. The "maximum partition problem" is an optimization version of the partition problem. In this paper, we give three algorithms for the problems. First is a linear-time algorithm for the partition problem. Second is a pseudo-polynomial-time algorithm for the maximum partition problem. Third is a fully polynomial-time approximation scheme (FPTAS) for the maximum partition problem.
11122815
Algorithms for the Multicolorings of Partial k-Trees
Let each vertex v of a graph G have a positive integer weight ?(v). Then a multicoloring of G is to assign each vertex v a set of ?(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.