8383423
A Support Method for Qualitative Simulation-Based Learning System
In this paper, we mainly present a support method of our proposed e-learning system. We employ qualitative simulations because this lets the learners understand the conceptual principles in economic dynamics. First, we define some qualitative values employed on simulation graph model that consists of nodes and arcs. Then, we show the support method using our learning system based on qualitative simulation.
37242657
A Strategy-Proof Mechanism Based on Multiple Auction Support Agents
Agent-mediated electronic commerce has recently commanded much attention. Bidding support agents have been studied very extensively. We envision a future in which many people can trade their goods by using a bidding support agent on Internet auctions. In this paper, we formalize a situation in which people are trading their goods on Internet auctions and employing bidding support agents. Then, we prove that people who use a bidding support agent can successively win trades. Also, we prove that the situation in which every people use a bidding support agent can satisfied strategy proofness and Pareto optimality. Further, we present in the situation, unsupported bidders do not make a positive benefit.
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.
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.
1779412
Designing an auction protocol under asymmetric information on nature's selection
Internet auctions are becoming an especially popular part of Electronic Commerce and auction protocols have been studied very widely in the field of multi-agent systems and AI. However, correctly judging the quality of auctioned goods is often difficult for non-experts (amateurs), in particular, on the Internet auctions. In this paper, we formalize such a situation so that Nature selects the quality of the auctioned good. Experts can observe Nature's selection (i.e., the quality of the good) correctly, while amateurs including the auctioneer cannot. In other words, the information on Nature's selection is asymmetric between experts and amateurs. In this situation, it is difficult to attain an efficient allocation, since experts have a clear advantage over amateurs and they would not reveal their valuable information without some reward. Thus, in this paper, we develop a new auction protocol in which truth-telling is a dominant strategy for each expert. This can be done by putting these experts in a situation similar to Prisoner's Dilemma. If they cooperate and tell lies, they can exclude amateurs, but betraying is a dominant strategy. By making experts to elicit their information on the quality of the good, the protocol can achieve a socially desirable, i.e., Pareto efficient allocation if certain assumptions are satisfied.
39083447
A new distributed approach to solve meeting scheduling problems
Meeting Scheduling (MS) is an important real world-problem that is defined by the process of scheduling meetings while taking into account several constraints related to the availability and preferences of the users. The main contribution of this paper is to propose a new approach based on the DRAC model (distributed reinforcement of arc consistency) to solve the MS problem. A simplified version of this approach was implemented and compared with an approach of the state of the art. The experimental results show that our approach is scalable.
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.
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.
32325022
Algorithms for Finding Distance-Edge-Colorings of Graphs
For a bounded integer l, we wish to color all edges of a graph G so that any two edges within distance l have different colors. Such a coloring is called a distance-edge-coloring or an l-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.
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.
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.