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.
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
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.
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.
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.
10045838
Algorithms for finding distance-edge-colorings of graphs
For a bounded integer @?, we wish to color all edges of a graph G so that any two edges within distance @? have different colors. Such a coloring is called a distance-edge-coloring or an @?-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.
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.
40274616
On the spectra of certain distance-regular graphs
Let r be an undirected graph whose vertex-set V(F) is the set (ZJ~ , u2 ,..., v,>. The adjacency matrix of I’ is the n x n matrix A = A(r), over the complex number field, whose entries aij are given by a,j = 1 if vi and vi are adjacent, = 0 otherwise. DEFINITION 1. The spectrum of r is the set of distinct eigenvalues 4l , 4 ,**-> Od of A(F), together with their multiplicities, written m(&), m(4),..., m(0,). Since r is undirected, A is symmetric, and so the Bi are all real numbers. We arrange the Bi in increasing order, namely, 0, < O1 < *.. < e dMany studies have been done on the spectra of graphs by many mathematicians. Some of them may be found, for instance, in Biggs [2].
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.