Current Research Statement
Takayuki Ito,
Nov. 1, 2009
Computational Negotiation Mechanisms
- Exploring the Future of Collaboration and Negotiation -
My main interest is to envision the future of collaboration and negotiation among people in the global world. As Internet has been growing, the large paradigm shift has begun in IT society and computer science. To catch and represent such paradigm shift, many words, “cloud computing”, “grid computing,” etc., have been invented. In essence, thanks to fiber optical cables and their enough equipment, the network bandwidth has been increased drastically compared with 10 years ago. People are starting to realize its huge merits on its scalability and its speed for collaboration and negotiation in global world. For example, offshore software development is one of the most popular examples, which utilize network scalability and speed. Electronic markets, like eBay, Yahoo! Auction, are also examples, which has been empowered by network scalability and speed. We can easily expect the increase of the number of participants in such a global collaboration and negotiation.
In such a situation, computational supports will play huge role to enhance the power of collaboration and negotiation. For example, during negotiation, computer software could help shaping uncertain utilities, finding a better contract, find alternative contracts for huge amount of possible contracts. Also, theoretical analysis and design of such negotiation and collaboration center is critical so that huge number of transactions and communication will be able to be processed and computed. Based on such theories and models, we can innovate real applications, which have never been in the past in the world. For example, some researchers have been working on future banking mechanism on global network systems. One of the early instantiations is online social lending in which a person can lend to and borrow from a person directly in a peer-to-peer lending market. Further, they provide automatic portfolio construction, match making, and also a secondary market. We can imagine a lot of such new innovative applications will be come up with in rush. One of my research topics is to reduce the default rates for social lending. Furthermore, the analysis of network of people is gathering much attention because such analysis can provide an insight for marketing, a tool for detecting frauds, and a view for social network research. One of my topics include developing a new ranking mechanism for trading people in auction network so that people can know good participants and find a possibility of frauds.
I am focusing on how computer systems support them and what kind of computer support is really effective to real world collaboration and negotiation from the following 3 different aspects, theoretical aspect, model-based aspect, and application aspect. For each aspect, I initiated the following project:
I would like to describe the details of the above projects. My continuing efforts on these projects have been honored as following Prize and Award :
The Young Scientists' Prize, The Commendation for Science and Technology by the Minister of Education, Culture, Sports, Science and Technology, 2007.
Information Processing Society of Japan, Nagao Special Researcher Award, 2007.
1. Computational Mechanism Design Theory
Computational Mechanism Design theory brings together the concern in microeconomics and game theory with decision making under distributed private information, uncertainty, and self-interest, and the concern in computer science with computational and communication complexity and real-time & large scale search algorithms.
1.1. Interdependent value auctions
We consider the problem of auction design with agents that have interdependent values, i.e. values that depend on each others' private signals. This can happen either because information about the value of a good (or goods) is distributed throughout a system, or because agents will later compete against each other and thus they care about the allocation to, and value of, other agents. In addition to e-commerce applications, we also see interdependent values in multiagent environments such as grid computing, for instance in allowing a team of scientists to evaluate their value for receiving the right to be the first to work with a new data set. We adopt the contingent bids model of Dasgupta and Maskin published in 2000, and allow agents to submit bids of the form ``if player 1 bids $x for good A then I will bid $y." Our main contribution is to identify a specific linear valuation model for which there exists an efficient auction for a single item, and then extend this to provide an approximately efficient combinatorial auction with single-minded bidders. In both auction, winners and payments are computed from the fixed point of the valuation mapping defined by contingent bids. We also adopt search in order to construct a variation on the single-item auction with improved revenue. In closing, we discuss the (many) challenges in moving to more general models of interdependent valuations. This is a collaborative work with Prof. David C. Parkes in Computer Science, Harvard University.
[Ito2006] Takayuki Ito, David Parkes, " Instantiating the Contingent Bids Model of Truthful Interdependent Value Auctions", In the Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2006), 2006. (This paper has been selected as the Best Paper in AAMAS2006).
[Florin2007]Florin Constantin, David Parkes, Takayuki Ito, " Online auctions for bidders with interdependent values", In the Proceedings of the Sixth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2007), 2007 (Poster).
1.2 Auctions under the situation in which players have multidimensional signals and interdependent values
In everyday life, it is often difficult for us to correctly know the quality of goods that are traded. In particular, on the Internet auctions, there exist many and unspecified persons who are selling their goods. If we misjudge the quality of a good, and purchase a poor quality item at an expensive price, we suffer loss by the trade. In game theory, information such as quality that cannot be determined by sellers and buyers is called Nature's selection. Experts who can recognize the nature's selection take advantage of it in trading. If we can make experts reveal their information on nature's selection, our auction mechanism can support people to make socially desirable decisions. In this research, we have proposed auction mechanisms under asymmetric information on nature's selection. In economics, such situation can be modeled as the situation in which players have multidimensional signals and interdependent values. Even in economics, this is on-going research field where several researchers have been publishing their possible or impossible results.
In [Ito 2002], we proposed a single unit auction protocol among experts and amateurs. In [Ito 2003], we proposed a combinatorial auction protocol among single-skilled experts and amateurs. In this year [Ito 2004], we focus on versatile experts, who have interest in and expert knowledge of the qualities of several items. In the case of versatile experts, there are several problems, e.g., free riding problems, if we simply extend the previous VCG-style auction protocol. Thus, in [Ito 2004], we employ a PORF (price-oriented, rationing-free) protocol for designing our new protocol to realize a strategy-proof auction protocol for experts. In the protocol, the dominant strategy for experts is telling the truth. Also for amateurs, telling the truth is the best response when two or more experts select the dominant strategy. Furthermore, the protocol is false-name-proof.
[Ito2002] Takayuki Ito, Makoto Yokoo, and Shigeo Matsubara, "Designing an Auction Protocol under Asymmetric Information on Nature's Selection," In the Proceedings of the International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2002), Bologna, Italy, July 15-19, pp.61-68, 2002
[Ito2003] Takayuki Ito, Makoto Yokoo, and Shigeo Matsubara, "Towards a Combinatorial Auction Protocol among Experts and Amateurs: The Case of Single-Skilled Experts," In the Proceedings of the Second International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2003), pp.481-488, 2003.
[Ito2004] Takayuki Ito, Makoto Yokoo, and Shigeo Matsubara, "A Combinatorial Auction among Versatile Experts and Amateurs" In the Proceedings of the Third International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2004), 2004.
[Ito2004] Takayuki Ito, Makoto Yokoo, and Shigeo Matsubara: " Designing Auction Protocols under Asymmetric Information on Nature's Selection, " In the Proceedings of DIMACS Workshop on Computational Issues in Auction Design, Rutgers University, NJ, on October 7 and 8, 2004.
[Ito2005] Takayuki Ito, Makoto Yokoo, Shigeo Matsubara, and Atsushi Iwasaki "A New Strategyproof Greedy-Allocation Combinatorial Auction Protocol and its Extension to Open Ascending Auction Protocol" In the Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI2005), pp.261-266, 2005.
The related our paper in Japanese got the 2005 Best Paper Award from Japan Society for Software Science and Technology.
1.3 Fast Approximation Algorithms for Very Large scale Combinatorial Auctions
Combinatorial auctions, one of the most popular market mechanisms, have a huge effect on electronic markets and political strategies. Combinatorial auctions provide suitable mechanisms for efficient allocation of resources to self-interested attendees. On the other hand, efficient resource allocation is also becoming crucial in many computer systems that should manage resources efficiently. Considering a Cloud Computing scenario, the ability to complete the results of auctions on combinations of services and software components within fine-grained time period without loss of allocation efficiency is in strong demand. Furthermore, to achieve such scenarios, it is very important to handle a large number of bids in an auction. In general, the optimal winner determination problem of a combinatorial auction is NP-hard. Thus, much work focuses on tackling the computational costs for winner determination. In this paper, we show that our approximation algorithms provide sufficient quality of winners for auctions that have a large number of bids on hard time constraints. Furthermore, we compare and discuss desirable properties of such approximation algorithms to be embedded in application systems.
In this study, we propose a set of approximation algorithms for winner determination problem of combinatorial auctions that offers following features that are important when they embedded into actual software systems: 1) Attaining the initial approximated allocations in very short time with acceptable (over 80 percent of) optimality, 2) Free from parameter tuning on using the algorithms, and 3) Better optimality of allocations (approximately 94 percent to optimal) without irrelevant unacceptable allocations. Here, it is guaranteed that (tentative) winner bids are dominated bids without special pre-processing of excluding non-dominated bids. We show our proposed algorithms outperform existing excellent approximated algorithms without breaking above features in some conditions.
[Fukuta 2009] Naoki Fukuta, and Takayuki Ito,``'Approximated Winner Determination for a Series of Combinatorial Auctions'',Proc. of the 1st International Conference on Agents and Artificial Intelligence (ICAART2009),2009.
[Fukuta 2008] Naoki Fukuta and Takayuki Ito, Performance Analysis about Parallel Greedy Approximation on Combinatorial Auctions, Proceedings of the 1st Pacific RIm International Conference on Multi-Agents (PRIMA 2008), (to appear ; full paper), Hanoi, Vietnum, 2008.
[Fukuta 2007a] Naoki Fukuta and Takayuki Ito, "Fast Partial Reallocation in Combinatorial Auctions for Iterative Resource Allocation", In The Proceedings of The 10th Pacific Rim International Workshop on Multi-Agents (PRIMA 2007), Bangkok, Thailand, Nov. 21-23, 2007.
[Fukuta 2007b] Naoki Fukuta, and Takayuki Ito,"Periodical Resource Allocation Using Approximated Combinatorial Auctions", The Proceedings of the 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT/WI 2007), 2007.
[Fukuta 2007c] Naoki Fukuta and Takayuki Ito, "Short-Time Approximation on Combinatorial Auctions - A Comparison on Approximated Winner Determination Algorithms", In the Proceeding of the 3rd International Workshop on Data Engineering Issues in E-Commerce and Services (DEECS2007), June 12, San Diego, USA, 2007.
[Fukuta 2007d] Naoki Fukuta and Takayuki Ito, "Toward A Large Scale E-Market : A Greedy and Local Search based Winner Determination", In the Proceeding of the 20th International Conference on Industrial, Engineering & Other Applications of Applied Intellitent Systems (IEA/AIE2007), 2007 .
[Fukuta 2006] Naoki Fukuta and Takayuki Ito, "Towards Better Approximation of Winner Determination for Combinatorial Auctions with Large Number of Bids", In the Proceeding of 2006 IEEE/WIC/ACM International Joing Conference on Web Intelligence and Intelligent Agent Technology (IAT2006), 2006.
1.4 Detecting and Avoiding Shill bidders in Auctions
This study [Matsuo 2006] focuses a method for discovering and detecting shill bids in combinatorial auctions. The Vickrey-Clarke-Groves Mechanism is one of the most important combinatorial auctions because it can satisfy the strategy-proof property, individual rationality, and Pareto efficiency, that is, it is the only mechanism that simultaneously satisfies these properties. As Yokoo et al. pointed out, false-name bids and shill bids pose an emerging problem for auctions, since on the Internet it is easy to establish different e-mail addresses and accounts for auction sites. Yokoo et al. proved that VCG cannot satisfy the false-name-proof property, and they also proved that no auction protocol can satisfy all three of the above properties and the false-name proof property simultaneously. Their approach concentrates on designing a new mechanism that has desirable properties, but this is quite complicated. As a new approach against shill-bids, in this paper, we design a mechanism that utilizes VCG and an algorithm for finding potential shill bids. Our mechanism is quite simple compared with Yokoo’s approaches. Our mechanism can judge whether there might be a shill bid from the results of the VCG procedure. We prove a theorem stating that shill bidders cannot increase their utilities unless all shill bidders win in the auction. Based on this theorem, our proposed mechanism compares the agents’ utilities in a conventional auction with those in an auction where a shill bidder does not join in the auction. When these agents’ utilities are different between the above cases, such agents might be shill bidders. Then, our mechanism allocates items to the shill bidders as a group from the set of items obtained through successful bids by the agent in the conventional auction. This process prevents shill bidders from increasing unfair profits. Furthermore, even though shill bidders participate in the auction, the seller’s profit does not decrease using our proposed method. Thus, our mechanism detects shill bids when it only detects the possibility of shill bids. Our proposed method has the following three key advantages. First, we propose a method to detect shill bidders by comparison between bidders utilities. Our method is superior than existing complex mechanisms in the point of view of generalization and wide-use, because our auction mechanism employs only VCG. Second, even though there are shill bidders in an auction, incentive compatibility property is preserved using our mechanism. Finally, the schemer, in our mechanism, does never have incentive to make shill bidders. The schemer’s utility does not increase in our mechanism even though a schemer make shill bidders. Namely, not to make shill bidders is dominant strategy for the schemer. This research is partially a cooperative work with Prof. Robert Day in Business School of Connecticut University.
[Matsuo 2006] Tokuro Matsuo, Takayuki Ito, Robert Day, Toramatsu Shintani "A Robust Combinatorial Auction Mechanism against Shill Bidders", In the Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2006), 2006.
2. Automated Negotiation Mechanisms for Complex Utilities
Multi-issue negotiation protocols have been studied widely and represent a promising field since most negotiation problems in the real world involve multiple issues. The vast majority of this work has assumed that negotiation issues are independent, so agents can aggregate the utilities of the issue values by simple summation, producing linear utility functions. In the real world, however, such aggregations are often unrealistic. We cannot, for example, just add up the value of car's carburetor and the value of car's engine when engineers negotiate over the design a car. These value of these choices are interdependent, resulting in nonlinear utility functions. In this paper, we address this important gap in current negotiation techniques. We propose a negotiation protocol where agents employ adjusted sampling to generate proposals, and an auction mechanism is used to find social-welfare maximizing deals. Our preliminary experimental results show that our method substantially outperforms existing methods in large nonlinear utility spaces like those found in real world contexts. Further, we show that our protocol is incentive compatible. This is a cooperative research project with Dr. Mark Klein, in the Center for Collective Intelligence (CCI), Sloan School of Management, Massachusetts Institute of Technology (MIT).
2.1 Auction-based Multi-Issue Negotiation Protocol
We have proposed an auction-based multiple-issue negotiation protocol among nonlinear utility agents [Ito2008, Ito2007, Ito2006a, Ito2006b, Ito2006c]. In order to make the protocol scalable, we first employ a sampling method for agents. By sampling its own utility space, an agent can reduce its search cost. Also, the simple sampling often fails to find better solutions. Thus, in our protocol, agents adjust their sampled points firstly by using a search technique. After that, agents submit bids. Since we assume a huge utility space, if these bids are based on contract points, there could be too much bids. Thus, in our model, agents make bids on a set of constraints among issue values. This bid expression can drastically reduce the computational cost. The mediator finds a combination of bids that maximizes social welfare. Our experimental results show that our method can outperform the existing simple methods in particular in the huge utility space that can be often found in the real-world. Further, theoretically, our negotiation protocol can guarantee to find the optimal point if the sampling is conducted extensively and the threshold for selecting bids is 0. Our experimental results show that our method can outperform the existing simple methods in particular in the huge utility space that can be often found in the real world. Further, theoretically, our negotiation protocol can guarantee the completeness if some conditions are satisfied. Interestingly, the exhaustive search often fails and cannot terminate if the utility space becomes huge,. Also, when the utility space becomes huge and the number of constraints is not large, then the simulated annealing search often drop into local optimal. Even such cases our proposed method, the negotiation method with SA-sampling, can find approximately optimal points (we can not validate the points are optimal because the exhaustive search does not work in such a huge utility space).
[Ito 2008] Takayuki Ito, Mark Klein, and Hiromitsu Hattori: "A Multi-Issue Negotiation Protocol among Agents with Nonlinear Utility Functions: A Preliminary Report", Journal of Multiagent and Grid Systems, ios press, Vol 4, No. 1, 2008.
[Ito 2007] Takayuki Ito, Mark Klein, Hiromitsu Hattori, "Multi-issue Negotiation Protocol for Agents: Exploring Nonlinear Utility Spaces", In the Twentieth International Joint Conference on Artificial Intelligence (IJCAI2007), Hyderabad, India, January 6-12, 2007.
[Ito 2006a] Takayuki Ito, Mark Klein, Hiromitsu Hattori, "A Multi-Issue Negotiation Protocol among Nonlinear Utility Agents : A Preliminary Report", In the Proceedings of the 2nd International Workshop on Rational, Robust, and Secure Negotiations in Multi-Agent Systems (RRS2006), 2006
[Ito 2006b] Takayuki Ito, Mark Klein, "A Multi-Issue Negotiation Protocol among Competitive Agents based on Auctions", In the Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2006), 2006.
[Ito 2006c] Takayuki Ito, Mark Klein, Hiromitsu Hattori, "A Negotiation Protocol for Agents with Nonlinear Utility Functions", In the 21st National Conference on Artificial Intelligence (AAAI2006), Boston, July 16-20, 2006.
2.2 Using Iterative Narrowing to Enable Multi-Party Negotiations with Multiple Interdependent Issues
We have presented a novel multi-round negotiation protocol that uses iterative narrowing of agent bids to achieve these goals [Hattori2007a, Hattori2007b, Hattori2007c]. In the early rounds, agents submit rough bids representing promising contract space regions (rather than individual contracts) to a mediator. In later rounds, they submit increasingly narrow bids for the subset of those regions that all agents liked in the previous round, until a deal is found. Our experimental results show that our method outperforms existing methods in large nonlinear utility spaces, and is computationally feasible for negotiations with as many as ten agents. Our experimental results show that our method offers near-optimal negotiation outcomes for up to 10 agents, if they have substantially clustered utility functions. We are aware of no previous work that scales up nonlinear negotiation beyond two agents.
[Hattori2007a] Hiromitsu Hattori, Mark Klein, Takayuki Ito, "Using Iterative Narrowing to Enable Multi-Party Negotiations with Multiple Interdependent Issues", In the Proceedings of the Sixth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2007), 2007
[Hattori2007b] Hiromitsu Hattori, Mark Klein, and Takayuki Ito, "A Multi-Phase Protocol for Negotiation with Interdependent Issues", The Proceedings of the 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT/WI 2007), 2007.
[Hattori2007c] Hiromitsu Hattori, Takayuki Ito, Mark Klein "Using Iterative Narrowing to Enable Multi-Party Negotiations with Multiple Interdependent Issues", In the Proceedings of the Sixth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2007), 2007
2.3 Towards to Secure and Privacy Preserved Automated Negotiation
Existing works have not yet concerned with agents’ private information that should be concealed from others in negotiations. In this research, we have proposed Distributed Mediator Protocol (DMP) to securely find the agreements that satisfy the Pareto optimality [Fujita 2008a, Fujita 2008b, Fujita 2008c, Fujita 2007a, Fujita 2007b]. DMP successfully conceals agents’ private information. Since there could be multiple Pareto-optimal contracts in the negotiation space, we extend it to employ the genetic algorithm (GA) to find a set of Pareto-optimal contracts. Then, we propose the following two measures for selecting the final agreements from the set of Pareto-optimal contracts. First, we propose “approximated fairness,” which represents how fair the contract is for each agent. We employ deviation for measuring the difference of utilities achieved by agents. Second, we propose the rate of Nash bargaining solution, which represents how close the contract is to the Nash bargaining solution. The Nash bargaining solution maximizes the product of each agent’s utilities (Nash product) in our model. The approximated fairness helps the mediator find the contract that is close to the Nash bargaining solution. This is because the Nash product will be increased if approximated fairness becomes small. We demonstrate that the DMP is better for finding the Nash bargaining solution compared with existing work. Moreover, we propose Hybrid Secure Protocol (HSP) with agents’ private information concealed. HSP also can make agreements with less communication cost than DMP.
[Fujita 2008a] Katsuhide Fujita,Takayuki Ito, Mark Klein, "A Multi-Round Persuasion based on Revealed Private Utility Space In Multi Issue Negotiations", In the Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2008), 2008.
[Fujita 2008b] Katsuhide Fujita, Takayuki Ito, and Mark Klein,Preliminary Result on Secure Protocols for Multiple Issue Negotiation Problems, Proceedings of the 1st Pacific Rim International Conference on Multi-Agents (PRIMA 2008), (to appear ; full paper), Hanoi, Vietnum, 2008.
[Fujita 2008c] Katsuhide Fujita, Takayuki Ito, and Mark Klein "Effects of Revealed Area based Selection Method for Representative-based Protocol", In the Proceedings of the 1st International Workshop on Agent-based Complex Automated Negotiations (ACAN 2008), 2008
[Fujita 2007a] Katsuhide Fujita and Takayuki Ito, "A Preliminary Analysis of Computational Complexity of the Threshold Adjusting Mechanism in Multi-Issue Negotiations", In The Proceeding of The 3rd International Workshop on Rational, Robust, and Secure Negotiations in Multi-Agent Systems (RRS2007), 2007.
[Fujita 2007b] Katsuhide Fujita and Takayuki Ito, "An Approach to Implementing A Threshold Adjusting Mechanism in Very Complex Negotiations: A Preliminary Result", In The Proceedings of The 2nd International Conference on Knowledge, Information and Creativity Support Systems (KICSS277), 2007 (Best Student Paper Award).
3 Analysis and Implementation of Electronic Markets.
In this project, I focus on implementing real systems and analyzing data from real world on mainly electronic markets. These real world oriented methodology is aimed at making the theory and the model more reliable and useful.
3.1 Developing Shopping support Bots & Bidding support Bots
In this project we consider the problem of eCommerce comparison shopping agents (shopbots) that are limited by capacity constraints. In light of the phenomenal increase both in demand for price comparison services over the internet and in the number of opportunities available in electronic markets, shopbots are nowadays required to improve the utilization of their finite set of querying resources. In [Sarn 2007], we introduce PlanBot, an innovative shopbot which uniquely integrates concepts from production management and economic search theory. PlanBot aims to maximize its efficiency by dynamically re-planning the allocation of its querying resources according to the results of formerly executed queries and new arriving requests. We detail the design principles that drive the PlanBot’s operation and illustrate its improved performance (in comparison to the traditional shopbots’ First-Come-First-Served (FCFS) query execution mechanisms) using a simulated environment which is based on price datasets collected over the internet. Our encouraging results suggest that the design principles we apply have the potential of being used as an infrastructure for various implementations of the future comparison shopping agents.
[Sarne 2007] David Sarne, Sarit Kraus, Takayuki Ito, "Scaling-Up Shopbots - a Dynamic Allocation-Based Approach", In the Proceedings of the Sixth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2007), 2007.
[Ito 2000] Takayuki Ito, Naoki Fukuta, Toramatsu Shintani, and Katia Sycara,: "BiddingBot: A Multiagent Support System for Cooperative Bidding in Multiple Auctions," In the Proceedings of the Fourth International Conference on Multi Agent Systems (ICMAS'2000), pp.399-400, 2000.
3.2 Ranking Participants based on Trading Relation Network in E-Commerce
According to Yahoo! Japan's statistics, 70% of Internet users have experience with Internet auctions. Furthermore, these statistics show that Internet auctions are the most utilized recycle market compared with offline recycle markets, such as used bookstores. Also, the number of users of Internet auctions has continuously increased. The largest Internet auction in Japan, Yahoo! Auction, had 6,800,000 registered premier-IDs as of Feb. 2008. The premier-ID provides the right to utilize the pay services on the site. Since Internet auctions constitute a large market, there has been much fraud and dishonest acts. As a result, Yahoo! Japan is handling such fraud by monitoring auctions and analyzing auction histories with human resources. But, in spite of such efforts, the amount of fraud has been not reduced. Thus, developing automated programs that support the monitoring of auctions and the analysis of auction histories has become an important research area. At the same time, network structures like the WWW have become huge and are analyzed on a grand scale. In Internet auctions, users face the problem of really knowing the credit and trustworthiness of participants. The simple rating mechanism widely used in Internet auctions fails to represent the real credit and trustworthiness of participants. This is because such a rating mechanism is based on a one-to-one point system, namely two people who have finished their trading give relatively positive points to each other, and this mechanism lacks the global point of view of a trading network. From the viewpoint of network structure, network analysis has been widely developed. Many researchers try to understand characteristics of complex networks such as human friend relationships and company relationships by using mathematical models. Since the WWW is one of the largest networks, a lot of researchers analyze it from many viewpoints. In this work [kobayashi2007a, kobayashi2007b], we try to analyze a trading network in Internet auctions by using network analysis techniques. The aim is to support users in discovering new knowledge and insight among sellers and buyers in the trading networks. Such knowledge and insight could be related to both good and bad acts in the trading network. We propose ANT (Auction Network Trust), a novel algorithm for evaluating and analyzing an trading network. By applying ANT to an trading network, scores for each user as a seller or as a buyer are calculated. We conducted preliminary experiments in which ANT was applied to real trading data. The following three points provide a summary of the experiments. (1) We found a correlation between ANT with the seller's response time (which does not depend on his rating values) and nice rating points. This means that ANT succeeded in finding nicer sellers without any rating values. (2) Good users could be found by the ANT that employs the difference between one's rating value and the other's rating value. (3) A well-known HITS problem in which pages in the same site could be ranked higher could be avoided since an auction network does not have a site-like structure. This work is in collaboration with Yahoo! Japan, inc.
[Kobayashi 2007a] Masao Kobayashi and Takayuki Ito, "An Approach to Implement A Trading Network Visualizing System for Internet Auctions", In The Proceedings of The 2nd International Conference on Knowledge, Information and Creativity Support Systems (KICSS277), 2007
[Kobayashi 2007b]Masao Kobayashi and Takayuki Ito, "A Transactional Relationship Visualization System In Internet Auctions", The Proceedings of the 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT/WI 2007), 2007.
This work has been awarded as Student Encouragement Award in Joint Agent Workshop & Symposium (JAWS2008), 2008.
3.3 A Dynamic Interest Rate Adjusting Mechanism for Online Social Lending
Social lending is, in its broadest sense, a certain breed of financial transaction (primarily lending and borrowing) that occurs directly between individuals without the intermediation or participation of a traditional financial institution. Social lending is a dynamic trading mechanism that can directly match one consumer with another consumer. Most manual transaction processes conducted by traditional financial institutions can be done automatically and tailored to each consumer in social lending so that every player can maximize his own values in the transactions. The processes that could be automated include adjusting interest rates, creating incentives for borrowers to return money, recommending lenders and borrowers, creating portfolios, etc. In this work [iwakami 2008], we focus on an automatic interest adjustment and incentive mechanism for borrowers because they are crucial for dynamic social lending since they could help increase worth and reduce payment delays. We propose two methods for automatically adjusting interest rates and creating incentives for borrowers to return money. First, we propose a Bayesian updating method for interest rate adjustment that considers the influence of their social groups on borrowers. Our method determines an accurate rate because the borrower’s delay history is dynamically reflected in the rate decision. Second, we propose an incentive mechanism that improves a borrower’s payment delay score. The mechanism offers incentives for payment with rewards (penalties) to borrowers. We demonstrate the efficiency on our proposed methods by conducting agent simulations. This work is collaboration with Dr. Joaquin Delgado (Yahoo!, US ; Former CTO of Lending Club, Inc.).
[Iwakami 2008] Masashi Iwakami and Takayuki Ito, An Interest Rate Adjusting Method with Bayesian Estimation in Social Lending, Proceedings of the 1st Pacific Rim International Conference on Multi-Agents (PRIMA 2008), Hanoi, Vietnum, 2008.
3.4 Facilitating Sharing Information based on Incentive Description language
WWW has been an important infrastructure for information sharing. We can create homepages and provide information on WWW. Except some successful examples, Wikipedia, etc., actually, to provide information on WWW is quite hard work for people. For example, in the online discussion boards, 80% people are ROPs (Read Only Persons). Further, to create a home page, we need to download, edit by a specific application, and upload it. Thus, actually, WWW is a nice information SHARING system. But, we cannot say WWW can facilitate people to provide information. We are tackling this problem by creating several concepts and applications. Descriptive Incentive is one of the concepts. Descriptive Incentive is different from Incentives in the field of economics. Descriptive Incentive can be described based on a set of services. These services motivate users to provide information. Concretely, we have developed the document sharing system. In this system, several service components are implemented. Users have different preferences on such services. Thus, the incentive mechanism evaluates user's preferences on services. Then, user's preferences on services are described by XML-based language, KRML (Knowledge Representation Mark-up Language).
Past and Old projects
These projects have been already done. However, I am interested in some of these even now.
Persuasion and Multiple Negotiations (1997 - 2000 for M.E. & D.E. thesis)
Persuasion: When two or more agents need to conduct a joint task, these agents need to reach an agreement on some conditions. If an agreement can be achieved, there is no problem, and agents can jointly condut the task. But, if they can not reach an agreement, one of the agents needs to PERSUADE the other to get an agreement. In agent-mediated group decision support systems, we often face agaist the above situation. In [Ito 97], we represented agent's belief as a AHP hierarchy. Then, we create an persuasion mechanism based on adjusting pairwise comparison values.
[Ito 97] Takayuki Ito and Toramatsu Shintani.: ``Persuasion among Agents : An Approach to Implementing a Group Decision Support System Based on Multi-Agent Negotiation'', In the Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI-97), pp.592-597, Morgan Kaufmann Publishers, Inc., 1997
Multiple Concurrent Negotiations: Persuasion was a good tool to get an agreement in TWO agents. However, if there are two or more agents, the order to persuade can be a critical matter. Actually, in [Ito 97], we employed a tournament method to get an agreement among several agents. Here, how to organize a tournament was one of issues. Thus, we proposed Multiple Negotiations in which each agent has a chance to persuade the other agents [Shintani 2000]. Because our agents are softwares, in an real application, each agent creates his/her clones. Then, these clones are persuaded by the other agents. Thus, these persuasions are conducted simultaneously.
The Achievements
1. The Young Scientists' Prize, The Commendation for Science and Technology by the Minister of Education, Culture, Sports, Science and Technology.
2. Information Processing Society of Japan, Nagao Special Researcher Award, 2007.
3. Nominated for Best Paper Award (JAWS2006)
4. Best Paper Award, The 5th International Joint Conference on Autonomous Agents and Multi-Agent Systems.
5. Best Paper Award 2005, Journal of Japan Society for Software Science and Technology (JSSST).
6. Super Creator Award of 2004 IPA Exploratory Software Creation Project.
7. Best Paper Award of the 66th IPSJ National Convention (in top 10 papers that selected from 1,000 papers)
8. Best Paper Award for Young Researcher of the 66th IPSJ National Convention (in top 10 younger researchers' papers that selected from 1,000 papers)
9. Nominated for Best Paper Award (top 5 papers were nominated from 129 accepted papers), The 16th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE-2004)
10. The Third Place in the world, RoboCup WorldCup 2001
11. Silver medal (The Second Place in the world), RoboCup in RoboFesta 2001
12. Students Research Encouraging Award of The Tokai Regional Section of The Institute of Electronics, Information and Communication Engineers (IEICE) ,1997.