| 1. |
Yokoo Makoto, Hirayama Katsutoshi, Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems, 船貨輸送研究施設研究報告, Vol.8, pp.43-50, 1997.03. |
| 2. |
New Directions of CSP : Distributed/Dynamic/Partial CSP. |
| 3. |
Distributed Breakout : Iterative Improvement Algorithm for Solving Distributed Constraint Satisfaction Problem
This paper presents a new algorithm for solving distributed constraint satisfaction problems (distributed CSPs) called the distributed breakout algorithm, which is inspired by the breakout algorithm for solving centralized CSPs. In this algorithm, each agent tries to optimize its evaluation value (the number of constraint violations) by exchanging its current value and the possible amount of its improvement among neighboring agents. Instead of detecting the fact that agents as a whole are trapped in a local-minimum, each agent detects whether it is in a quasi-local-minimum, which is a weaker condition than a local-minimum, and changes the weights of constraint violations to escape from the quasi-local minimum. Experimental evaluations show this algorithm to be much more efficient than existing algorithms for critically difficult (phase transition) problem instances of distributed graph-coloring problems.. |
| 4. |
A Limitation of the Generalized Vickrey Auction in Electronic Commerce : Robustness against False-name Bids. |
| 5. |
Frequency Assignment for Cellular Mobile Systems Using Constraint Satisfaction Techniques. |
| 6. |
Distributed Partial Constraint Satisfaction Problem. |
| 7. |
横尾 真, 平山 勝敏, Makoto Yokoo, Katsutoshi Hirayama, Kobe University of Mercantile Marine., 複雑な局所問題に対応する分散制約充足アルゴリズム, 人工知能学会誌 = Journal of Japanese Society for Artificial Intelligence, 10.1109/ICMAS.1998.699222, Vol.15, No.2, pp.348-354, 2000.03, A distributed constraint satisfaction problem can formalize various application problems in Multiagent systems, and several algorithms for solving this problem have been developed. One limitation of these algorithms is that they assume each agent has only one local variable. Although simple modifications enable these algorithms to handle multiple local variables, obtained algorithms are neither efficient nor scalable to larger problems.We develop a new algorithm that can handle multiple local variables efficiently, which is based on the asynchronous weak-commitment search algorithm. In this algorithm, a bad local solution can be modified without forcing other agents to exhaustively search local problems. Also, the number of interactions among agents can be decreased since agents communicate only when they find local solutions that satisfy all of the local constraints. Experimental evaluations show that this algorithm is far more efficient than an algorithm that uses the prioritization among agents.. |
| 8. |
Robust Combinatorial Auction Protocol against False-name Bids. |
| 9. |
Frequency Assignment for Cellular Mobile Systems Using Constraint Satisfaction Techniques
This paper presents a new algorithm for solving frequency assignment problems in cellular mobile systems using constraint satisfaction techniques. The characteristics of this algorithm are as follows : 1) instead of representing each call in a cell (a unit area in providing communication services) as a variable, we represent a cell (which has multiple calls) as a variable that has a very large domain, and determine a variable value step by step, 2) a branch-and-bound search that incorporates forward-checking is performed, 3) a powerful cell-ordering heuristic is introduced, and 4) the limited discrepancy search is introduced to improve the chance of finding a solution in a limited amount of search. Experimental evaluations using standard benchmark problems show that this algorithm can find optimal or semi-optimal solutions for these problems, and most of the obtained solutions are better than or equivalent to those of existing methods using simulated annealing, tabu search, or neural networks. These results show that state-of-the-art constraint satisfaction / optimization techniques are capable of solving realistic application problems when equipped with an appropriate problem representation and heuristics.. |
| 10. |
平山 勝敏, 横尾 真, Katsutoshi Hirayama, Makoto Yokoo, Kobe University of Mercantile Marine., NTT Communication Science Laboratories., 分散制約充足におけるnogood学習の効果, 人工知能学会誌 = Journal of Japanese Society for Artificial Intelligence, 10.1109/ICDCS.2000.840919, Vol.15, No.2, pp.355-361, 2000.03, We present resolvent-based learning as a new nogood learning method for a distributed constraint satisfaction algorithm. This method is based on a look-back technique in the CSP literature and can efficiently make effective nogoods.We combine the method with the asynchronous weak-commitment search algorithm (AWC) and evaluate the performance of the resultant algorithm on distributed 3-coloring problems and distributed 3SAT problems. As a result, we found that the resolvent-based learning works well compared to previous learning methods for distributed constraint satisfaction algorithms. We also found that the AWC with the resolvent-based learning is able to find a solution with fewer cycles than the distributed breakout algorithm, which was known to be the most efficient algorithm (in terms of cycles) for solving distributed CSPs.. |
| 11. |
An Efficient Approximate Algorithm for Winner Determination in Combinatorial Auctions
This paper presents an approximate algorithm for the winner determination problem in combinatorial auctions, which is based on limited discrepancy search (LDS). Internet auctions have become an integral part of Electronic Commerce and can incorporate large-scale, complicated types of auctions including combinatorial auctions, where multiple items are sold simultaneously and bidders can express complementarity among these items. Although we can increase participants’ utilities by using combinatorial auctions, determining the optimal winners is a complicated constraint optimization problem that is shown to be NP-complete. We introduce the idea of LDS to an existing algorithm based on A<SUP>*</SUP>. The merit of LDS is that it can avoid time-consuming re-computation of heuristic function h(·), since LDS is less sensitive to the quality of h(·). It can also limit the search efforts only to promising regions. Experiments using various problem settings show that, compared with the existing optimal algorithm, LDS can find near-optimal solutions (better than 95%) very quickly (around 1% of the running time).. |
| 12. |
Robust Double Auction Protocol against False-Name Bids
オークションは急成長している電子商取引の重要な一分野であり, ソフトウェアエージェント技術の有望な適用領域であると考えられる. インターネットを利用することにより低コストで大規模なオークションが可能となった一方で, ネットワークでの匿名性を利用した新しいタイプの不正行為が問題となる. 本論文では, このような不正行為の一つである架空名義入札に対して頑健性が保証される, 新しいダブルオークションプロトコルを提案する. ダブルオークションは買手/売手の双方が複数存在し入札を行うオークションであり, 外貨, 証券, 株等の取引に広く用いられている. 従来, 架空名義入札が存在しない場合には, 支配戦略において誘因両立的であるダブルオークションプロトコル(PMDプロトコル)が提案されている. 一方, 売手が別の名義を用いて, 買手になりすまして入札を行うといった架空名義入札の可能性を考えると, PMDプロトコルでは, 入札者は架空名義入札によって利益を増やすことが可能であり, 誘因両立性は保証されない. 本論文では, 架空名義入札が可能な場合でも, 支配戦略において誘因両立的である, しきい値価格ダブルオークションプロトコル(Threshold Price Double auction protocol, TPD)を提案する. TPDプロトコルの特徴は, 財のしきい値価格を用いて可能な取引の数及び取引価格を制御することである. シミュレーションを用いた実験結果を用いて, 適切なしきい値価格を設定することにより, TPDプロトコルでパレート効率的な割当てに非常に近い社会的余剰が得られることを示す.. |
| 13. |
Report on ACM EC-00.. |
| 14. |
Robust Combinatorial Auction Protocol against False-name Bids
This paper presents a new combinatorial auction protocol that is robust against false-name bids. Internet auctions have become an integral part of Electronic Commerce (EC) and a promising field for applying agent and Artificial Intelligence technologies. Although the Internet provides an excellent infrastructure for combinatorial auctions, we must consider the possibility of a new type of cheating, i.e., an agent tries to profit from submitting several bids under fictitious names (false-name bids). If there exists no false-name bid, the generalized Vickrey auction protocol (GVA) satisfies individual rationality, Pareto efficiency, and incentive compatibility. On the other hand, when false-name bids are possible, it is theoretically impossible for any combinatorial auction protocol to simultaneously satisfy these three properties in all cases. Our newly developed Leveled Division Set (LDS) protocol, which is a modification of the GVA, utilizes reservation prices of auctioned goods for making decisions on whether to sell goods in a bundle or separately. The LDS protocol satisfies individual rationality and incentive compatibility, although it is not guaranteed to achieve a Pareto efficieht social surplus. Simulation results show that the LDS protocol can achieve a better social surplus than that for a protocol that always sells goods in a bundle.. |
| 15. |
Bundle Design in Robust Combinatorial Auction Protocol against False-name Bids
本論文では,インターネットオークションで深刻な問題となり得る架空名義入札に対して,頑健性が保証される組合せオークションプロトコルの実現方法について検討する.インターネットを利用することにより低コストで大規模なオークションが可能となった一方で,ネットワークでの匿名性を利用した新しいタイプの不正行為が問題となる.このような不正行為の1つとして,単一のエージェントが,複数の名義を用いて入札を行う架空名義入札が存在する.複数種類の商品を扱う組合せオークションにおいて,架空名義入札に対して頑健なプロトコルとして,レベル付き分割セットプロトコル(LDSプロトコル)が提案されている.しかしながら,LDSプロトコルではオークションの主催者がレベル付き分割セットと呼ばれる一連の財のバンドルの組合せを決定しなければならない.良い社会的余剰を得られるようにレベル付き分割セットを設計することは,組合せオークションにおける勝者決定問題よりもはるかに複雑な最適化問題となる.本論文では良い社会的余剰を得ることができるレベル付き分割セットを設計するためのヒューリスティックな手法を提案する.この手法は勝者決定アルゴリズムを主要な構成要素として,目的とするバンドルの組合せを元に,レベル付き分割セットを構成する.計算機シミュレーションを用いて,提案手法により,パレート効率的な社会的余剰に非常に近い結果が得られることを示す.. |
| 16. |
An Average-case Budget-Non-Negative Double Auction Protocol. |
| 17. |
Katsutoshi Hirayama, Makoto Yokoo, Katia Sycara, 分散・協調AI, 情報処理学会論文誌, Vol.45, No.9, pp.2217-2225, 2004.09, We first present an algorithm called multi-ABT as a baseline algorithm for solving distributed constraint satisfaction problems where each agent has multiple local variables. Then we show a cost profile of multi-ABT for various numbers of intra-agent constraints (constraints defined over variables of one agent) and inter-agent constraints (constraints defined over variables of multiple agents) in a distributed graph-coloring problem. This cost profile enabled us to make the following observations: (1) the satisfiability thresholds are identified in the narrow region on the x-y plane (where the x-axis is the number of intra-agent constraints and the y-axis is the number of inter-agent constraints) in which the sum of intra- and inter-agent constraints is constant and problem instances in the region (called the crossover belt) are likely to be expensive in terms of the median cost; (2) among problem instances on the crossover belt those with a smaller number of intra-agent constraints and a larger number of inter-agent constraints may be more expensive; and (3) for a fixed total number of variables problem instances on the crossover belt may be more expensive as the number of agents increases or the number of variables per agent decreases. Our further experiments suggest that these observations can be generalized to cases where different algorithms are applied or different sets of parameters of the problem are used.We first present an algorithm called multi-ABT as a baseline algorithm for solving distributed constraint satisfaction problems where each agent has multiple local variables. Then, we show a cost profile of multi-ABT for various numbers of intra-agent constraints (constraints defined over variables of one agent) and inter-agent constraints (constraints defined over variables of multiple agents) in a distributed graph-coloring problem. This cost profile enabled us to make the following observations: (1) the satisfiability thresholds are identified in the narrow region on the x-y plane (where the x-axis is the number of intra-agent constraints and the y-axis is the number of inter-agent constraints) in which the sum of intra- and inter-agent constraints is constant, and problem instances in the region (called the crossover belt) are likely to be expensive in terms of the median cost; (2) among problem instances on the crossover belt, those with a smaller number of intra-agent constraints and a larger number of inter-agent constraints may be more expensive; and (3) for a fixed total number of variables, problem instances on the crossover belt may be more expensive as the number of agents increases or the number of variables per agent decreases. Our further experiments suggest that these observations can be generalized to cases where different algorithms are applied or different sets of parameters of the problem are used.. |
| 18. |
A False-name-Proof Double Auction Protocol for Arbitrary Evaluation Values. |
| 19. |
False-name-proof multi-unit auction protocols for non-quasi-linear utility
This paper develops strategy/false-name-proof multi-unit auction protocols that can handle non-quasi-linear utilities. One almost universal assumption in auction theory literature is that each bidder has quasi-linear utility, except for some works on budget-constrained bidders. In particular, the VCG protocol is strongly believed to critically depend on the quasi-linear assumption and will break down if this assumption does not hold. We show that with a simple modification, the VCG can handle non-quasi-linear utilities by sacrificing efficiency to a certain extent. Also, we develop a new false-name-proof open ascending auction protocol.. |
| 20. |
A new keyword auction protocol for determining the appropriate number of slots
In a keyword auction, advertisers submit their bids to search keywords and their ads are displayed according the result of the auction when people search the keyword on internet search engines. In existing keyword auctions, the number of slots is determined in advance and the obtained social surplus is not always maximized. Thus, we develop new keyword auction protocols in which the auctioneer can flexibly determine the optimal number of slots which maximizes social surplus. First, we propose an auction protocol based on the Vickrey-Clarke-Groves mechanism. While the VCG can satisfy theoretically good characteristics, it needs the complicated calculation of payment. Therefore, we propose a practical protocol based on existing auction protocol applied in Google and Yahoo!. |
| 21. |
New Keyword Auction Protocols for Determining the Appropriate Number of Slots. |
| 22. |
Automated Mechanism Design for False-name-proof Combinatorial Auctions. |
| 23. |
Characterizing False-name-proof Allocation Rules in Combinatorial Auctions
メカニズムデザインとは，複数の人間 （エージェント） が何らかの社会的決定をする場合に，社会的に望ましい結果をもたらすような相互作用のルール （割当規則と支払規則） を設計することである．この分野は電子商取引の拡大にともない，経済学だけでなく，人工知能／エージェント分野でも活発に研究が行われている．その中にメカニズムの単調性に関する研究がある．この研究によって，単調性を満たす割当規則さえ見つかれば，メカニズムが戦略的操作不可能となるような支払規則が存在することが示されている （実装可能性） ．しかし，複数のメールアドレスを用いて不正に利益を増加させるといった架空名義操作に関する性質はほとんど検討されていない．そこで本論文では，架空名義操作に対して，割当規則が満たすべき条件を吟味する．その結果，組合せオークションメカニズムが架空名義操作不可能となる支払規則が存在するために割当規則が満たすべき条件を示した．We identify a simple condition called subadditivity, which characterizes false-name-proof allocation rules in combinatorial auctions. An auction mechanism consists of an allocation rule that defines the allocation of goods for each agent, and a payment rule that defines the payment of a winner. An auction mechanism is false-name-proof if an agent has no incentive for submitting multiple bids from different identifiers. We prove that a deterministic allocation rule will be false-name-proof (when coupled with an appropriate payment rule) if and only if it satisfies subadditivity condition.. |
| 24. |
Characterizing False-Name-Proof Allocation Rules in Combinatorial Auctions
メカニズムデザインとは複数の人間/エージェントが何らかの社会的決定をする場合に,社会的に望ましい結果をもたらす相互作用のルール(例えば,割当規則と支払規則)を設計することである.この分野は電子商取引の拡大に伴い,経済学だけでなく,人工知能/エージェント分野でも活発に研究が行われている.特に,電子商取引のための基盤技術としてオークションメカニズムに関する研究が注目されている.その一つに割当規則の実装可能性に関する研究があり,戦略的操作不可能なオークションメカニズムの割当規則が満たすべき性質を吟味している.しかし,複数のメールアドレスなどを用いて不正に利益を増加させる架空名義操作に関する性質はほとんど検討されていない.そこで本論文では,架空名義操作不可能な組合せオークションメカニズムの割当規則が満たすべき性質を提案する.また,提案した性質を用いて,既存の組合せオークションメカニズムが架空名義操作不可能であるかを検証し,架空名義操作不可能であると信じられてきた二つのメカニズムが,実は架空名義操作可能であることを発見した.. |
| 25. |
Game Theory, Auction Theory for Keyword Auctions(Web Technology, Business Model and Artificial Intelligence). |
| 26. |
RF-002 A False-name-proof Combinatorial Auction Mechanism : A variation of VCG Mechanism. |
| 27. |
RA-007 Characterization of False-name-proof Facility Location Mechanisms. |
| 28. |
*-SAT: Extentions of SAT(Recent Advances in SAT Techniques). |
| 29. |
RF-001 A rule extraction algorithm for combinatorial auctions with automated mechanism design. |
| 30. |
A-024 The Laboratories/Students Problem with Quota Lower Bounds. |
| 31. |
A Rule Extraction Algorithm for Combinatorial Auctions with Automated Mechanisms Design. |
| 32. |
The 2011 IPSJ Best Paper Award：Toward a Foundation of Market Design Theory for the Internet Era. |
| 33. |
Studies on reward mechanisms for self-fulfilling declaration
We investigate a mechanism for giving a right incentive to each agent to predict her own future actions and to declare her predictions truthfully. Obtaining an accurate prediction of customer actions is valuable for certain providers who are required to meet customer demands. If an agent predicts an external event that she cannot control herself, any proper scoring rule can give a right incentive. In our problem setting, an agent needs to predict her own action that she can control to maximize her utility. Also, her (gross) utility can vary based on an eternal event. While proper scoring rules have been proposed for eliciting truthful subjective beliefs/prediction of agents in a prediction market, this work presents a new and interesting application for proper scoring rule. We prove that a mechanism that utilizes any strictly proper scoring rule is only a mechanism that can satisfy our goal, assuming an agent can find an optimal declaration that maximizes her expected utility.. |
| 34. |
RF-002A complexity approach for Pareto efficient exchange with multiple indivisible goods. |
| 35. |
D-8-13 Coalitional Structure Generation Algorithm for Coalitional Games with Externalities. |
| 36. |
An Improvement of MaxSAT Encoding for Coalition Structure Generation Using MC-nets. |
| 37. |
An Improvement of MaxSAT Encoding for Coalition Structure Generation Using MC-nets and Its Evaluations. |
| 38. |
Makoto Yokoo and Satoru Fujita, "Trends of Internet Auctions and Agent-mediated Web Commerce'', New Generation computing, Vol.19, No.4, pp.369-388, 2001.01. |
