Atsushi IWASAKI
| Department of Informatics | Associate Professor |
| Cluster I (Informatics and Computer Engineering) | Associate Professor |
Researcher Information
Research Activity Information
Award
- Jul. 2022
人工知能学会
取り違えのある繰り返し囚人のジレンマにおける協力のダイナミクス
JSAI Annual Conference Student Incentive Award, 村井 伸一郎
Japan society - 2021
見間違えのある繰り返し囚人のジレンマにおける方策勾配法に関する研究
第20回情報科学技術フォーラムFIT2021 船井ベストペーパー賞, 坂本充生;阿部拳之;サイバーエージェント;岩崎 敦
Japan society - 2021
ほぼ公的観測下の囚人のジレンマにおける協力のダイナミクス
第20回情報科学技術フォーラムFIT2021 FIT論文賞, 五十嵐瞭平;岩崎 敦
Japan society - 2020
私的観測下の繰り返し囚人のジレンマにおける協力のダイナミクス
第19 回情報科学技術フォーラムFIT2020 船井ベストペーパー賞, 西野上 和真;五十嵐 瞭平;岩崎 敦
Japan society - 2015
日本ソフトウェア科学会
『計算機科学者のためのゲーム理論入門』シリーズ
日本ソフトウェア科学会第５回解説論文賞, 横尾真;岩崎敦;櫻井祐子;岡本吉央 - 2014
第30 回テレコムシステム技術学生賞, 藤田悦誌;岩崎敦;東藤大樹;横尾真 - 2013
AAMAS-2013
12th International Joint Conference on Autonomous Agents and Multi-Agent System (AAMAS-2013), Best Program Committee Member Nomination - 2013
第12回情報科学技術フォーラムFIT2013 論文賞 - 2012
情報処理学会
2011年度情報処理学会論文賞 - 2011
第10 回情報科学技術フォーラムFIT2011 船井ベストペーパー賞 - 2011
合同エージェントワークショップ＆シンポジウム2011 (JAWS-2011) 優秀論文賞 - 2011
2nd International Joint Agent Workshop & Symposium (iJAWS-2011), Best paper award, - 2011
合同エージェントワークショップ2011 (JAWS-2011) JAWS10 周年記念賞 - 2011
14th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2011), Best paper award - 2010
IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT-2010), Best paper award nomination - 2010
第9 回情報科学技術フォーラムFIT2010 論文賞 - 2010
1st International Joint Agent Workshop & Symposium (iJAWS-2010), Best paper award - 2010
13th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2010), Best paper award nomination - 2009
8th International Joint Conference on Autonomous Agents and Multi-Agent System (AAMAS-2009), Best student paper award nomination - 2009
第25 回テレコムステム技術学生賞 - 2008
7th International Joint Conference on Autonomous Agents and Multi-Agent System (AAMAS-2008), Best student paper award - 2008
2008 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT-2008), Best paper award - 2008
合同エージェントワークショップ＆シンポジウム2007 (JAWS-2007) 最優秀論文賞 - 2007
10th Paci.c Rim International Workshop on Multi-agents (PRIMA-2007), Best paper award - 2004
合同エージェントワークショップ＆シンポジウム2004 (JAWS-2004) 最優秀論文賞
Paper
- Adaptively Perturbed Mirror Descent for Learning in Games
Kenshi Abe; Kaito Ariu; Mitsuki Sakamoto; Atsushi Iwasaki
Proceedings of the Forty-first International Conference on Machine Learning, Jul. 2024, Peer-reviwed
Scientific journal, English - 二人零和ゲームにおける突然変異駆動型正則化先導者追従法の終極反復収束
阿部 拳之; 豊島 健太郎; 坂本 充生; 岩崎 敦
Last, 情報処理学会論文誌, 65, 5, May 2024, Peer-reviwed
Scientific journal, Japanese - Learning Fair Division from Bandit Feedback
Hakuei Yamada; Junpei Komiyama; Kenshi Abe; Atsushi Iwasaki
Last, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, 238, 3106-3114, May 2024, Peer-reviwed, True, with international co-author(s)
International conference proceedings, English - Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games
Kenshi Abe; Kaito Ariu; Mitsuki Sakamoto; Kentaro Toyoshima; Atsushi Iwasaki
Last, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, 206, 7999-8028, Apr. 2023, Peer-reviwed
Scientific journal, English - オンライン環境において公平な資源配分を実現するアルゴリズムに関する研究
山田博瑛; 小宮山純平; 阿部拳之; 岩﨑 敦
情報処理学会第85回全国大会, 2T-01, Mar. 2023
Symposium, Japanese - 研修医配属における地域間格差を調整するための制約のモンテカルロ木探索
板垣圭知; 小宮山純平; 阿部拳之; 岩崎 敦
Last, 情報処理学会第85回全国大会, 2T-08, Mar. 2023
Symposium, Japanese - 公平なインターバルスケジューリング問題に関する研究
酒井洸星; 岩崎 敦
Last, 情報処理学会第85回全国大会, 7S-07, Mar. 2023
Symposium, Japanese - 取り違えのある繰り返し囚人のジレンマにおける単独裏切-相互同期戦略
村井伸一郎; 岩崎 敦
情報処理学会第85回全国大会, 5B-03, Mar. 2023
Symposium, Japanese - Mutation-driven follow the regularized leader for last-iterate convergence in zero-sum games
Kenshi Abe; Mitsuki Sakamoto; Atsushi Iwasaki
Last, Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, PMLR 180, 1-10, 01 Jul. 2022, Peer-reviwed
Scientific journal, English - Anytime Capacity Expansion in Medical Residency Match by Monte Carlo Tree Search
Kenshi Abe; Junpei Komiyama; Atsushi Iwasaki
Last, Proceedings of the 31th International Joint Conference on Artificial Intelligence (IJCAI-2022), Main Track, 3-9, Jun. 2022, Peer-reviwed, with international co-author(s)
Scientific journal, English - 私的観測下の繰り返し囚人のジレンマにおける協力のダイナミクス
西野上 和真; 五十嵐 瞭平; 岩崎 敦
情報処理学会論文誌, 63, 4, 1138-1148, 15 Apr. 2022, Peer-reviwed
Scientific journal, Japanese - Repeated Multimarket Contact with Private Monitoring: A Belief-Free Approach
Atsushi Iwasaki; Tadashi Sekiguchi; Shun Yamamoto; Makoto Yokoo
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI-2020), AAAI Press, 34, 2, 2038-2045, 03 Apr. 2020, Peer-reviwed
Scientific journal, English - Approximately Stable Matchings with General Constraints.
Yasushi Kawase; Atsushi Iwasaki
CoRR, abs/1907.04163, 2019, Peer-reviwed
Scientific journal - Repeated Triangular Trade: Sustaining Circular Cooperation with Observation Errors.
Kota Shigedomi; Tadashi Sekiguchi; Atsushi Iwasaki; Makoto Yokoo
PRIMA 2018: Principles and Practice of Multi-Agent Systems - 21st International Conference(PRIMA), Springer, 242-257, 2018
International conference proceedings - Coalition structure generation in cooperative games with compact representations.
Suguru Ueda; Atsushi Iwasaki; Vincent Conitzer; Naoki Ohta; Yuko Sakurai; Makoto Yokoo
Auton. Agents Multi Agent Syst., Springer US, 32, 4, 503-533, 2018, Peer-reviwed
Scientific journal, English - Approximately Stable Matchings With Budget Constraints.
Yasushi Kawase; Atsushi Iwasaki
Proceedings of the 32th AAAI Conference on Artificial Intelligence (AAAI-2018), 1113-1120, 2018, Peer-reviwed
International conference proceedings, English - Controlled School Choice with Soft Bounds and Overlapping Types
Ryoji Kurata; Naoto Hamada; Atsushi Iwasaki; Makoto Yokoo
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, AI ACCESS FOUNDATION, 58, 153-184, 2017, Peer-reviwed, School choice programs are implemented to give students/parents an opportunity to choose the public school the students attend. Controlled school choice programs need to provide choices for students/parents while maintaining distributional constraints on the composition of students, typically in terms of socioeconomic status. Previous works show that setting soft-bounds, which flexibly change the priorities of students based on their types, is more appropriate than setting hard-bounds, which strictly limit the number of accepted students for each type. We consider a case where soft-bounds are imposed and one student can belong to multiple types, e.g., "financially-distressed" and "minority" types. We first show that when we apply a model that is a straightforward extension of an existing model for disjoint types, there is a chance that no stable matching exists. Thus we propose an alternative model and an alternative stability definition, where a school has reserved seats for each type. We show that a stable matching is guaranteed to exist in this model and develop a mechanism called Deferred Acceptance for Overlapping Types (DA-OT). The DA-OT mechanism is strategy-proof and obtains the student-optimal matching within all stable matchings. Furthermore, we introduce an extended model that can handle both type-specific ceilings and floors and propose a extended mechanism DA-OT* to handle the extended model. Computer simulation results illustrate that DA-OT outperforms an artificial cap mechanism where we set a hard-bound for each type in each school. DA-OT* can achieve stability in the extended model without sacrificing students' welfare.
Scientific journal, English - Achieving Sustainable Cooperation in Generalized Prisoner's Dilemma with Observation Errors
Fuuki Shigenaka; Tadashi Sekiguchi; Atsushi Iwasaki; Makoto Yokoo
Proceedings of the 31th AAAI Conference on Artificial Intelligence (AAAI-2017), AAAI Press, 677-683, 2017, Peer-reviwed
International conference proceedings, English - Near-feasible stable matchings with budget constraints
Yasushi Kawase; Atsushi Iwasaki
Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-2017), 242-248, 2017, Peer-reviwed
Scientific journal, English - Strategyproof matching with regional minimum and maximum quotas
Masahiro Goto; Atsushi Iwasaki; Yujiro Kawasaki; Ryoji Kurata; Yosuke Yasuda; Makoto Yokoo
ARTIFICIAL INTELLIGENCE, ELSEVIER SCIENCE BV, 235, 40-57, Jun. 2016, Peer-reviwed, This paper considers matching problems with individual/regional minimum/maximum quotas. Although such quotas are relevant in many real-world settings, there is a lack of strategyproof mechanisms that take such quotas into account. We first show that without any restrictions on the regional structure, checking the existence of a feasible matching that satisfies all quotas is NP-complete. Then, assuming that regions have a hierarchical structure (i.e., a tree), we show that checking the existence of a feasible matching can be done in time linear in the number of regions. We develop two strategyproof matching mechanisms based on the Deferred Acceptance mechanism (DA), which we call Priority List based Deferred Acceptance with Regional minimum and maximum Quotas (PLDA-RQ) and Round-robin Selection Deferred Acceptance with Regional minimum and maximum Quotas (RSDA-RQ). When regional quotas are imposed, a stable matching may no longer exist since fairness and nonwastefulness, which compose stability, are incompatible. We show that both mechanisms are fair. As a result, they are inevitably wasteful. We show that the two mechanisms satisfy different versions of nonwastefulness respectively; each is weaker than the original nonwastefulness. Moreover, we compare our mechanisms with an artificial cap mechanism via simulation experiments, which illustrate that they have a clear advantage in terms of nonwastefulness and student welfare. (C) 2016 The Authors. Published by Elsevier B.V.
Scientific journal, English - How is Cooperation/collusion Sustained in Repeated Multimarket Contact with Observation Errors?: (Extended Abstract).
Atsushi Iwasaki; Tadashi Sekiguchi; Shun Yamamoto; Makoto Yokoo
Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems(AAMAS), ACM, 1369-1370, 2016
International conference proceedings - Achieving Sustainable Cooperation in Generalized Prisoner's Dilemma with Observation Errors: (Extended Abstract).
Fuuki Shigenaka; Shun Yamamoto; Motohide Seki; Tadashi Sekiguchi; Atsushi Iwasaki; Makoto Yokoo
Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems(AAMAS), ACM, 1323-1324, 2016
International conference proceedings - Repeated Multimarket Contact with Observation Errors
Atsushi Iwasaki; Tadashi Sekiguchi; Shun Yamamoto; Makoto Yokoo
ALGORITHMIC GAME THEORY, SAGT 2016, SPRINGER INT PUBLISHING AG, 9928, 344-345, 2016, Peer-reviwed
International conference proceedings, English - Simplifying Urban Network Security Games with Cut-Based Graph Contraction
Hiroaki Iwashita; Kotaro Ohori; Hirokazu Anai; Atsushi Iwasaki
AAMAS'16: PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS, ASSOC COMPUTING MACHINERY, to appear, 205-213, 2016, Peer-reviwed, The scalability of the algorithm for solving urban network security games, which is an important challenge concerning security game problems, was improved. State-of-the-art solvers have been scaled up to handle real-world networks with tens of thousands of edges; however, it can take days or more when the inputs are varied. Since they do not essentially overcome exponential growth of the strategy space with increasing graph size, an approach, which can be combined with previous ones, is proposed. In particular, a practical approach of simplifying the graphs so that they can be handled within a realistic time is devised and tested. The key idea behind this approach is to restrict the defender's pure strategies to potential ones before calculating an equilibrium solution. The restriction can be tightened for faster computation and loosened for better solution. The following three techniques for computing an optimal solution to the restricted game are proposed and evaluated: (i) contraction of the network based on the restriction, (ii) compact formulation of the optimization problem using weighted edges in place of multiple edges, and (iii) efficient solution using a mixed-integer quadratic programming oracle. They can naturally cope with an extension of the game to one taking width of the roads into account. Furthermore, a heuristic algorithm of finding effective restriction of the game is also proposed.
International conference proceedings, English - How is cooperation/collusion sustained in repeated multimarket contact with observation errors?
Atsushi Iwasaki; Tadashi Sekiguchi; Shun Yamamoto; Makoto Yokoo
AAAI Fall Symposium on Sequential Decision Making for Intelligent Agents, AAAI Press, 46-53, Nov. 2015, Peer-reviwed
International conference proceedings, English - Finding core for coalition structure utilizing dual solution
Atsushi Iwasaki; Suguru Ueda; Naoyuki Hashimoto; Makoto Yokoo
ARTIFICIAL INTELLIGENCE, ELSEVIER SCIENCE BV, 222, 49-66, May 2015, Peer-reviwed, When forming the grand coalition is not possible or optimal, agents need to create a coalition structure. The idea of the core can be extended to such a case. In this paper, we propose an innovative exact algorithm called CoreD to check core-non-emptiness for coalition structures. A more straightforward exact algorithm based on existing techniques, which we call CoreP, first obtains the value of optimal coalition structure by solving an integer programming problem. Then, it checks whether that value can be divided without making a blocking (dissatisfied) coalition. In contrast, CoreD first finds a minimal value of the optimal coalition structure so that there exists no blocking coalition. Next, it checks whether the optimal value equals the minimal value We empirically show that when the core is empty, CoreD is by far superior to CoreP. Also, to find a second-best payoff vector when the core is empty, we propose a new solution concept called the weak epsilon-core(+), which can utilize the approximate value of the optimal coalition structure. Based on the idea of CoreD, we further develop an algorithm for checking the non-emptiness of the weak epsilon-core(+). (C) 2015 Elsevier B.V. All rights reserved.
Scientific journal, English - Can local caution restore global tacit collusion?: Repeated multimarket contact with observation
Atsushi Iwasaki; Tadashi Sekiguchi; Shun Yamamoto; Makoto Yokoo
AAAI Spring Symposium on Applied Computational Game Theory, ...-..., Mar. 2015, Peer-reviwed
Symposium, English - Secure (M+1) st-Price Auction with Automatic Tie-Break
Takashi Nishide; Mitsugu Iwamoto; Atsushi Iwasaki; Kazuo Ohta
TRUSTED SYSTEMS, INTRUST 2014, SPRINGER INT PUBLISHING AG, 9473, 422-437, 2015, Peer-reviwed, In auction theory, little attention has been paid to a situation where the tie-break occurs because most of auction properties are not affected by the way the tie-break is processed. Meanwhile, in secure auctions where private information should remain hidden, the information of the tie can unnecessarily reveal something that should remain hidden. Nevertheless, in most of existing secure auctions, ties are handled outside the auctions, and all the winning candidates or only the non-tied partial bidders are identified in the case of ties, assuming that a subsequent additional selection (or auction) to finalize the winners is held publicly. However, for instance, in the case of the (M + 1) st-price auction, the tied bidders in the (M + 1) st-price need to be identified for such a selection, which implies that their bids (unnecessary private information) are revealed. Hence it is desirable that secure auctions reveal neither the existence of ties nor the losing tied bidders.
To overcome these shortcomings, we propose a secure (M + 1) st-price auction protocol with automatic tie-breaks and no leakage of the tie information by improving the bit-slice auction circuit without increasing much overhead.
International conference proceedings, English - Controlled School Choice with Soft Bounds and Overlapping Types
Ryoji Kurata; Masahiro Goto; Atsushi Iwasaki; Makoto Yokoo
Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-2015), AAAI Press, 951-957, 2015, Peer-reviwed
International conference proceedings, English - Parametric Mechanism Design via Quantifier Elimination.
Atsushi Iwasaki; Etsushi Fujita; Taiki Todo; Hidenao Iwane; Hirokazu Anai; Mingyu Guo; Makoto Yokoo
Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2015), ACM, 1885-1886, 2015, Peer-reviwed
International conference proceedings, English - Improving fairness in nonwasteful matching with hierarchical regional minimum quotas
Masahiro Goto; Ryoji Kurata; Naoto Hamada; Atsushi Iwasaki; Makoto Yokoo
Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2015), ACM, 1887-1888, 2015, Peer-reviwed
International conference proceedings, English - VCG-equivalent in Expectation Mechanism
FUJITA Etsushi; IWASAKI Atsushi; TODO Taiki; YOKOO Makoto
Computer Software, Japan Society for Software Science and Technology, 31, 3, 3_156-3_167, 2014, In this paper, we develop a new class of iterative mechanisms called a <I>VCG-equivalent in expectation</I> mechanism. To guarantee that sincere strategies are an <I>ex post</I> equilibrium, it inevitably asks an irrelevant query, in which a participant has no incentive to answer the query sincerely. Such an irrelevant query causes unnecessary leakage of private information and a different incentive issue. In a VCG-equivalent in expectation mechanism, the mechanism achieves the same allocation as VCG, but the transfers are the same as VCG only in expectation. We show that in a VCG-equivalent in expectation mechanism, sincere strategies constitute a sequential equilibrium. Also, we develop a general procedure for constructing a VCG-equivalent in expectation mechanism that does not ask any irrelevant query. To demonstrate the applicability of this idea in a practical application, we develop a VCG-equivalent in expectation mechanism that can be applied to the Japanese 4G spectrum auction.
Japanese - VCG-equivalent Mechanism in Expectation: General Framework for Constructing Iterative Combinatorial Auction Mechanisms
Atsushi Iwasaki; Etsushi Fujita; Taiki Todo; Yao Miao; Makoto Yokoo
Proceedings of the 12th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2014), IFAAMAS, 699-706, 2014, Peer-reviwed
International conference proceedings, English - VCG-equivalent in Expectation メカニズム
藤田悦誌; 岩崎敦; 東藤大樹; 横尾真
コンピュータソフトウェア, 31, 3, 156-167, 2014, Peer-reviwed
Scientific journal, Japanese - Computing a Payoff Division in the Least Core for MC-nets Coalitional Games
Katsutoshi Hirayama; Kenta Hanada; Suguru Ueda; Makoto Yokoo; Atsushi Iwasaki
PRIMA 2014: PRINCIPLES AND PRACTICE OF MULTI-AGENT SYSTEMS, SPRINGER-VERLAG BERLIN, 8861, 319-332, 2014, Peer-reviwed, MC-nets is a concise representation of the characteristic functions that exploits a set of rules to compute payoffs. Given a MC-nets instance, the problem of computing a payoff division in the least core, which is a generalization of the core-non-emptiness problem that is known to be coNP-complete, is definitely a hard computational problem. In fact, to the best of our knowledge, no algorithm can actually compute such a payoff division for MC-nets instances with dozens of agents. We propose a new algorithm for this problem, that exploits the constraint generation technique to solve the linear programming problem that potentially has a huge number of constraints. Our experimental results are striking since, using 8 GB memory, our proposed algorithm can successfully compute a payoff division in the least core for the instances with up to 100 agents, but the naive algorithm fails due to a lack of memory for instances with 30 or more agents.
International conference proceedings, English - Strategy-proof matching with regional minimum quotas.
Masahiro Goto; Naoyuki Hashimoto; Atsushi Iwasaki; Yujiro Kawasaki; Suguru Ueda; Yosuke Yasuda; Makoto Yokoo
Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2014), IFAAMAS/ACM, 1225-1232, 2014, Peer-reviwed
International conference proceedings, English - Interactive Algorithm for Multi-objective Constraint Optimization
Tenda Okimoto
Transactions of the Japanese Society for Artificial Intelligence, 28, 1, 57-66, Jan. 2013, Peer-reviwed
Scientific journal, Japanese - Finding the core for coalition structure utilizing dual solution
Atsushi Iwasaki; Suguru Ueda; Makoto Yokoo
Proceedings - 2013 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2013, IEEE Computer Society, 2, 114-121, 2013, Peer-reviwed, When forming the grand coalition is not possible/optimal, agents need to create a coalition structure. The idea of the core can be extended to such a case. In this paper, we propose an innovative algorithm called CoreD to check core-non-emptiness for coalition structures. A more straightforward algorithm based on existing techniques, which we call CoreP, first obtains the value of optimal coalition structure by solving an integer programming problem. Then, it checks whether that value can be divided without making a blocking (dissatisfied) coalition. In contrast, CoreD first finds a minimal amount value of optimal coalition structure so that there exists no blocking coalition. Then, it checks whether the optimal value can be equal to the minimal value. We empirically show that when the core is empty, CoreD is by far superior to CoreP. Also, to find a second-best payoff vector when the core is empty, we propose a new solution concept called the weak ε-core+, which can utilize the approximate value of the optimal coalition structure. Based on the idea of CoreD, we further develop an algorithm for checking the non-emptiness of the weak ε-core+. © 2013 IEEE.
International conference proceedings, English - Payoff levels, loss avoidance, and equilibrium selection in games with multiple equilibria: An experimental study
Nick Feltovich; Atsushi Iwasaki; Sobei H. Oda
Economic Inquiry, 50, 4, 932-952, Oct. 2012, Game theorists typically assume that changing a game's payoff levels-by adding the same constant to, or subtracting it from, all payoffs-should not affect behavior. Although this invariance is an implication of the theory when payoffs mirror expected utilities, it is an empirical question when "payoffs" are actually money amounts. Loss avoidance is a phenomenon where payoff-level changes matter when they change the signs of payoffs: gains become losses or vice versa. We report the results of a human-subjects experiment designed to test for two types of loss avoidance: certain-loss avoidance (avoiding a strategy leading to a sure loss, in favor of an alternative that might lead to a gain) and possible-loss avoidance (avoiding a strategy leading to a possible loss, in favor of an alternative that leads to a sure gain). Subjects in the experiment play three versions of Stag Hunt, which are identical up to the level of payoffs, under a variety of treatments. We find strong evidence of behavior consistent with certain-loss avoidance in the experiment. We also find evidence of possible-loss avoidance, although weaker than that for certain-loss avoidance. Our results carry implications for theorists modeling real-life situations with game theory and for experimenters attempting to test theory and interpret observed behavior in terms of theory. © 2011 Western Economic Association International.
Scientific journal, English - Interactive Algorithm for Multi-Objective Constraint Optimization.
Tenda Okimoto; Yongjoon Joe; Atsushi Iwasaki; Toshihiro Matsui; Katsutoshi Hirayama; Makoto Yokoo
Principles and Practice of Constraint Programming - 18th International Conference(CP), Springer, 7514, 561-576, Oct. 2012, Peer-reviwed
International conference proceedings, English - 多目的制約最適化問題：ユーザとの対話型解法の提案
OKIMOTO TENDA; ジョ ヨンジュン; 岩崎 敦; 横尾 真
第11回情報科学技術フォーラム (FIT-2012), 1, 23-30, Sep. 2012, Peer-reviwed
Research society, Japanese - Strategy-proof mechanisms for two-sided matching with minimum and maximum quotas.
Suguru Ueda; Daniel Fragiadakis; Atsushi Iwasaki; Peter Troyan; Makoto Yokoo
International Conference on Autonomous Agents and Multiagent Systems(AAMAS), IFAAMAS, 1327-1328, 2012
International conference proceedings - Automated equilibrium analysis of repeated games with private monitoring: a POMDP approach.
Yongjoon Joe; Atsushi Iwasaki; Michihiro Kandori; Ichiro Obara; Makoto Yokoo
International Conference on Autonomous Agents and Multiagent Systems(AAMAS), IFAAMAS, 1305-1306, 2012
International conference proceedings - A Differential Game Theoretic Model for Real-Time Spectrum Pricing in Cognitive Radio Networks
Dong Hao; Atsushi Iwasaki; Makoto Yokoo
37TH ANNUAL IEEE CONFERENCE ON LOCAL COMPUTER NETWORKS (LCN 2012), IEEE, 236-239, 2012, Peer-reviwed, In cognitive radio networks, one key feature of spectrum trading is its short term or, even, real time, since the spectrum availability, quality, and price keep changing over time. Therefore, a spectrum pricing policy should be dynamically optimal. In this work, we address the real-time optimal pricing problem for primary users. Based on differential game model, we analyze the optimal pricing strategy for QoS-aware dynamic networks in which the secondary users' number and primary users' QoS level keep changing over time. Nash equilibrium is derived and an optimal pricing and QoS setting policy is formulated. Since the Nash equilibrium of our differential game based model deals with optimal pricing in each time instance, the real-time optimal pricing characteristic can be realized.
International conference proceedings, English - False-name-proofness in online mechanisms.
Taiki Todo; Takayuki Mouri; Atsushi Iwasaki; Makoto Yokoo
International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2012, Valencia, Spain, June 4-8, 2012 (3 Volumes), IFAAMAS, 753-762, 2012, Peer-reviwed
International conference proceedings - Handling negative value rules in MC-net-based coalition structure generation.
Suguru Ueda; Takato Hasegawa; Naoyuki Hashimoto; Naoki Ohta; Atsushi Iwasaki; Makoto Yokoo
International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2012, Valencia, Spain, June 4-8, 2012 (3 Volumes), IFAAMAS, 795-804, 2012, Peer-reviwed
International conference proceedings - 多目的分散制約最適化問題における厳密／非厳密解法の提案
沖本天太; ジョヨンジュン; 上田俊; 岩崎敦; 櫻井祐子; 横尾真; 井上克巳
合同エージェントワークショップ＆シンンポジウム (JAWS 2012), Kakegawa, Japan, October 25th, 2012. IEEE Computer Society Japan Chapter JAWS Young Researcher Award受賞, 2012, Peer-reviwed - 部分観測可能マルコフ決定過程を用いた私的観測付き繰り返しゲームにおける均衡分析プログラム
ジョヨンジュン; 岩崎敦; 神取道宏; 小原一郎; 横尾真
情報処理学会論文誌, 53, 11, 1882-7764, 2012, Peer-reviwed
Scientific journal, Japanese - 自動メカニズムデザインを利用した組合せオークションのルール抽出アルゴリズムの提案
毛利貴之; 杉町勇和; 東藤大樹; 岩崎敦; 横尾真
情報処理学会論文誌, 53, 8, 1882-7764, 2012, Peer-reviwed
Scientific journal, Japanese - Effect of DisCSP variable-ordering heuristics in scale-free networks
Tenda Okimoto; Atsushi Iwasaki; Makoto Yokoo
Multiagent and Grid Systems, 8, 2, 127-141, 2012, A Distributed Constraint Satisfaction Problem (DisCSP) is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various algorithms for solving DisCSPs have been developed, which are intended for general purposes, i.e., they can be applied to any network structure. However, if a network has some particular structure, e.g., the network structure is scale-free, we can expect that some specialized algorithms/heuristics, which are tuned for the network structure, can outperform general purpose algorithms/heuristics. In this paper, as an initial step toward developing specialized algorithms for particular network structures, we examine variable-ordering heuristics in scale-free networks. We use the classic asynchronous backtracking algorithm (ABT) as a baseline algorithm and examine the effect of variable-ordering heuristics. First, we show that the choice of variable-ordering heuristics is more influential in scale-free networks than in random networks. Furthermore, we develop a novel variable-ordering heuristic that is specialized to scale-free networks. In the evaluations, we show that our new variable-ordering heuristic is more effective than a standard degree-based variable-ordering heuristic. Our proposed heuristic reduces the required cycles by 30% at the critical point where the required cycles are maximum. © 2012 - IOS Press and the authors. All rights reserved.
International conference proceedings, English - Pseudo-Tree-Based Incomplete Algorithm for Distributed Constraint Optimization with Quality Bounds.
Tenda Okimoto; Yongjoon Joe; Atsushi Iwasaki; Makoto Yokoo; Boi Faltings
Principles and Practice of Constraint Programming - CP 2011 - 17th International Conference(CP), Springer, 6876, 660-674, Sep. 2011, Peer-reviwed
International conference proceedings, English - 擬似木に基づく分散制約最適化問題の精度保証付き非厳密解法の提案
OKIMOTO TENDA; ジョ ヨンジュン; 岩崎 敦; 横尾 真
第25回人工知能学会全国大会 (JSAI-2011), Jun. 2011
Research society, Japanese - Pseudo-tree-based Incomplete Algorithm for Distributed Constraint Optimization with Quality Bounds
Tenda Okimoto; Yongjoon Joe; Atsushi Iwasaki; Makoto Yokoo
The 4th International Workshop on Optimisation in Multi-agent Systems (OPTMAS 2011) (held in conjunction with AAMAS 2011), 52-67, May 2011, Peer-reviwed
Symposium, English - Pseudo-tree-based Algorithm for Approximate Distributed Constraint Optimization with Quality Bounds
Tenda Okimoto; Yongjoon Joe; Atsushi Iwasaki; Makoto Yokoo
The 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), 1269-1270, May 2011, Peer-reviwed
International conference proceedings, English - Pseudo-tree-based algorithm for approximate distributed constraint optimization with quality bounds.
Tenda Okimoto; Yongjoon Joe; Atsushi Iwasaki; Makoto Yokoo
10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011)(AAMAS), IFAAMAS, 1269-1270, 2011
International conference proceedings - Characterizing strategy-proof, revenue monotone allocation rules in auction mechanisms
Taiki Todo; Atsushi Iwasaki; Makoto Yokoo
Transactions of the Japanese Society for Artificial Intelligence, 26, 1, 86-96, 2011, Peer-reviwed, An auction mechanism consists of an allocation rule and a payment rule. There have been several studies on characterizing strategy-proof allocation rules, i.e., if the allocation rule satisfies a condition called weak-monotonicity, an appropriate payment rule is guaranteed to exist. One desirable property that an auction mechanism should satisfy is revenue monotonicity, i.e., a seller's revenue is guaranteed to weakly increase as the number of bidders grows. In this paper, we first identify a simple condition called summation-monotonicity for characterizing strategy-proof and revenue monotone allocation rules. To the best of our knowledge, this is the first attempt to characterize revenue monotone allocation rules. Based on this characterization, we also examine the connections between revenue monotonicity and false-name-proofness, which means a bidder cannot increase his utility by submittingmultiple bids under fictitious names. These two concepts look quite similar but their interaction is complicated. In a single-item auction, we show that they are basically equivalent
a mechanism is false-name-proof if and only if it is strategy-proof and revenue monotone. On the other hand, we show these two conditions cannot coexist in combinatorial auctions
under some minor conditions, there exists no combinatorial auction mechanism that is simultaneously revenue monotone and false-name-proof.
Scientific journal, Japanese - A Compact Representation Scheme of Coalitional Games Based on Multi-Terminal Zero-Suppressed Binary Decision Diagrams
Yuko Sakurai; Suguru Ueda; Atsushi Iwasaki; Shin-Ichi Minato; Makoto Yokoo
AGENTS IN PRINCIPLE, AGENTS IN PRACTICE, SPRINGER-VERLAG BERLIN, 7047, 4-+, 2011, Peer-reviwed, Coalitional games, including Coalition Structure Generation (CSC), have been attracting considerable attention from the AI research community. Traditionally, the input of a coalitional game is a black-box function called a characteristic function. Previous studies have found that many problems in coalitional games tend to be computationally intractable in this black-box function representation. Recently, several concise representation schemes for a characteristic function have been proposed. Among them, a synergy coalition group (SCG) has several good characteristics, but its representation size tends to be large compared to other representation schemes.
We propose a new concise representation scheme for a characteristic function based on a Zero-suppressed Binary Decision Diagram (ZDD) and a SCG. We show our scheme (i) is fully expressive, (ii) can be exponentially more concise than the SCG representation, (iii) can solve core-related problems in polynomial time in the number of nodes, and (iv) can solve a CSG problem reasonably well by utilizing a MIP formulation. A Binary Decision Diagram (BDD) has been used as unified infrastructure for representing/manipulating discrete structures in such various domains in AI as data mining and knowledge discovery. Adapting this common infrastructure brings up the opportunity of utilizing abundant BDD resources and cross-fertilization with these fields.
International conference proceedings, English - Generalizing Envy-Freeness toward Group of Agents.
Taiki Todo; Runcong Li; Xuemei Hu; Takayuki Mouri; Atsushi Iwasaki; Makoto Yokoo
IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, IJCAI/AAAI, 386-392, 2011, Peer-reviwed
International conference proceedings - False-name-proof mechanism design without money.
Taiki Todo; Atsushi Iwasaki; Makoto Yokoo
10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan, May 2-6, 2011, Volume 1-3, IFAAMAS, 651-658, 2011, Peer-reviwed
International conference proceedings - Concise Characteristic Function Representations in Coalitional Games Based on Agent Types.
Suguru Ueda; Makoto Kitaki; Atsushi Iwasaki; Makoto Yokoo
IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, IJCAI/AAAI, 393-399, 2011, Peer-reviwed
International conference proceedings - Concise characteristic function representations in coalitional games based on agent types.
Suguru Ueda; Makoto Kitaki; Atsushi Iwasaki; Makoto Yokoo
10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan, May 2-6, 2011, Volume 1-3, IFAAMAS, 1271-1272, 2011, Peer-reviwed
International conference proceedings - Extension of MC-net-based coalition structure generation: handling negative rules and externalities.
Ryo Ichimura; Takato Hasegawa; Suguru Ueda; Atsushi Iwasaki; Makoto Yokoo
10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan, May 2-6, 2011, Volume 1-3, IFAAMAS, 1173-1174, 2011, Peer-reviwed
International conference proceedings - MC-nets を用いた提携構造形成アルゴリズムの拡張：負の利得と外部性の導入
一村良; 長谷川隆人; 上田俊; 岩崎敦; 横尾真
電子情報通信学会論文誌, J94-D, 11, 1707-1715, 2011, Peer-reviwed
Scientific journal, Japanese - 協力ゲームにおける特性関数のエージェントのタイプに基づく簡略表記法
上田俊; 岩崎敦,横尾
電子情報通信学会論文誌, J94-D, 11, 1716-1728, 2011, Peer-reviwed
Scientific journal, Japanese - 収入単調性を満たすオークションメカニズムの特性及びその架空名義操作不可能性との関係
東藤大樹; 岩崎敦; 横尾真
人工知能学会論文誌, 26, 1, 86-96, 2011, Peer-reviwed
Scientific journal, Japanese - 分散制約最適化問題に基づく提携構造形成問題
上田俊; 岩崎敦; 横尾真
人工知能学会論文誌, The Japanese Society for Artificial Intelligence, 26, 1, 179-189, 2011, Peer-reviwed, Forming effective coalitions is a major research challenge in AI and multi-agent systems. Coalition Structure Generation (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. A partition is called a coalition structure (CS). In traditional works, the value of a coalition is given by a black box function called a characteristic function. In this paper, we propose a novel formalization of CSG, i.e., we assume that the value of a characteristic function is given by an optimal solution of a distributed constraint optimization problem (DCOP) among the agents of a coalition. A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. At first glance, this approach sounds like a very bad idea considering the computational costs, since we need to solve an NP-hard problem just to obtain the value of a single coalition. To optimally solve a CSG, we might need to solve O(2n) DCOP problem instances, where n is the number of agents. However, quite surprisingly, we show that an approximation algorithm, whose computational cost is about the same as solving just one DCOP, can find a CS whose social surplus is at least max(2/n, 1/(w*+1)) of the optimal CS, where w* is the tree width of a constraint graph. Furthermore, we can generalize this approximation algorithm with a parameter k, i.e., the generalized algorithm can find a CS whose social surplus is at least max(2k/n, k/(w*+1)) of the optimal CS by exploring more search space. These results illustrate that the locality of interactions among agents, which is explicitly modeled in the DCOP formalization, is quite useful in developing efficient CSG algorithms with quality guarantees.
Scientific journal, Japanese - 第一価格入札における架空名義入札の影響の解析
桂木敦史; 櫻井祐子; 岩崎敦; 横尾真
人工知能学会論文誌, The Japanese Society for Artificial Intelligence, 26, 1, 199-207, 2011, Peer-reviwed, This paper provides a numerical analysis of Bayesian Nash equilibrium in first-price combinatorial auctions, where participants/agents can use false-name bids. False-name bids is ones submitted by a single agent which uses multiple fictitious names, such as multiple e-mail addresses. It is well-known that even the celebrated Vickrey-Clarke-Groves (VCG) mechanism is influenced by the false-name bids. However, it is not so far investigated how false-name bids affects outcomes of first-price combinatorial auctions, which are widely used in realistic settings. This paper shed a light on the effect of false-name bids in first-price combinatorial auctions, by utilizing Bayesian Nash equilibrium concept via theoretical and numerical analysis.
Scientific journal, Japanese - 疑似木に基づく分散制約最適化問題の制度保証付き非厳密解法の提案
沖本天太; ジョヨンジュン; 岩崎敦; 横尾真
情報処理学会論文誌, 情報処理学会, 52, 12, 3786-3795, 2011, Peer-reviwed, 分散制約最適化問題（DCOP）はマルチエージェントシステムにおける協調問題解決の基本的な枠組みである．DCOPはNP-hardであるため，大規模な問題に対して，比較的少ない計算で近似解を探索する非厳密解法を考える必要がある．しかしながら，既存の非厳密解法のほとんどは解品質を保証しない．数少ない例外としてDALO，bounded max-sum解法，ADPOPがある．本論文では，近似解の新しい評価基準$p$-optimalityに基づく非厳密解法を提案する．本解法の特徴を以下に示す．本解法は，(i)得られる解の絶対/相対誤差の上界をそれぞれ事前/事後に与えることができる，(ii) DCOPの厳密解法で広く用いられている擬似木に基づく解法である，(iii)エージェント数nに関して多項式時間で実行可能なone-shot typeの解法である，(iv)調整可能なパラメータpを持つ．実験では本解法が，解品質を保証する既存の非厳密解法と比べ，より高品質な解および高精度な誤差の上界を与えることを示した．さらに本解法は，これらの非厳密解法と比べ，より高速に求解可能であることを示した．A Distributed Constraint Optimization Problem (DCOP) is a fundamental problem that can formalize various applications related to multi-agent cooperation. Since it is NP-hard, considering faster incomplete algorithms is necessary for large-scale applications. Most incomplete algorithms generally do not provide any guarantees on the quality of solutions. Some notable exceptions are DALO, the bounded max-sum algorithm, and ADPOP. In this paper, we develop a new solution criterion called p-optimality and an incomplete algorithm for obtaining a p-optimal solution. The characteristics of this algorithm are as follows: (i) it can provide the upper bounds of the absolute/relative errors of the solution, which can be obtained a priori/a posteriori, respectively, (ii) it is based on a pseudo-tree, which is a widely used graph structure in complete DCOP algorithms, (iii) it is a one-shot type algorithm, and (iv) it has adjustable parameter p, The evaluation results illustrate that this algorithm can obtain better quality solutions and bounds compared to existing bounded incomplete algorithms, while the run time of this algorithm is shorter.
Scientific journal, Japanese - 分散制約充足問題：特定の制約網に特化した変数順序付けヒューリスティックの提案
沖本 天太; 岩崎 敦; 横尾 真
情報処理学会論文誌, 情報処理学会, 52, 12, 3018-3029, 2011, Peer-reviwed, 分散制約充足問題とは，制約充足問題における変数および制約が複数のエージェントに分散された問題である．既存の分散制約充足アルゴリズムのほとんどは，任意の制約網で動作することを保証している．しかし，特定の制約網，たとえば，ハブを含むようなスケールフリー的な制約網を対象とする場合，対象とする制約網に特化したアルゴリズム/ヒューリスティックが有効となることが予想される．我々の研究は，特定の制約網に特化したアルゴリズムの開発を目的とする．本論文では，その第1歩として，スケールフリー的な制約網に特化した静的な変数順序付けヒューリスティックを提案し，その有効性を示す．実験では，非同期バックトラッキングを用い，エージェントの優先順位の決定法が，スケールフリー的な制約網ではランダム構造の制約網より，アルゴリズムの性能に大きな影響を与えることを示す．さらに，エージェントの優先順位を提案手法と次数順に基づくヒューリスティックによって決定した，非同期バックトラッキングの性能を比較し，提案手法では最大29%の性能向上が得られることを示した．A Distributed Constraint Satisfaction Problem (DisCSP) is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various algorithms for solving DisCSPs have been developed, which are intended for general purposes, i.e., they can be applied to any network structure. However, if a network has some particular structure, e.g., the network structure is scale-free, we can expect that some specialized algorithms or heuristics, which are tuned for the network structure, can outperform general purpose algorithms/heuristics. In this paper, as an initial step toward developing specialized algorithms for particular network structures, we examine variable-ordering heuristics in scale-free networks. We use the classic asynchronous backtracking algorithm as a baseline algorithm and examine the effect of variable-ordering heuristics. First, we show that the choice of variable-ordering heuristics is more influential in scale-free networks than in random networks. Furthermore, we develop a novel variable-ordering heuristic that is specialized to scale-free networks. Experimental results illustrate that our new variable-ordering heuristic is more effective than a standard degree-based variable-ordering heuristic. Our proposed heuristic reduces the required cycles by 29% at the critical point.
Scientific journal, Japanese - モンテカルロゲーム木探索に基づく限量記号付き制約充足問題の実時間解決
馬場里美; 岩崎敦; 横尾真
電子情報通信学会論文誌, J94-D, 11, 1729-1739, 2011, Peer-reviwed
Scientific journal, Japanese - 架空名義操作不可能な施設配置メカニズムの特徴付け
東藤大樹; 岩崎敦; 横尾真
情報処理学会論文誌, 情報処理学会, 52, 4, 1657-1666, 2011, Peer-reviwed, 施設配置問題は，施設の配置場所を適切に決定する問題であり，オペレーションズリサーチや経済学において広く研究が行われてきた．特に戦略的操作不可能（各参加者にとって正直が最良の策）な配置メカニズムの設計が重要な課題として認知されている．一方，インターネットを介してこのような施設配置を実現する場合には，1人のエージェントが複数のエージェントであるかのように振る舞う架空名義操作と呼ばれる不正行為が可能となる．本研究では，施設配置メカニズムの架空名義操作不可能性を定式化し，この性質を満たす配置メカニズムの特徴付けを与える．また，この特徴付けを応用し，架空名義操作不可能な配置メカニズムが達成可能な近似率を解明する．具体的には社会的コストおよび最大コストの2つの評価基準に関して，架空名義操作不可能な配置メカニズムが達成可能な近似率の下界値を解明し，その下界値を達成するメカニズムの存在を示す．さらに，従来施設配置問題や経済学において議論されてきた類似の概念と架空名義操作不可能性との関係を明確にする．具体的には，人口単調性，匿名操作不可能性，架空名義操作不可能性の3つの性質が等価となることを明らかにする．また，架空名義操作不可能な配置メカニズムはつねに結託的戦略的操作不可能性を満たすことを示す．Recently, mechanism design without monetary transfers is attracting much attention, since in many application domains on Internet, introducing monetary transfers is impossible or undesirable. Mechanism design studies how to design mechanisms that result in good outcomes even when agents strategically report their preferences. However, in highly anonymous settings such as the Internet, declaring preferences dishonestly is not the only way to manipulate the mechanism. Often, it is possible for an agent to pretend to be multiple agents, and submit multiple reports using different identifiers, e.g., different e-mail addresses. Such false-name manipulations are more likely to occur in a mechanism without monetary transfers, since submitting multiple reports would be less risky in such a mechanism. In this paper, we formalized false-name manipulations in facility location problems on the real line and obtained a full characterization of false-name-proof facility location mechanisms. By utilizing this characterization, we obtained tight bounds of approximation ratios for two objective functions; the social cost and the maximum cost. We also clarified the connections between false-name-proofness and other related properties. In particular, we showed that both population monotonicity and anonymity-proofness are equivalent to false-name-proofness.
Scientific journal, Japanese - 利得関数の簡潔な記述方法を用いた提携構造形成問題の解法
大田 直樹; Vincent Conitzer; 一村良; 櫻井祐子; 岩崎敦; 横尾真
人工知能学会論文誌, The Japanese Society for Artificial Intelligence, 26, 3, 451-460, 2011, This paper presents a new way of formalizing the Coalition Structure Generation problem (CSG), so that we can apply constraint optimization techniques to it. Forming effective coalitions is a major research challenge in AI and multi-agent systems. CSG involves partitioning a set of agents into coalitions so that social surplus is maximized. Traditionally, the input of the CSG problem is a black-box function called a characteristic function, which takes a coalition as an input and returns the value of the coalition. As a result, applying constraint optimization techniques to this problem has been infeasible. However, characteristic functions that appear in practice often can be represented concisely by a set of rules, rather than a single black-box function. Then, we can solve the CSG problem more efficiently by applying constraint optimization techniques to the compact representation directly. We present new formalizations of the CSG problem by utilizing recently developed compact representation schemes for characteristic functions. We first characterize the complexity of the CSG under these representation schemes. In this context, the complexity is driven more by the number of rules rather than by the number of agents. Furthermore, as an initial step towards developing efficient constraint optimization algorithms for solving the CSG problem, we develop mixed integer programming formulations and show that an off-the-shelf optimization package can perform reasonably well, i.e., it can solve instances with a few hundred agents, while the state-of-the-art algorithm (which does not make use of compact representations) can solve instances with up to 27 agents.
Scientific journal, Japanese - 敵対者に対応する協調問題解決：限量記号付き 分散制約充足問題
馬場里美; 西村直史; 岩崎敦; 櫻井祐子; 横尾真
人工知能学会論文誌, The Japanese Society for Artificial Intelligence, 26, 1, 136-146, 2011, Peer-reviwed, In this paper, we extend the traditional formalization of distributed constraint satisfaction problems (DisCSP) to a quantified DisCSP. A quantified DisCSP includes several universally quantified variables, while all of the variables in a traditional DisCSP are existentially quantified. A universally quantified variable represents a choice of nature or an adversary. A quantified DisCSP formalizes a situation where a team of agents is trying to make a robust plan against nature or an adversary. In this paper, we present the formalization of such a quantified DisCSP and develop an algorithm for solving it by generalizing the asynchronous backtracking algorithm used for solving a DisCSP. In this algorithm, agents communicate a value assignment called a good in addition to the nogood used in asynchronous backtracking. Interestingly, the procedures executed by an adversarial/cooperative agent for good/nogood are completely symmetrical. Furthermore, we develop a method that improves this basic algorithm. Experimental evaluation results illustrate that we observe an easy-hard-easy transition by changing the tightness of the constraints, while very loose problem instances are relatively hard. The modification of the basic algorithm is also effective and reduces the number of cycles by approximately 25% for the hardest problem instances.
Scientific journal, Japanese - Effect of DisCSP Variable-Ordering Heuristics in Scale-free Networks
OKIMOTO TENDA; Atsushi Iwasaki; Makoto Yokoo
In proceedings of the 13th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2010), Springer, 168-180, Nov. 2010, Peer-reviwed
International conference proceedings, English - 誘導幅に基づく分散制約最適化問題の精度保証付き近似解法の提案
OKIMOTO TENDA; 岩崎 敦; 横尾 真
合同エージェントワークショップ＆シンポジウム (JAWS-2010), Oct. 2010, Peer-reviwed
Symposium, Japanese - スケールフリーネットワーク上での非同期バックトラッキングの評価
OKIMOTO TENDA; 岩崎 敦; 横尾 真
第24回人工知能学会全国大会 (JSAI-2010), Jun. 2010
Research society, Japanese - Cooperative problem solving against adversary: quantified distributed constraint satisfaction problem.
Satomi Baba; Atsushi Iwasaki; Makoto Yokoo; Marius-Calin Silaghi; Katsutoshi Hirayama; Toshihiro Matsui
9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010)(AAMAS), IFAAMAS, 781-788, 2010
International conference proceedings - Characterization of Revenue Monotonicity in Combinatorial Auctions.
Taiki Todo; Atsushi Iwasaki; Makoto Yokoo
Proceedings of the 2010 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2010, Toronto, Canada, August 31 - September 3, 2010, IEEE Computer Society Press, 383-390, 2010, Peer-reviwed
International conference proceedings - Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms.
Atsushi Iwasaki; Vincent Conitzer; Yoshifusa Omori; Yuko Sakurai; Taiki Todo; Mingyu Guo; Makoto Yokoo
9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada, May 10-14, 2010, Volume 1-3, IFAAMAS, 633-640, 2010, Peer-reviwed
International conference proceedings - Keyword auction protocol for dynamically adjusting the number of advertisements
Yuko Sakurai; Atsushi Iwasaki; Makoto Yokoo
Web Intelligence and Agent Systems, 8, 4, 331-341, 2010, Peer-reviwed, We propose a keyword auction protocol called the GSP-ExR (GSP with an exclusive right) in which the number of advertisements displayed around search results can be dynamically adjusted. It is an extension of the generalized second-price (GSP) auction, which is currently used for keyword auctions. However, in the GSP, the number of displayed advertisements (slots) is determined in advance. We consider adjusting the number of advertisements dynamically on the basis of the bids to improve both the social surplus and seller's revenue. In the GSP-ExR, the number of slots can be either 1 or K. The GSP-ExR pricing scheme is relatively simple and the seller's revenue is at least as good as that with the GSP. If the highest ranked bidder's bid is high enough, she can exclusively display her advertisement by paying a premium. Otherwise, the GSP-ExR is identical to the GSP. © 2010 - IOS Press and the authors. All rights reserved.
Scientific journal, English - Anonymity-proof shapley value: Compact and computationally efficient solution concept for coalitional games in open anonymous environment
Naoki Ohta; Yasufumi Sato; Atsushi Iwasaki; Makoto Yokoo; Vincent Conitzer
Computer Software, 26, 4, 181-196, 2009, Coalition formation is an important capability for automated negotiation among self-interested agents. In order for coalitions to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Coalitional game theory provides a number of solution concepts for this. However, recent research has revealed that these traditional solution concepts are vulnerable to various manipulations in open anonymous environments such as the Internet. To address this, previous work has developed a solution concept called the anonymity-proof core, which is robust against such manipulations. That work also developed a method for compactly representing the anonymity-proof core. However, the required computational and representational costs are still huge. In this paper, we develop a new solution concept which we call the anonymity-proof Shapley value. We show that the anonymity-proof Shapley value is characterized by certain simple axiomatic conditions, always exists, and is uniquely determined. The computational and representational costs of the anonymity-proof Shapley value are drastically smaller than those of existing anonymity-proof solution concepts.
Scientific journal, Japanese - Introducing Communication in Dis-POMDPs with Finite State Machines.
Yuki Iwanari; Makoto Tasaki; Makoto Yokoo; Atsushi Iwasaki; Yuko Sakurai
Proceedings of the 2009 IEEE/WIC/ACM International Conference on Intelligent Agent Technology(IAT), IEEE Computer Society, 267-270, 2009
International conference proceedings - Characterization of Strategy-Proof, Revenue Monotone Combinatorial Auction Mechanisms and Connection with False-Name-Proofness
Taiki Todo; Atsushi Iwasaki; Makoto Yoko
INTERNET AND NETWORK ECONOMICS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 5929, 561-568, 2009, Peer-reviwed, A combinatorial auction mechanism consists if an allocation rule and a payment rule. There have been several studies on characterizing strategy-proof allocation rules. lit particular, conditions called weak-monotonicity has been identified as a lull characterization (of them. On the other hand, revenue monotonicity is recognized as one of the desirable properties. A combinatorial auction mechanism is revenue monotone if a seller's revenue is guaranteed to weakly increase as the number of bidders grows. Though the property is quite reasonable, there exists virtually no work on the characterization. In this paper, we identified a simple condition called sunrmation-monotonicity. We then proved that we call construct a strategy-proof, revenue monotone mechanism if and only if the allocation rule satisfies weak-monotonicity and summation-monotonicity. To the best of our knowledge, this is the first attempt to characterize revenue monotone allocation rules. In addition, we shed light on a connection between revenue monotonicity and false-name-proolness. In fact, we proved that, assuming a natural condition, revenue monotonicity is equivalent to false-name-proofness for single-item auctions.
International conference proceedings, English - Multiagent Planning with Trembling-Hand Perfect Equilibrium in Multiagent POMDPs
Yuichi Yabu; Makoto Yokoo; Atsushi Iwasaki
AGENT COMPUTING AND MULTI-AGENT SYSTEMS, SPRINGER-VERLAG BERLIN, 5044, 13-24, 2009, Peer-reviwed, Multiagent Partially Observable Markov Decision Processes are a popular model of multiagent systems with uncertainty. Since the computational cost for finding an optimal joint policy is prohibitive, a Joint Equilibrium-based Search for Policies with Nash Equilibrium (JESP-NE) is proposed that finds a locally optimal joint policy in which each policy is a best response to other policies, i.e., the joint policy is a Nash equilibrium.
One limitation of JESP-NE is that the quality of the obtained joint policy depends on the predefined default policy. More specifically, when finding a best response, if some observation have zero probabilities, JESP-NE uses this default policy. If the default policy is quite bad, JESP-NE tends to converge to a sub-optimal joint policy.
In this paper, we propose a method that finds a locally optimal joint policy based on a concept called Trembling-hand Perfect Equilibrium (TPE). In finding a TPE, we assume that an agent might make a mistake in selecting its action with small probability. Thus, an observation with zero probability in JESP-NE will have non-zero probability. We no longer use the default policy. As a result, JESP-TPE can converge to a better joint policy than the JESP-NE, which we confirm this fact by experimental evaluations.
International conference proceedings, English - Coalition Structure Generation Utilizing Compact Characteristic Function Representations
Naoki Ohta; Vincent Conitzer; Ro Ichimura; Yuko Sakurai; Atsushi Iwasaki; Makoto Yokoo
PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, SPRINGER-VERLAG BERLIN, 5732, 623-+, 2009, Peer-reviwed, This paper presents a, new way of formalizing the Coalition Structure Generation problem (CSG), so that we can apply constraint optimization techniques to it. Forming effective coalitions is a major research challenge in AI and of multi-agent systems. CSG involves partitioning a. set of agents into coalitions so that social surplus is maximized. Traditionally, the input of the CSG problem is a, black-box function called a, which takes a, coalition as an input and returns the value of the coalition. As a, result, applying constraint optimization techniques to this problem has been feasible. However, characteristic functions that appear in practice often can lie represented concisely by a set of rules, rather than a single black-box function. Then, we can solve the CSG problem more efficiently by applying constraint optimization techniques to the compact; representation directly.
We present; new formalizations of the CSG problem by utilizing recently developed compact representation schemes for characteristic functions. We first characterize the complexity of the CSG under these representation schemes. In this context, the complexity is driven more by the number of rules rather than by the number of agents. Furthermore, as an initial step towards developing efficient constraint optimization algorithms for solving the CSG problem, we develop mixed integer programming formulations and show that an off-the-shelf optimization package can perform reasonably well, i.e., it can solve instances with a few hundred agents, while the state-of-the-art algorithm (which does not make use of compact representations) can solve instances with up to 27 agents.
International conference proceedings, English - Secure Keyword Auction: Preserving Privacy of Bidding Prices and CTRs.
Yuko Sakurai; Makoto Yokoo; Atsushi Iwasaki; Koutarou Suzuki
Proceedings of the 2009 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2009, Milan, Italy, 15-18 September 2009, IEEE Computer Society, 419-422, 2009, Peer-reviwed
International conference proceedings - 開環境での協力ゲームにおける解の簡略記述法
大田直樹; 岩崎敦; 横尾真; Vincent Conitzer; Tuomas Sandholm
情報処理学会論文誌, 情報処理学会, 50, 12, 3211-3221, 2009
Scientific journal, Japanese - 匿名操作不可能シャプレイ値：開環境での協力ゲームへのシャプレイ値の拡張
大田直樹; 佐藤恭史; 岩崎敦; 横尾真; Vincent Conitzer
コンピュータソフトウェア,, 26, 4, 4 181-4 196, 2009, Peer-reviwed
Scientific journal, Japanese - 架空名義操作不可能な組合せオークションの割当規則の特性
東藤大樹; 岩崎敦; 横尾真; 櫻井祐子
電子情報通信学会論文誌, J92-D, 11, 1890-1901, 2009, Peer-reviwed
Scientific journal, Japanese - Take-it-or-leave-it 方式に基づく再配分メカニズムの提案
櫻井祐子; 斉藤恭昌; 横尾真; 岩崎敦
電子情報通信学会論文誌, J92-D, 11, 1890-1901, 2009, Peer-reviwed
Scientific journal, Japanese - セキュアキーワード広告オークションプロトコルの提案
櫻井祐子; 鈴木幸太郎; 岩崎敦; 横尾真
電子情報通信学会論文誌, J92-D, 11, 1881-1889, 2009, Peer-reviwed
Scientific journal, Japanese - GSP-ExR: GSP protocol with an exclusive right for keyword auctions
Yuko Sakurai; Atsushi Iwasaki; Yasumasa Saito; Makoto Yokoo
Proceeding of the 17th International Conference on World Wide Web 2008, WWW'08, 1089-1090, 2008, Peer-reviwed, We propose a keyword auction protocol called the Generalized Second Price with an Exclusive Right (GSP-ExR). In existing keyword auctions, the number of displayed advertisements is determined in advance. Thus, we consider adjusting the number of advertisements dynamically based on bids. In the GSP-ExR, the number of slots can be either 1 or K. When K slots are displayed, the protocol is identical to the GSP. If the value per click of the highest ranked bidder is large enough, then this bidder can exclusively display her advertisement by paying a premium. Thus, this pricing scheme is relatively simple and seller revenue is at least as good as the GSP. Also, in the GSP-ExR, the highest ranked bidder has no incentive to change the number of slots by over/under-bidding as long as she retains the top position.
International conference proceedings, English - Keyword auction protocol for dynamically adjusting the number of advertisements
Yuko Sakurai; Atsushi Iwasaki; Makoto Yokoo
Proceedings - 2008 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2008, 410-416, 2008, Peer-reviwed, Search engines including Yahoo! and Google utilize a keyword auction for ranking the advertisements displayed around the search results. In existing keyword auctions called the GSP, the number of displayed advertisements (slots) is determined in advance. Therefore, we consider adjusting the number of advertisements dynamically based on bids in order to improve both social surplus and seller's revenue. For example, we allow a bidder to display her advertisement exclusively when she is willing to pay a premium. We propose a new keyword auction protocol called the GSP-ExR in which the number of slots can be either 1 or K. The GSP-ExR pricing scheme is relatively simple and the seller's revenue is at least as good as with the GSP. If the highest ranked bidder's bid is large enough, she can exclusively display her advertisement by paying a premium. Otherwise, the GSP-ExR is identical to the GSP. © 2008 IEEE.
International conference proceedings, English - Beyond quasi-linear utility: Strategy/false-name-proof multi-unit auction protocols
Yuko Sakurai; Yasumasa Saito; Atsushi Iwasaki; Makoto Yokoo
Proceedings - 2008 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2008, 417-423, 2008, Peer-reviwed, We develop strategy/false-name-proof multi-unit auction protocols for non-quasi-linear utilities. One almost universal assumption in auction theory literature is that each bidder has quasi-linear utility. However, in practice, a bidder might have some kind of financial condition including budget constraints. The Vickrey-Clarke-Groves (VCG) protocol is designed to be truthful under the quasi-linear assumption and will break down if this assumption does not hold. We show with a simple modification, the VCG can handle non-quasi-linear utilities. However, there are possibilities that the modified VCG sacrifices significant efficiency loss, since it only uses the gross utilities for determining tentative allocation and payments. Also, it has been shown that the VCG is vulnerable to a false-name bid which is a new type of cheating on the Internet. To improve efficiency without collecting the entire utility functions and guarantee falsename-proofness, we develop a false-name-proof open ascending auction protocol. © 2008 IEEE.
International conference proceedings, English - 適切な掲載数を決定するキーワード広告オークションの提案,
櫻井祐子; 岩崎敦; 横尾真
コンピュータソフトウェア, 日本ソフトウェア科学会, 25, 4, 60-67, 2008, Peer-reviwed, 現在,Yahoo!やGoogleなどの検索エンジンでは検索結果の周囲に関連した広告が表示される.これら広告の掲載順位を決定するためにオークションが利用されている.既存のキーワード広告オークションでは掲載数は固定されているが,掲載数を入札額に応じて決定することにより,社会的余剰が増加することが予想される.従って,掲載数が可変の場合を対象とした新しいプロトコルを提案する,まず,Vickrey-Clarke-Groves (VCG)メカニズムを適用したプロトコルを提案する.VCGメカニズムは理論的に望ましい性質を持つ一方で,支払額の計算が複雑であるなどの課題がある.そこで,既存プロトコルの一般化第二価格入札(GSP)に基づき,より実践的なプロトコルの独占権付き一般化第二価格入札(GSP-ExR)の提案を行う.具体的には,最高入札者はプレミアムを払うことで独占的に広告を表示させることを可能にする.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. The first protocol is based on the Vickrey-Clarke-Groves (VCG) mechanism. Although this protocol has good theoretical characteristics such as strategy-proofness, determining the payment is quite complicated. The second protocol, which we call the GSP with Exculsive Right (GSP-ExR), eliminates these VCG drawbacks. If the value per click of the highest ranked bidder is large enough, then this bidder can exclusively display his advertisement by paying a premium.
Scientific journal, Japanese - チーム選択問題のための架空名義操作不可能なオークションメカニズムの提案
斎藤恭昌; 岩崎敦; 横尾真; David Kempe; Mahyar Salek
コンピュータソフトウェア, 25, 4, 199-207, 2008, Peer-reviwed
Scientific journal, Japanese - Implementing a strategyproof greedy-allocation combinatorial auction and extending to ascending auction
Takayuki Ito; Makoto Yokoo; Shigeo Matsubara; Atsushi Iwasaki
Systems and Computers in Japan, 38, 9, 44-51, Aug. 2007, Peer-reviwed, This paper proposes a new combinatorial auction protocol called Average-Max-Minimal-Bundle (AM-MB) protocol. The characteristics of the AM-MB protocol are as follows: (i) it is strategyproof, that is, truth-telling is a dominant strategy, (ii) the computational overhead is very low, since it allocates bundles greedily thereby avoiding an explicit combinatorial optimization problem, and (iii) it can obtain higher social surplus and revenue than can the Max-Minimal-Bundle (M-MB) protocol, which also satisfies (i) and (ii). Furthermore, this paper extends the AM-MB protocol to an open ascending-price protocol in which straight-forward bidding is an ex-post Nash equilibrium. © 2007 Wiley Periodicals, Inc.
Scientific journal, English - False-name-proof mechanisms for hiring a team
Atsushi Iwasaki; David Kempe; Yasumasa Saito; Mahyar Salek; Makoto Yokoo
INTERNET AND NETWORK ECONOMICS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 4858, 245-+, 2007, Peer-reviwed, We study the problem of hiring a team of selfish agents to perform a task. Each agent is assumed to own one or more elements of a set system, and the auctioneer is trying to purchase a feasible solution by conducting an auction. Our goal is to design auctions that are truth-: ful and false-name-proof, meaning that it is in the agents' best interest to reveal ownership of all elements (which may not be known to the auctioneer a priori) as well as their true incurred costs. We first propose and analyze a false-name-proof mechanism for the special cases where each agent owns only one element in reality. We prove that its frugality ratio is bounded by n2(n), which nearly matches a lower bound of Omega(2(n)) for all false-name-proof mechanisms in this scenario. We then propose a second mechanism. It requires the auctioneer to choose a reserve cost a priori, and thus does not always purchase a solution. In return, it is false-name-proof even when agents own multiple elements. We experimentally evaluate the payment (as well as social surplus) of the second mechanism through simulation.
International conference proceedings, English - Reinforcement learning on monopolistic intermediary games: Subject experiments and simulation
Atsushi Iwasaki; Kazuhito Ogawa; Makoto Yokoo; Sobei H. Oda
AGENT-BASED APPROACHES IN ECONOMIC AND SOCIAL COMPLEX SYSTEMS IV, SPRINGER-VERLAG TOKYO, 3, 131-+, 2007, Peer-reviwed
International conference proceedings, English - 摂動完全均衡に基づくマルチエージェント部分観測可能マルコフ決定過程のプラン構築
籔悠一; 横尾真; 岩崎敦
電子情報通信学会論文誌, J90-D, 9, 2314-2323, 2007, Peer-reviwed
Scientific journal, Japanese - False-name-proof combinatorial auction protocol: Groves Mechanism with SubModular Approximation.
Makoto Yokoo; Toshihiro Matsutani; Atsushi Iwasaki
5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006)(AAMAS), ACM, 1135-1142, 2006
International conference proceedings - A Compact Representation Scheme for Coalitional Games in Open Anonymous Environments.
Naoki Ohta; Atsushi Iwasaki; Makoto Yokoo; Kohki Maruono; Vincent Conitzer; Tuomas Sandholm
Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference(AAAI), AAAI Press, 697-702, 2006
International conference proceedings - A new solution concept for coalitional games in open anonymous environments
Makoto Yokoo; Vincent Conitzer; Tuomas Sandholm; Naoki Ohta; Atsushi Iwasaki
NEW FRONTIERS IN ARTIFICIAL INTELLIGENCE, SPRINGER-VERLAG BERLIN, 4012, 53-64, 2006, Peer-reviwed, Coalition formation is a key aspect of automated negotiation among self-interested agents. In order for coalitions to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Various solution concepts (such as the Shapley value, core, least core, and nucleolus) have been proposed. In this paper, we demonstrate how these concepts are vulnerable to various kinds of manipulations in open anonymous environments such as the Internet. These manipulations include submitting false names (one acting as many), collusion (many acting as one), and the hiding of skills. To address these threats, we introduce a new solution concept called the anonymity-proof core, which is robust to these manipulations. We show that the anonymity-proof core is characterized by certain simple axiomatic conditions. Furthermore, we show that by relaxing these conditions, we obtain a concept called the least anonymity-proof core, which is guaranteed to be non-empty.
Scientific journal, English - 架空名義入札に頑健な組合せオークションプロトコルの提案と評価：バンドルサイズ優先プロトコル
松谷俊宏; 横尾真; 岩崎敦
情報処理学会論文誌, Information Processing Society of Japan (IPSJ), 47, 5, 1406-1414, 2006, Peer-reviwed, This paper develops a new false-name proof, sealed-bid combinatorial auction protocol called Bundle Size Ordered (BSO) protocol. As Internet auctions become popular, we must consider the possibility of a new type of fraud called false-name bids that are submitted by a single buyer who uses multiple fictitious names such as multiple e-mail addresses. We develop the BSO protocol and compare its performance with traditional protocols. Our simulation result shows that the BSO outperforms existing false-name proof protocols in large scale combinatorial auctions.
Scientific journal, Japanese - 匿名の開環境下における協力ゲームについて
横尾真; Vincent Conitzer; Tuomas Sandholm; 大田直樹; 岩崎敦
情報処理学会論文誌, 47, 5, 1451-1462, 2006
Scientific journal, Japanese - Greedyな割当て手法に基づくStrategy-proofな 組合せオークションプロトコルと公開競上げ式プロトコルへの拡張
伊藤孝行; 横尾真; 松原繁夫; 岩崎敦
電子情報通信学会論文誌, The Institute of Electronics, Information and Communication Engineers, J89-D, 5, 943-953, 2006, Peer-reviwed, 本論文では,新たな組合せオークションプロトコルとしてAM-MB(Average-Max-Minimal-Bundle)プロトコルを提案する.AM-MBプロトコルの特長を以下の(i),(ii),及び(iii)に示す:(i)strategy-proofである.すなわち,真の申告が支配戦略である.(ii)勝者決定及び支払額計算のための計算コストが小さい.これは,AM-MBプロトコルでは組合せオークションを扱うが,バンドルをグリーディな方法で割り当てることによって,組合せ最適化問題を解く必要がないためである.(iii)既存のM-MB(Max-Minimal-Bundle)プロトコルと比較して社会的余剰及び収益が大きい.既存のM-MBプロトコルは,(i)及び(ii)を満たす組合せオークションプロトコルである.更に,本論文では,AM-MBプロトコルを公開競上げ式組合せオークションプロトコルに拡張する.本公開競上げ式組合せオークションでは,正直な(straightforward)入札が事後ナッシュ均衡であることを証明する.
Scientific journal, Japanese - A robust open ascending-price multi-unit auction protocol against false-name bids
A Iwasaki; M Yokoo; K Terada
DECISION SUPPORT SYSTEMS, ELSEVIER SCIENCE BV, 39, 1, 23-39, Mar. 2005, Peer-reviwed, This paper develops a new ascending-price multi-unit auction protocol that has the following characteristics: (i) it has an open format, and (ii) sincere bidding is an equilibrium strategy even if the marginal values of each agent can increase and agents can submit false-name bids. False-name bids are bids submitted under fictitious names such as multiple e-mail addresses, which can be done easily on the Internet. This is the first protocol that has both of these characteristics. Our simulation results indicate that the developed protocol obtains a social surplus close to Pareto efficient. (C) 2004 Elsevier B.V. All rights reserved.
Scientific journal, English - A New Strategy-Proof Greedy-Allocation Combinatorial Auction Protocol and Its Extension to Open Ascending Auction Protocol.
Takayuki Ito 0001; Makoto Yokoo; Atsushi Iwasaki; Shigeo Matsubara
Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference(AAAI), AAAI Press / The MIT Press, 261-268, 2005
International conference proceedings - Coalitional Games in Open Anonymous Environments
Makoto Yokoo; Vincent Conitzer; Tuomas Sandholm; Naoki Ohta; Atsushi Iwasaki
19TH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI-05), IJCAI-INT JOINT CONF ARTIF INTELL, 1668-1669, 2005, Peer-reviwed
International conference proceedings, English - 複数同一財権利配分型オークションの安定性：被験者実験による検証
岩崎敦; 松田昌史; 横尾真
電気情報通信学会論文誌, J88-D, 9, 1321-1330, 2005, Peer-reviwed
Research institution, Japanese - A robust open ascending-price multi-unit auction protocol against false-name bids
Atsushi Iwasaki; Makoto Yokoo; Kenji Terada
Transactions of the Japanese Society for Artificial Intelligence, ACM, 19, 4, 334-342, 2004, Peer-reviwed, This paper develops a new ascending-price multi-unit auction protocol that has following characteristics: (i) it has an open format, (ii) sincere bidding is an equilibrium strategy even if the marginal utilities of each agent can increase and agents can submit false-name bids. False-name bids are bids submitted under fictitious names such as multiple e-mail addresses, which can be done easily in the Internet. This is the first protocol that has these two characteristics. We show that our new protocol outperforms an existing protocol, which satisfies (ii), with respect to the social surplus and the seller's revenue.
Scientific journal, Japanese - Stability of the Truth-Telling Strategy in Multi-Unit Option Allocation Auctions: Laboratory Experimentation.
Atsushi Iwasaki; Makoto Yokoo; Masafumi Matsuda
3rd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2004)(AAMAS), IEEE Computer Society, 1282-1283, 2004
International conference proceedings - 架空名義入札に頑健な公開競上げ式複数同一財オークションプロトコル
岩崎 敦; 横尾 真; 寺田 賢二
人工知能学会誌, 19, 4, 334-342, 2004, Peer-reviwed
Scientific journal, Japanese - Does reinforcement learning simulate threshold public goods games?: A comparison with subject experiments
A Iwasaki; S Imura; SH Oda; Hatono, I; K Ueda
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E86D, 8, 1335-1343, Aug. 2003, Peer-reviwed, This paper examines the descriptive power and the limitations of a simple reinforcement learning model (REL), comparing the simulation results with the results of an economic experiment employing human subjects. Agent-based computational economics and experimental economics are becoming increasingly popular as tools for economists. A new variety of learning model using games with a unique equilibrium is proposed and examined in both of the fields mentioned above. However, little attention is given to games with multiple equilibria. We examine threshold public goods games with two types of equilibria, where each player in a five-person group simultaneously contributes the public goods from her private endowments. In the experiments, we observe two patterns of the subjects' behavior: the cooperative and non-cooperative patterns. Our simulation results show that the REL reproduces the cooperative pattern, but does not reproduce the non-cooperative pattern. However, the results suggest that the REL does reproduce the non-cooperative pattern in terms of the agents' internal states. That implies that deterministic strategies would be required to reproduce the non-cooperative pattern in the games. We show an example of the REL with deterministic strategies.
Scientific journal, English - Design and evaluation of the recycle of home appliances: An application of market microstructure theory
K Ueda; N Nishino; A Iwasaki; SH Oda; Hatono, I
SECOND INTERNATIONAL SYMPOSIUM ON ENVIRONMENTALLY CONSCIOUS DESIGN AND INVERSE MANUFACTURING, PROCEEDINGS, IEEE COMPUTER SOC, 678-683, 2001, Peer-reviwed, This paper describes how a recycling market is constructed and what conditions are necessary to realize the recycling. Recently we face the various environment problems and we are trying to solve them. In Japan, the Law for Recycling of Specified Kinds of Home Appliances was enforced in April 2001. Firms have responsibility for recycling their own products, while consumers have to pay money for wastes' disposal. We present the recycling market model based on the law, and analyze the recycling market by applying to Market Microstructure Theory. As a result, we specify the recycling market equilibrium and analyze the market effect of the life of products and the conditions for holding the market.
International conference proceedings, English - Simulating a N-person multi-stage game for making a state
A Iwasaki; SH Oda; K Ueda
SIMULATED EVOLUTION AND LEARNING, SPRINGER-VERLAG BERLIN, 1585, 309-316, 1999, Peer-reviwed, This paper describes how a state emerges and collapses that makes it possible for citizens to do something which they will not do voluntarily. The model is a generalisation of the multi-stage game of Okada and Sakakibara (1991). The general model, its mathematical analysis with condition for simplicity and simulations for more general cases are presented. The results of simulations suggest that selfish but rational people may agree to make a state, which grows as the public capital stock accumulates but collapses when the stock reaches a certain level.
Scientific journal, English
MISC
- Approximately Stable Matchings with Budget Constraints.
Yasushi Kawase; Atsushi Iwasaki
2017, CoRR, abs/1711.07359, journals/corr/abs-1711-07359 - Equilibrium Search Program of Repeated Games with Private Monitoring
山本 駿; 岩崎 敦; 趙 登吉
人工知能学会, 2014, 人工知能学会全国大会論文集, 28, 1-4, Japanese, 1347-9881, 40020085695, AA11578981 - RF-004 地域制約の下での戦略的操作不可能なマッチングメカニズム(F分野:人工知能・ゲーム)
橋本 直幸; 上田 俊; 岩崎 敦; 安田 洋祐; 横尾 真
FIT(電子情報通信学会・情報処理学会)運営委員会, 20 Aug. 2013, 情報科学技術フォーラム講演論文集, 12, 2, 49-56, Japanese, 110009814441, AA1242354X - RA-007 双対解を用いた提携構造付きコアの非空判定アルゴリズムの高速化(A分野:モデル・アルゴリズム・プログラミング,査読付き論文)
岩崎 敦; 上田 俊; 横尾 真
FIT(電子情報通信学会・情報処理学会)運営委員会, 20 Aug. 2013, 情報科学技術フォーラム講演論文集, 12, 1, 49-56, Japanese, 110009814582, AA1242354X - An Overview of Studies on Game Theory and Mechanism Design(
Agent Technology)
Iwasaki Atsushi; Todo Taiki
The Japanese Society for Artificial Intelligence, 01 May 2013, Journal of Japanese Society for Artificial Intelligence, 28, 3, 389-396, Japanese, 0912-8085, 110009604070 - Game Theory for Computer Scientists : Cooperative Games
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
日本ソフトウェア科学会 ; 1984-, 25 Apr. 2013, コンピュータソフトウェア, 30, 2, 33-51, Japanese, 0289-6540, 10031151473 - Game Theory for Computer Scientist : Mechanism Design (Advanced)
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
This tutorial focuses on designing a mechanism that achieves a socially desirable outcome or a goal of the designer that arises from some practical demands, as several advanced topics on <IT>mechanism design</IT> theory. We first briefly explains the theory of combinatorial auctions via the most well-known Vickrey-Clarke-Groves mechanism. Second, as an example that designs a new mechanism for a practical demand, we introduce false-name bids and illustrate how we improve a trivial robust mechanism against false-name bids. Furthermore, we explore models and several theoretical results on mechanisms of a keyword auction and a two-sided matching as other well-known topics of mechanism design theory., Japan Society for Software Science and Technology, 25 Jan. 2013, Computer Software, 30, 1, 34-52, Japanese, 0289-6540, 10031138249 - VCG-equivalent in Expectation Mechanism : General Framework for Constructing Iterative Combinatorial Auction Mechanisms
藤田 悦誌; 岩崎 敦; 東藤 大樹
人工知能学会, 2013, 人工知能学会全国大会論文集, 27, 1-4, Japanese, 1347-9881, 40020291543, AA11578981 - A theoretical design and evaluation of matching mechanisms with minimum quotas
後藤 誠大; 岩崎 敦; 上田 俊
人工知能学会, 2013, 人工知能学会全国大会論文集, 27, 1-4, Japanese, 1347-9881, 40020291970, AA11578981 - Game Theory for Computer Scientists — Cooperative Games —
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
This tutorial introduces a cooperative game theory which is one of main parts in game theory. A cooperative game theory consists of two major research topics. The first topic involves how to divide the value of the coalition among agents. We explain the desirable ways of dividing the rewards among cooperative agents, called solution concepts. The traditional cooperative game theory provides a number of solution concepts, such as the core, the Shapley value, and the nucleolus. We introduce some algorithms for dividing the obtained rewards among agents and show their computational complexities. The second topic involves partitioning a set of agents into coalitions so that the sum of the rewards of all coalitions is maximized. This is called Coalition Structure Generation problem (CSG). We explain efficient constraint optimization algorithms for solving the CSG problem. Furthermore, we introduce concise representation schemes for a characteristic function, since it is likely that we can solve solution concepts/CSG problem more efficiently by utilizing concise representation methods for a game., Japan Society for Software Science and Technology, 2013, Computer Software, 30, 2, 2_33-2_51, Japanese, 0289-6540, 130004892257 - Equilibrium Analysis Program of Repeated Games with Private Monitoring: A POMDP Approach
ジョヨンジュン; 岩崎 敦; 神取 道宏; 小原 一郎; 横尾 真
本論文では不完全私的観測付き繰返しゲームの均衡を分析するプログラムを提案する．不完全私的観測付き繰返しゲームは，プレイヤが相手の行動についてノイズを含むシグナルを観測し，そのシグナルを他のプレイヤは観測できないという特徴を持つ．こうしたゲームは人工知能や経済の分野において様々な適用領域を持つため，大きく注目されている．しかし，このゲームにおける均衡を求めるには，非常に複雑な統計的推論が必要になるため，従来難しい未解決問題として知られていた．近年，均衡における振舞いを有限状態オートマトン（finite state automaton，FSA）で記述し，部分観測可能マルコフ決定過程（partially observable Markov decision process，POMDP）の理論を用いることで，あるFSAが均衡を構成するかどうかを明らかにできることが示された．しかし，その具体的な実装方法や実際の問題へ適用するためのプログラムは提供されていない．そこで本論文ではまず，標準的なPOMDPソルバのラッパとなるプログラムを開発する．このプログラムでは私的観測付き繰返しゲームの記述とFSAを入力として，そのFSAが対称的均衡を構成するかどうかを自動的に確認できる．さらに，このプログラムを繰返し囚人のジレンマに適用し，k-期相互処罰（k-MP）と呼ぶ新しいFSAのクラスを発見した．k-MPにおけるプレイヤは，初めに協力し相手の裏切りを観測するとそれ以降自分も裏切るが，続けてk回裏切りを観測すると元に戻り協力する．このプログラムを用いて状態数3以下のFSAを全探索した結果，繰返しゲームにおける観測構造パラメータのいくらかの範囲で，2-MPが他の純粋戦略均衡より優れており，従来よく知られている均衡である無限期罰則のトリガ戦略（grim-trigger）よりも効率的，つまり高い平均利得を実現することが分かった．The present paper investigates repeated games with imperfect private monitoring, where each player privately receives a noisy observation (signal) of the opponent's action. Such games have been paid considerable attention in the AI and economics literature. Since players do not share common information in such a game, characterizing players' optimal behavior is substantially complex. As a result, identifying pure strategy equilibria in this class has been known as a hard open problem. Recently, Kandori and Obara (2010) showed that the theory of partially observable Markov decision processes (POMDP) can be applied to identify a class of equilibria where the equilibrium behavior can be described by a finite state automaton (FSA). However, they did not provide a practical method or a program to apply their general idea to actual problems. We first develop a program that acts as a wrapper of a standard POMDP solver, which takes a description of a repeated game with private monitoring and an FSA as inputs, and automatically checks whether the FSA constitutes a symmetric equilibrium. We apply our program to repeated Prisoner's dilemma and find a novel class of FSA, which we call k-period mutual punishment (k-MP). The k-MP starts with cooperation and defects after observing a defection. It restores cooperation after observing defections k-times in a row. Our program enables us to exhaustively search for all FSAs with at most three states, and we found that 2-MP beats all the other pure strategy equilibria with at most three states for some range of parameter values and it is more efficient in an equilibrium than the grim-trigger., 情報処理学会, 15 Nov. 2012, 情報処理学会論文誌, 53, 11, 2445-2456, Japanese, 1882-7764, 110009486858, AN00116647 - Game Theory for Computer Scientists : Mechanism Design (Basic)
横尾 真; 岩崎 敦; 櫻井 祐子
日本ソフトウェア科学会 ; 1984-, Nov. 2012, コンピュータソフトウェア, 29, 4, 15-31, Japanese, 0289-6540, 40019482077 - 1-G-8 双対解を用いたコアおよび弱εコア^+の非空判定アルゴリズム(ゲーム理論(1))
上田 俊; 北木 真; 岩崎 敦; 横尾 真
公益社団法人日本オペレーションズ・リサーチ学会, 12 Sep. 2012, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2012, 126-127, Japanese, 110009588842, AN00351192 - オークションメカニズムの多項式表現と限量記号消去法を用いたメカニズム設計の自動化
杉町勇和; 岩崎敦; 横尾真; 穴井宏和
12 Sep. 2012, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2012, 198-199, Japanese, 1883-1893, 201202250150583121 - A Rule Extraction Algorithm for Combinatorial Auctions with Automated Mechanisms Design
毛利 貴之; 杉町 勇和; 東藤 大樹; 岩崎 敦; 横尾 真
一般に組合せオークションのためのメカニズムは割当て規則と支払い規則の2つの関数によって構成される．メカニズムに関する著名な研究成果として，理論的に優れた性質を持つVickrey-Clarke-Groves（VCG）メカニズムが知られている．しかしながら，VCGメカニズムにはいくつかの問題点があると近年指摘されている．これまでに，その問題に対して頑健性が保証されるメカニズムがいくつか提案されている．従来，これらの関数は人手で設計されてきたが，多大な時間と労力がかかる．そこで近年，整数計画法を利用した自動設計の手法（自動メカニズムデザイン）が提案されている．しかしながら，自動メカニズムデザインは小規模な問題にしか対応できず，現実の問題サイズを扱うことができない．そのため従来研究では，小規模な問題を解き，出力された結果の中から特徴的な結果を抽出し，一般に適用可能なルールを求めようとしている．それでも一般的なルールを得るには人手による部分がまだまだ多い．また，得られたルールが必ずしも適切だとは限らず，別途検証する必要がある．本論文では，自動メカニズムデザインの出力結果から一般的なルールを抽出するアルゴリズムを提案する．具体的には商品の割当て方法や支払額を決定する関数は，あるしきい値を超えているかどうかで勝敗が決まるとし，そのしきい値を出力するアルゴリズムである．Automated mechanism design (AMD) provides a novel scheme to design social choice rules (e.g., combinatorial auction mechanisms) by using mathematical programming technique. However, it only returns a discretized set of outcomes, i.e., allocations and the associated payments given possible type profiles. Therefore, for large combinatorial auction problems, there has been no scheme to effectively generalize a social choice rule for a continuous set of outcomes in the literature of mechanism design. In this paper, we formalize the problem as a rule extraction problem. We then propose a new algorithm to automatically extract a payment rule of a combinatorial auction mechanism from the discretized set of outcomes obtained from AMD. Our experiments reveal that the proposed algorithm successfully extracts payment rules of two existing combinatorial auction mechanisms that is either strategy-proof or false-name-proof., 情報処理学会, 15 Aug. 2012, 情報処理学会論文誌, 53, 8, 2006-2017, Japanese, 1882-7764, 110009464344, AN00116647 - Game Theory for Computer Scientists : Noncooperative Games (Advanced)
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
日本ソフトウェア科学会, 25 Jul. 2012, コンピュータソフトウェア, 29, 3, 39-53, Japanese, 0289-6540, 10030497690 - The 2011 IPSJ Best Paper Award：Toward a Foundation of Market Design Theory for the Internet Era
東藤 大樹; 岩崎 敦; 横尾 真
15 Jul. 2012, 情報処理, 53, 8, 857-857, Japanese, 170000071325 - Introduction of Game Theory for Computer Scientists
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
Japan Society for Software Science and Technology, 25 Apr. 2012, Computer Software, 29, 2, 65-68, Japanese, 0289-6540, 10030311272 - Game Theory for Computer Scientists : Noncooperative Games (Basic Theory)
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
Game theory is a mathematical study of interaction among rational players. This tutorial presents an overview of noncooperative game theory, specifically games in normal-form. In noncooperative game theory in normal-form, multiple players independently and simultaneously select their actions so as to maximize their own utilities. The obtained utility of a player is determined by combination of her own action and the actions of other players. In noncooperative games, various equilibrium concepts have been developed to predict the result of a game. First, we introduce basic notations and equilibrium concepts in noncoperative games. If we explicitly represent a normal form game, the size of the representation grows exponentially as the number of players increases. Thus, we explain the algorithms/computational costs to efficiently find Nash equilibria in graphical games and congestion games, which have been proposed as concise representation schema., Japan Society for Software Science and Technology, 25 Apr. 2012, Computer Software, 29, 2, 69-84, Japanese, 0289-6540, 10030311279 - 1-I-6 混合整数計画法による自動メカニズムデザイン : 組合せオークションの設計と高速化(離散最適化(1))
杉町 勇和; 毛利 貴之; 岩崎 敦; 横尾 真
公益社団法人日本オペレーションズ・リサーチ学会, 13 Sep. 2011, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2011, 158-159, Japanese, 110009358866, AN00351192 - 1-I-7 配属人数下限付き研究室配属問題(離散最適化(1))
上田 俊; 岩崎 敦; 横尾 真
公益社団法人日本オペレーションズ・リサーチ学会, 13 Sep. 2011, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2011, 160-161, Japanese, 110009358867, AN00351192 - 1-E-1 無閉路ネットワーク上の架空名義操作不可能な施設配置メカニズムの特徴付け(都市・地域・国土)
東藤 大樹; 岩崎 敦; 横尾 真
公益社団法人日本オペレーションズ・リサーチ学会, 13 Sep. 2011, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2011, 72-73, Japanese, 110009358823 - RA-003 相互処罰による協調 : 私的観測付き無限回繰り返し囚人のジレンマの部分観測マルコフ決定過程による解法(アルゴリズム・コンピュテーション(2),A分野:モデル・アルゴリズム・プログラミング)
ジョ ヨンジュン; 岩崎 敦; 神取 道宏; 小原 一郎; 横尾 真
FIT(電子情報通信学会・情報処理学会)運営委員会, 07 Sep. 2011, 情報科学技術フォーラム講演論文集, 10, 1, 15-22, Japanese, 110009623232, AA1242354X - RF-001 A rule extraction algorithm for combinatorial auctions with automated mechanism design
Mouri Takayuki; Sugimachi Toshikazu; Todo Taiki; Iwasaki Atsushi; Yokoo Makoto
Forum on Information Technology, 07 Sep. 2011, 情報科学技術フォーラム講演論文集, 10, 2, 47-54, Japanese, 110009623059 - Simultaneous Solving of Coalition Structure Generation and Payoff Distribution with Linear Programming
北木 真; 上田 俊; 岩崎 敦
人工知能学会, 2011, 人工知能学会全国大会論文集, 25, 1-4, Japanese, 1347-9881, 40020257357, AA11578981 - RA-007 Characterization of False-name-proof Facility Location Mechanisms
Todo Taiki; Iwasaki Atsushi; Yokoo Makoto
Forum on Information Technology, 20 Aug. 2010, 情報科学技術フォーラム講演論文集, 9, 1, 39-46, Japanese, 110008145519 - RF-002 A False-name-proof Combinatorial Auction Mechanism : A variation of VCG Mechanism
Mouri Takayuki; Todo Taiki; Iwasaki Atsushi; Yokoo Makoto
Forum on Information Technology, 20 Aug. 2010, 情報科学技術フォーラム講演論文集, 9, 2, 51-58, Japanese, 110008145635 - Coalition Structure Generation based on Distributed Constraint Optimization
上田 俊; 岩崎 敦; 横尾 真
人工知能学会, 2010, 人工知能学会全国大会論文集, 24, 1-4, Japanese, 1347-9881, 40020259926, AA11578981 - False-Name-Proofness in Facility Location Problem on the Real Line
Taiki Todo; Atsushi Iwasaki; Makoto Yokoo
Recently, mechanism design without monetary transfers is attracting much attention, since in many application domains on Internet, introducing monetary transfers is impossible or undesirable. Mechanism design studies how to design mechanisms that result in good outcomes even when agents strategically report their preferences. However, in highly anonymous settings such as the Internet, declaring preferences dishonestly is not the only way to manipulate the mechanism. Often, it is possible for an agent to pretend to be multiple agents, and submit multiple reports using different identifiers, e.g., different e-mail addresses. Such false-name manipulations are more likely to occur in a mechanism without monetary transfers, since submitting multiple reports would be less risky in such a mechanism. In this paper, we formalize false-name manipulations in facility location problems on the real line and discuss the effect of such manipulations., SPRINGER-VERLAG BERLIN, 2010, INTERNET AND NETWORK ECONOMICS, 6484, 559-562, English, Peer-reviwed, 0302-9743, conf/wine/TodoIY10, WOS:000290644400050 - New Redistribution Mechanism Based on Take-It-or-Leave-It
SAKURAI Yuko; SAITO Yasumasa; IWASAKI Atsushi; YOKOO Makoto
エージェントやマルチエージェントシステム研究分野において,オークションのメカニズム設計に関する研究が盛んに行われている.近年,一般的なオークションだけでなく,再配分メカニズムと呼ばれるオークションのメカニズム設計が注目されている.入札者らが共同所有する財を対象にオークションを行う場合,落札者が支払った支払額をどうすればよいかが問題となる.支払額が誰の手にも渡らずに残れば,その分の社会的余剰が減少することとなる.そこで,再配分メカニズムでは財の割当を決めるだけでなく,支払額を入札者らで配分する方法も与える.本論文では,戦略的操作不可能性と,すべての支払額を入札者らに再配分可能,すなわち,強予算均衡を満たす,新しい再配分メカニズム(RM-TLA)の提案を行う.RM-TLAは,主催者が各入札者に提示価格を示し,入札者はその価格に対して受諾/拒否を申告するTake-it-or-leave-it方式に基づく.したがって,RM-TLAでは,入札者は入札額を申告する必要がない.入札額は重要な個人情報であり,入札額に関して公開する情報量が少ない方が望ましい.更に,我々は,入札者が得る効用の分散(公平性)について着目し,RM-TLAが既存のメカニズムよりも公平性が高くなることと,得られる社会的余剰を改善できることを計算機実験によって示した., The Institute of Electronics, Information and Communication Engineers, 01 Nov. 2009, The IEICE transactions on information and systems, 92, 11, 1861-1868, Japanese, 1880-4535, 110007467227 - 2-D-1 数理計画法を用いたメカニズムデザインの自動化 : 架空名義入札に頑健な組合せオークションメカニズムの設計(離散・組合せ最適化(5))
岩崎 敦; 大森 由総; 東藤 大樹; 横尾 真
公益社団法人日本オペレーションズ・リサーチ学会, 09 Sep. 2009, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2009, 227-228, Japanese, 110007467831 - 1-D-6 特性関数の簡略記述法を用いた提携構造の形成(離散・組合せ最適化(2))
一村 良; 大田 直樹; コニッツァー ヴィンセント; 佐藤 恭史; 櫻井 祐子; 岩崎 敦; 横尾 真
公益社団法人日本オペレーションズ・リサーチ学会, 09 Sep. 2009, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2009, 82-83, Japanese, 110007467761 - Characterizing False-name-proof Allocation Rules in Combinatorial Auctions
東藤 大樹; 岩崎 敦; 横尾 真
人工知能学会, 2009, 論文集, 23, 1-4, Japanese, 1347-9881, 40020258294, AA11578981 - The effect of false-name bids in first price auctions
桂木 敦史; 櫻井 祐子; 岩崎 敦
人工知能学会, 2009, 論文集, 23, 1-4, Japanese, 1347-9881, 40020259889, AA11578981 - 第一価格入札における架空名義操作の影響の解析
桂木 敦史; 櫻井 祐子; 岩崎 敦; 横尾 真
<p>インターネットのような匿名の環境では一人の参加者が複数の名義を用いる架空名義入札が可能となる．従来研究では，架空名義入札の影響を受けない新しいメカニズムが提案されているが，既存の第一価格入札における架空名義操作の影響は明らかとなっていない．本論文では，第一価格入札でのベイジアンナッシュ均衡を計算機シミュレーションにより求め，架空名義入札により社会的余剰及び主催者の収入が減少することを示す．</p>, 一般社団法人 人工知能学会, 2009, 人工知能学会全国大会論文集, 2009, 0, 1I33-1I33, Japanese, 130007426693 - 架空名義操作不可能な組合せオークションの割当規則の特性
東藤 大樹; 岩崎 敦; 横尾 真; 櫻井 祐子
<p>インターネットは大規模なオークションに適した環境を提供する．しかし，その匿名性により，架空名義操作と呼ばれる新たな不正が可能となる．本論文では，架空名義操作不可能な組合せオークションメカニズムが満たすべき性質を提案する．また，提案した性質を用いて既存のメカニズムの架空名義操作不可能性を検証し，架空名義操作不可能であると信じられてきた２つのメカニズムが，実際には架空名義操作可能であることを示す．</p>, 一般社団法人 人工知能学会, 2009, 人工知能学会全国大会論文集, 2009, 0, 1I32-1I32, Japanese, 130007425741 - 制約充足／最適化テクニックを用いた会議プログラム自動作成ツール
西村 直史; 大田 直樹; 櫻井 祐子; 岩崎 敦; 横尾 真
<p>ある程度規模の大きい学会では，様々な制約条件や価値基準を満足する会議プログラムを手作業で作成することは困難であり，大きな労力が伴う．そのため著者らは，制約充足／最適化のテクニックを用いた会議プログラムの自動生成ツールを開発した．本論文では，開発したツールを用いて実際の2008年度人工知能学会全国大会のプログラムを作成した結果と，大会終了後に行なったツールの改良について報告する．</p>, 一般社団法人 人工知能学会, 2009, 人工知能学会全国大会論文集, 2009, 0, 2H31-2H31, Japanese, 130007424034 - 架空名義入札に頑健な再配分メカニズムの提案
櫻井 祐子; Conitzer Vincent; 斎藤 恭昌; 岩崎 敦; 横尾 真
<p>グループで共同所有している車の使用権をオークションで決定する場合，集めた支払額をどうするかが問題となる．再配分メカニズムは，財の割当てだけでなく，入札者らに支払額を配分する方法を与える．架空名義入札は，一人のエージェントが複数の名義で入札することを意味し，インターネットオークションにおいて深刻な問題の1つであることが指摘されている．本論文では，架空名義入札に頑健な再配分メカニズムの提案を行う．</p>, 一般社団法人 人工知能学会, 2009, 人工知能学会全国大会論文集, 2009, 0, 1I31-1I31, Japanese, 130007423035 - Automated Mechanism Design for False-name-proof Combinatorial Auctions
OMORI Yoshifusa; SAITO Yasumasa; IWASAKI Atsushi; SAKURAI Yuko; YOKOO Makoto
本論文では，自動メカニズムデザインを用いて架空名義入札に頑健なオークションメカニズムを構築する新しい手法を提案する．インターネットオークションのような匿名性の高い環境では，架空名義入札と呼ばれる新しい不正行為の危険性が指摘されており，架空名義入札の影響を受けないオークションメカニズムがいくつか提案されているが，まだ決定版といわれるメカニズムは提案されていない．本論文では，最適化手法を用いて社会的に望ましい性質を満たすようメカニズムを自動設計する手法である自動メカニズムデザインを用いることで，新しい架空名義入札に頑健なオークションメカニズムを構築する．また，提案手法が構築したメカニズムと既存のオークションメカニズムを比較する．This paper proposes automated mechanism design, as a mechanism design technique, for false-name-proof combinatorial auctions. Mechanisms have traditionally been designed manually for classes of problems. Sandholm (2003) introduced automated mechanism design, where a mechanism is automatically designed using constrained optimization technique. This paper presents the first attempt for automatically generating a false-name-proof combinatorial auction mechanism. False-name-proofness means that a mechanism is not influenced by false-name manipulations that submitted by a single buyer who uses multiple fictitious names such as multiple e-mail addresses. Then, we show that our technique yields an auction mechanism which has better outcomes than some existing combinatorial auction mechanisms., Information Processing Society of Japan (IPSJ), 23 Oct. 2008, IPSJ SIG Notes. ICS, 2008, 104, 49-56, Japanese, 0919-6072, 110007081208 - Secure Keyword Auction Protocol
SAKURAI Yuko; SUZUKI Koutarou; YOKOO Makoto; IWASAKI Atsushi
キーワード広告オークションは，検索エンジンが検索結果に関連する広告の掲載順位を決定するために行われている．広告主は入札額を主催者 （検索エンジン） に表明するが，主催者が入札額を知ることで，オークション結果を不正に操作する可能性が考えられる．従って，入札額を秘匿したまま，オークション結果を決定できることが望ましい．しかしながら，我々は，既存のキーワード広告オークションプロトコルの場合，入札額を秘匿したとしても，主催者は，支払額から入札額を求めることができることを示した．そこで，支払額から入札額が漏洩しにくいオークションプロトコル，及びそれを実現する暗号プロトコルを提案する．In a keyword auction, each advertiser submits her bid to each keyword and her advertisement is displayed according the result of the auction when users search the keyword on internet search engines. In existing keyword auctions called the GSP, the auctioneer can increase his revenue by knowing all bidding prices. We show, in the GSP, even if bidders submit encrypted bids, the auctioneer can calculate each winner's bidding price by knowing winners' payments. Thus, we develop a new privacy preserving keyword auction protocol by improving the payment rule and utilizing cryptographic technologies., Information Processing Society of Japan (IPSJ), 23 Oct. 2008, IPSJ SIG Notes. ICS, 2008, 104, 41-48, Japanese, 0919-6072, 110007081210 - New Redistribution Mechanism based on Take-It-or-Leave-It
SAITO Yasumasa; SAKURAI Yuko; IWASAKI Atsushi; YOKOO Makoto
再配分オークションでは，一般的なオークションとは異なり，販売する財の所有者が存在しない状況を対象とし，支払額を入札者に再配分する．このとき，再配分オークションメカニズムは，社会的に望まれる性質に加え，出来る限り支払額の全額を再配分するといった性質も満たす必要がある．そこで，本論文では，戦略的操作不可能性を満足しつつ，全ての支払額を再配分することが可能な逐次区分メカニズムという新しいクラスを提案する．逐次区分メカニズムでは，全ての財の割当てを同時に行うのではなく，入札者と財を複数の区分に分割し，区分ごとに財の割当てを行う．各区分に適用するオークションは，戦略的操作不可能性を満足するメカニズムであれば，区分ごとに異なるメカニズムを適用することが可能である．さらに，逐次区分メカニズムのインスタンスの一つであり，各区分に Take-It-or-Leave-It メカニズムを適用した再配分オークションメカニズム (RM-TLA) を提案する． RM-TLA は，入札のルールが非常に単純であることに加え，入札者が公開する情報が少なくてすむという性質を持つ．This paper develops a new redistribution mechanism where the items do not have an owner and the agents are merely interested in allocating the items efficiently among themselves. Therefore, to circumvent any surplus payment, (strong) budget-balance is one of the most desirable property for redistribution mechanisms. That is to say, the sum of the agents' payments is exactly zero. Though a series of redistribution mechanisms has been proposed, we propose a sequential partition mechanism as a new class of budget-balanced redistribution mechanisms. As one instance of the class, we develop a new redistribution mechanism based on Take-It-or-Leave-It auction (RM-TLA). The RM-TLA has very simple allocation and payment rule and it preserves agents' private information than existing redistribution mechanisms., Information Processing Society of Japan (IPSJ), 23 Oct. 2008, IPSJ SIG Notes. ICS, 2008, 104, 17-24, Japanese, 0919-6072, 110007081216 - Strategy-proof Cost Sharing Mechanism based on Clarke Tax
SATOH Yasufumi; OHTA Naoki; SAKURAI Yuko; IWASAKI Atsushi; YOKOO Makoto
費用分担問題とは，複数のエージェントが提携を組み，目的の達成に必要な費用の分担方法 （メカニズム） に関する問題である．しかし従来メカニズムは，戦略的操作不可能性を満たすために，適用領域を限定したり，費用が不足するといった問題があった．そこで，本論文では，費用の均等分担にクラーク税を加えることで，戦略的操作不可能性を満たしつつ，より適応領域が広く，費用が不足することのないメカニズムを提案する．Cost sharing problem is how the cost is to be shared in order to make a stable coalition to achieve an objective. There has been a lot of cost sharing mechanism in the literature of economics and computer science. For some specific cost functions, there are several traditional mechanism satisfying strategy-proofness and budget-balanced at the same time. However, for any arbitrary cost function, there does not exist a representative mechanism yet. In this paper, we develop a new cost sharing mechanism satisfying strategy-proofness and budget-positive at the same time for any arbitrary cost function., Information Processing Society of Japan (IPSJ), 23 Oct. 2008, IPSJ SIG Notes. ICS, 2008, 104, 9-16, Japanese, 0919-6072, 110007081218 - Characterizing False-name-proof Allocation Rules in Combinatorial Auctions
TODO Taiki; IWASAKI Atsushi; YOKOO Makoto; SAKURAI Yuko
メカニズムデザインとは，複数の人間 （エージェント） が何らかの社会的決定をする場合に，社会的に望ましい結果をもたらすような相互作用のルール （割当規則と支払規則） を設計することである．この分野は電子商取引の拡大にともない，経済学だけでなく，人工知能／エージェント分野でも活発に研究が行われている．その中にメカニズムの単調性に関する研究がある．この研究によって，単調性を満たす割当規則さえ見つかれば，メカニズムが戦略的操作不可能となるような支払規則が存在することが示されている （実装可能性） ．しかし，複数のメールアドレスを用いて不正に利益を増加させるといった架空名義操作に関する性質はほとんど検討されていない．そこで本論文では，架空名義操作に対して，割当規則が満たすべき条件を吟味する．その結果，組合せオークションメカニズムが架空名義操作不可能となる支払規則が存在するために割当規則が満たすべき条件を示した．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., Information Processing Society of Japan (IPSJ), 23 Oct. 2008, IPSJ SIG Notes. ICS, 2008, 104, 1-8, Japanese, 0919-6072, 110007081220 - 特集「エージェント」の編集にあたって
栗原聡; 秋山英三; 伊藤孝行; 今井倫太; 岩崎敦; 大須賀昭彦; 小野哲雄; 北村泰彦; 松原繁夫; 峯恒憲; 森山甲一
Oct. 2008, 日本ソフトウェア科学会コンピュータソフトウェア, 25, 4, 1-2, Japanese, Introduction other - Anonymity-proof Shapley Value : Extending Shapley Value for Coalitional Games in Open Environments
大田 直樹; 佐藤 恭史; 岩崎 敦
人工知能学会, 2008, 人工知能学会全国大会論文集, 22, 1-4, Japanese, 1347-9881, 40020235727, AA11578981 - False-name-proof auction protocols for budget-constrained bidders
櫻井 祐子; 斎藤 恭昌; 岩崎 敦
人工知能学会, 2008, 人工知能学会全国大会論文集, 22, 1-4, Japanese, 1347-9881, 40020235752 - 予算制約を考慮した架空名義入札に頑健なオークションプロトコルの提案
櫻井 祐子; 斎藤 恭昌; 岩崎 敦; 横尾 真
従来，オークション理論では，入札者の効用は評価値と支払額の差である準線形効用を仮定している．しかしながら，現実社会では入札者が評価値より低い予算を持つ場合がある．そこで，予算制約を考慮した架空名義入札に頑健なオークションプロトコルの提案を行う．, 一般社団法人 人工知能学会, 2008, 人工知能学会全国大会論文集, 8, 0, 171-171, Japanese, 130004654026 - 人工知能学会全国大会プログラム自動作成ツールの開発
西村 直史; 徳永 亮; 櫻井 祐子; 大田 直樹; 岩崎 敦; 横尾 真
本論文では，制約最適化のテクニックを用い，著者間距離等のデータを活用する会議プログラム自動生成ツールの提案を行う．また，提案ツールを用いて，本大会のプログラムの作成を行った結果に関して報告する．, 一般社団法人 人工知能学会, 2008, 人工知能学会全国大会論文集, 8, 0, 289-289, Japanese, 130004654151 - False-name-proof multi-unit auction protocols for non-quasi-linear utility
SAKURAI Yuko; SAITO Yasumasa; IWASAKI Atsushi; YOKOO Makoto
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., The Institute of Electronics, Information and Communication Engineers, 06 Dec. 2007, IEICE technical report, 107, 383, 17-22, Japanese, 0913-5685, 110006549167 - False-Name-Proof Mechanisms for Hiring a Team
SAITO YASUMASA; IWASAKI ATSUSHI; YOKOO MAKOTO; KEMPE DAVID; SALEK MAHYAR
This paper develops two new false-name proof auction mechanisms for hiring a team. In the problem of hiring a team, each agent is assumed to own one or more edges of a set system, and the auctioneer is trying to purchase a feasible solution to perform a task by conducting an auction. We introduce two models of false-name manipulations in hiring a team auctions and propose the MP and AP mechanisms, which are robust against false-name manipulations. Furthermore, we show the frugality ratio of MP is bounded by n2^n , and that of AP is bounded by reserve cost, which is choosen a priori by the auctioneer., Information Processing Society of Japan (IPSJ), 30 Oct. 2007, IPSJ SIG Notes. ICS, 2007, 106, 17-24, Japanese, 0919-6072, 110006452382, AA11135936 - A Fair Solution Concept for Coalitional Games in Open Anonymous Environments
OHTA Naoki; SATO Yasufumi; IWASAKI Atsushi; YOKOO Makoto; CONITZER Vincent
Coalition formation is an important capability of automated negotiation among self-interested agents. In order for coalitions to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Recent research has revealed that traditional solution concepts are vulnerable to various manipulations in open anonymous environments such as the Internet. To address the manipulations, a solution concept called the anonymity-proof core, which is robust against such manipulations, was developed. However, this solution concept is difficult to represent and calculate outcome functions in terms of computational complexity. To address these problems, we develop a new solution concept called the anonymity-proof shapley value. This solution concept is easy to represent/calculate the anonymity-proof shapley value., Information Processing Society of Japan (IPSJ), 30 Oct. 2007, IPSJ SIG Notes. ICS, 2007, 106, 49-56, Japanese, 0919-6072, 110006452386, AA11135936 - A new keyword auction protocol for determining the appropriate number of slots
SAKURAI Yuko; IWASAKI Atushi; YOKOO Makoto
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!, Information Processing Society of Japan (IPSJ), 30 Oct. 2007, IPSJ SIG Notes. ICS, 2007, 106, 1-8, Japanese, 0919-6072, 110006452380 - Agent Systems Meet Human Society : Internet Auction and Mechanism Design
YOKOO Makoto; IWASAKI Atsushi
インターネットオークションは急成長している電子商取引の重要な一分野であり，エージェント技術の有望な適用領域であると考えられる．インターネットの利用により低コストで大規模なオークションが実行可能となった反面 不特定多数の人々が参加可能であることから オークション方式(プロトコル) の設計にあたっては様々な不正行為に対する頑健性 オークションの結果に関するなんらかの理論的な裏付け等が重要となるものと考えられる. 様々なオークションのプロトコルに関して これらの性質を解明しようとする研究は経済学の一分野，特にメカニズムデザイン／制度設計と呼ばれる分野で活発な研究が行われてきている．本稿では これらのインターネットオークションとメカニズムデザインに関する事例と研究について概説する, Information Processing Society of Japan (IPSJ), 15 Mar. 2007, IPSJ Magazine, 48, 3, 236-242, Japanese, 0447-8053, 110006224549, AN00116625 - Development of stock exchange simulator and automated trading strategy
黒田 直樹; 横尾 真; 岩崎 敦
人工知能学会, 2007, 人工知能学会全国大会論文集, 21, 1-4, Japanese, 1347-9881, 40020251969, AA11578981 - False-Name-Proof mechanisms for Path Auction
斎藤 恭昌; 岩崎 敦; 横尾 真
人工知能学会, 2007, 人工知能学会全国大会論文集, 21, 1-4, Japanese, 1347-9881, 40020253414, AA11578981 - A New Keyword Auction Protocol for Optimizing the Number of Advertisement Slots
櫻井 祐子; 井上 博文; 岩崎 敦
人工知能学会, 2007, 人工知能学会全国大会論文集, 21, 1-4, Japanese, 1347-9881, 40020252992 - Multiagent Planning with Trembling-hand Perfect Equilibrium in Multiagent POMDP
籔 悠一; 横尾 真; 岩崎 敦
人工知能学会, 2006, 人工知能学会全国大会論文集, 20, 1-4, Japanese, 1347-9881, 40020228537, AA11578981 - Implementation and evaluation of Secure DisCSP algorithm using ElGamal Encryption
黒田 直樹; 横尾 真; 岩崎 敦
人工知能学会, 2006, 人工知能学会全国大会論文集, 20, 1-4, Japanese, 1347-9881, 40020228508, AA11578981 - A Cycle-Cutset-based Algorithm for Solving Distributed CSP
松下 俊伸; 横尾 真; 岩崎 敦
人工知能学会, 2005, 人工知能学会全国大会論文集, 19, 1-3, Japanese, 1347-9881, 40020228922, AA11578981 - Estimating Demand Functions using Bidding Data on the Internet Auctions
田中 保行; 岩崎 敦; 横尾 真
人工知能学会, 2005, 人工知能学会全国大会論文集, 19, 1-4, Japanese, 1347-9881, 40020228907, AA11578981 - Performance evaluation of false-name proof protocol in combinatorial auction
松谷 俊宏; 横尾 真; 岩崎 敦
人工知能学会, 2005, 人工知能学会全国大会論文集, 19, 1-4, Japanese, 1347-9881, 40020228899, AA11578981
Lectures, oral presentations, etc.
- 中古自動車の査定価格決定支援システムにおける区間推定モデルの評価
林 雄太郎; 松下 旦; 岩崎 敦
Oral presentation, Japanese, 第23回情報科学技術フォーラム
04 Sep. 2024
04 Sep. 2024- 06 Sep. 2024 - 二人零和マルコフゲームにおける状態抽象化に関する研究
石橋 宙希; 阿部 拳之; 岩崎 敦
Oral presentation, Japanese, 第23回情報科学技術フォーラム
04 Sep. 2024
04 Sep. 2024- 06 Sep. 2024 - 花き市場における需要の可視化と推定に関する研究
酒井 洸星; 岩崎 敦; 松下 旦; 段 裕之; 齋藤 麗
Oral presentation, Japanese, 第23回情報科学技術フォーラム
04 Sep. 2024
04 Sep. 2024- 06 Sep. 2024 - 不正確な特定化を含む恒常所得モデルに関する研究
足立 幸大; 池上 慧; 岩崎 敦
Oral presentation, Japanese, 第38回人工知能学会全国大会
31 May 2024
28 May 2024- 31 May 2024 - 機械学習が紡ぐゲーム理論のフロンティア
阿部 拳之; 岩崎 敦
Public discourse, Japanese, 第38回人工知能学会全国大会
29 May 2024
28 May 2024- 31 May 2024 - 車種グループ別モデル構築による中古自動車価格予測精度の改善
西山 佑典; Le Binh Thanh; 段 裕之; 林 雄太郎; 松下 旦; 岩崎 敦
Oral presentation, Japanese, 第38回人工知能学会全国高い
29 May 2024
28 May 2024- 31 May 2024 - 花卉市場における需要の可視化と推定に関する研究
酒井 洸星; 段 裕之; 松下 旦; 岩崎 敦; 斎藤 麗
Oral presentation, Japanese, 第38回人工知能学会全国大会
28 May 2024
28 May 2024- 31 May 2024 - 不正確な特定化を含む恒常所得モデルに関する研究
足立幸大; 岩﨑 敦; 池上 慧
Oral presentation, Japanese, 情報処理学会第86回全国大会, with international co-author(s)
Mar. 2024
15 Mar. 2024- 17 Mar. 2024 - 見間違えのある繰り返し囚人のジレンマの確率動学による分析
谷川颯希; 村井伸一郎; 岩﨑 敦
Oral presentation, Japanese, 情報処理学会第86回全国大会
Mar. 2024
15 Mar. 2024- 17 Mar. 2024 - 二人零和マルコフゲームにおける状態抽象化法に関する研究
石橋宙希; 島野雄貴; 阿部拳之; 岩﨑 敦
Oral presentation, Japanese, 情報処理学会第86回全国大会
Mar. 2024
15 Mar. 2024- 17 Mar. 2024 - 研修医配属における地域間格差を調整する制約のモンテカルロ木探索
板垣圭知; 小宮山純平; 阿部拳之; 岩崎 敦
Oral presentation, Japanese, 情報処理学会第86回全国大会, with international co-author(s)
Mar. 2024
15 Mar. 2024- 17 Mar. 2024 - Slingshot Perturbation to Learning in Monotone Games
Atsushi Iwasaki
Nominated symposium, Japanese, International Workshop on Learning in Misspecified Models and Beyond, Invited
15 Mar. 2024
15 Mar. 2024- 16 Mar. 2024 - 研修医配属における地域間格差を調整する制約のモンテカルロ木探索
板垣 圭知; 小宮山 純平; 阿部 拳之; 岩﨑 敦
Oral presentation, 第２２回情報科学技術フォーラム（選奨論文）
06 Sep. 2023
06 Sep. 2023- 08 Sep. 2023 - 中古車査定価格支援システムにおける機械学習モデル改善の取り組み
段 裕之; 林 雄太郎; Le Binh Thanh; 西山 佑典; 松下 旦; 岩崎 敦
Oral presentation, 第２２回情報科学技術フォーラム（選奨論文）
06 Sep. 2023
06 Sep. 2023- 08 Sep. 2023 - オンライン環境において公平な資源配分を実現するアルゴリズムに関する研究
山田 博瑛; 小宮山純平; 阿部 拳之; 岩﨑 敦
第２２回情報科学技術フォーラム（選奨論文）
06 Sep. 2023
06 Sep. 2023- 08 Sep. 2023 - 取り違えのある繰り返し囚人のジレンマにおける単独裏切-相互処罰戦略
村井 伸一郎; 岩崎 敦
Oral presentation, 第２２回情報科学技術フォーラム（選奨論文）
06 Sep. 2023
06 Sep. 2023- 08 Sep. 2023 - オンライン環境において公平な資源配分を実現するアルゴリズムに関する研究
山田 博瑛; 小宮山 純平; 阿部 拳之; 岩﨑 敦
Oral presentation, 人工知能学会全国大会
07 Jun. 2023
06 Jun. 2023- 09 Jun. 2023 - 中古自動車の査定価格決定支援システムの実装
段 裕之; 林 雄太郎; 松下 旦; 岩崎 敦
Oral presentation, 人工知能学会全国大会
07 Jun. 2023
06 Jun. 2023- 09 Jun. 2023 - 二人零和展開型ゲームにおける突然変異付き乗算型重み更新に関する研究
坂本 充生; 阿部 拳之; 蟻生 開人; 岩崎 敦
Oral presentation, 人工知能学会全国大会
07 Jun. 2023
06 Jun. 2023- 09 Jun. 2023 - 取り違えのある繰り返し囚人のジレンマにおける単独裏切-相互同期戦略
村井 伸一郎; 岩崎 敦
Oral presentation, 人工知能学会全国大会
07 Jun. 2023
06 Jun. 2023- 09 Jun. 2023 - Regulating Matching Markets with Constraints: Data-driven Taxation
Akira Matsushita; Kei Ikegami; Kyohei Okumura; Yoji Tomita; Atsushi Iwasaki
Oral presentation, Japanese, ゲーム理論ワークショップ2023
06 Mar. 2023 - 取り違えのある繰り返し囚人のジレンマにおける単独裏切-相互同期戦略
村井伸一郎; 岩崎 敦
Japanese, 情報処理学会第85回全国大会
Mar. 2023
Mar. 2023 Mar. 2023 - 公平なインターバルスケジューリング問題に関する研究
酒井洸星; 岩崎 敦
Japanese, 情報処理学会第85回全国大会
Mar. 2023
Mar. 2023 Mar. 2023 - 研修医配属における地域間格差を調整するための制約のモンテカルロ木探索
板垣圭知; 小宮山純平; 阿部拳之; 岩崎 敦
Japanese, 情報処理学会第85回全国大会
Mar. 2023
Mar. 2023 Mar. 2023 - オンライン環境において公平な資源配分を実現するアルゴリズムに関する研究
山田博瑛; 小宮山純平; 阿部拳之; 岩﨑 敦
Japanese, 情報処理学会第85回全国大会
Mar. 2023
Mar. 2023 Mar. 2023 - Regulating Matching Markets with Constraints: Data-driven Taxation
Akira Matsushita; Kei Ikegami; Kyohei Okumura; Yoji Tomita; Atsushi Iwasaki
Oral presentation, Japanese, 第28回DCコンファレンス
14 Oct. 2022 - 取り違えのある繰り返し囚人のジレンマにおける協力のダイナミクス
村井 伸一郎
Oral presentation, Japanese, 第２１回情報科学技術フォーラム（選奨論文）, 情報処理学会, オンライン, Domestic conference
13 Sep. 2022 - 二人零和ゲームにおける突然変異駆動型Follow-The-Regularized-Leaderの終極反復収束
豊島 健太郎
Oral presentation, Japanese, 第２１回情報科学技術フォーラム（選奨論文）, 情報処理学会, オンライン, Domestic conference
13 Sep. 2022 - 制約付きマッチングのためのデータ駆動型課税規則に関する研究
岩崎 敦
Oral presentation, Japanese, 第２１回情報科学技術フォーラム（選奨論文）, 情報処理学会, オンライン, Domestic conference
13 Sep. 2022 - 制約付きマッチングのためのデータ駆動型課税規則に関する研究
岩崎 敦
Oral presentation, Japanese, 人工知能学会全国大会, Domestic conference
16 Jun. 2022 - 取り違えのある繰り返し囚人のジレンマにおける協力のダイナミクス
村井 伸一郎
Oral presentation, Japanese, 人工知能学会全国大会, Domestic conference
15 Jun. 2022 - 二人零和ゲームにおける突然変異付きレプリケータダイナミクスを用いた学習アルゴリズムに関する研究
豊島 健太郎
Oral presentation, Japanese, 人工知能学会全国大会, Domestic conference
15 Jun. 2022 - ほぼ公的観測下の繰り返しプロジェクトゲームにおける協力のダイナミクス
五十嵐瞭平
Oral presentation, Japanese, 情報処理学会第84回全国大会, Domestic conference
04 Mar. 2022 - 二人零和ゲームにおける突然変異付きレプリケータダイナミクスを用いた学習アルゴリズムに関する研究
坂本充生
Oral presentation, Japanese, 情報処理学会第84回全国大会, Domestic conference
04 Mar. 2022 - 取り違えのある繰り返し囚人のジレンマにおける協力のダイナミクス
村井伸一郎
Oral presentation, Japanese, 情報処理学会第84回全国大会, Domestic conference
03 Mar. 2022 - クールノー競争におけるマルチエージェント強化学習に関する研究
豊島健太郎
Oral presentation, Japanese, 情報処理学会第84回全国大会, Domestic conference
03 Mar. 2022 - 見間違えのある繰り返しゲームのためのActor-Critic型強化学習
坂本充生
Oral presentation, Japanese, 第24回情報論的学習理論ワークショップ (IBIS2021), 電子情報通信学会 情報論的学習理論と機械学習研究会, オンライン, Domestic conference
11 Nov. 2021 - ほぼ公的観測下の囚人のジレンマにおける協力のダイナミクス
五十嵐瞭平
Oral presentation, Japanese, 日本OR学会秋季研究発表会, 日本OR学会, 九州大学（オンライン）, Domestic conference
17 Sep. 2021 - 見間違えのある繰り返しゲームのためのActor-Critic型強化学習
坂本充生
Oral presentation, Japanese, 日本OR学会秋季研究発表会, 日本OR学会, 九州大学（オンライン）, Domestic conference
17 Sep. 2021 - ほぼ公的観測下の繰り返し囚人のジレンマにおける協力のダイナミクス
五十嵐瞭平
Oral presentation, Japanese, 第２０回情報科学技術フォーラム（選奨論文）, 情報処理学会, オンライン, Domestic conference
25 Aug. 2021 - 見間違えのある繰り返し囚人のジレンマにおける方策勾配法に関する研究
坂本充生
Oral presentation, Japanese, 第２０回情報科学技術フォーラム（選奨論文）, 情報処理学会, オンライン, Domestic conference
25 Aug. 2021 - 反実仮想後悔最小化によるアメリカンフットボールにおけるオフェンス戦略の均衡推定
島野 雄貴
Oral presentation, Japanese, 人工知能学会全国大会, Domestic conference
09 Jun. 2021 - 見間違えのある繰り返し囚人のジレンマにおけるQ学習に関する研究
坂本充生
Oral presentation, Japanese, 人工知能学会全国大会, Domestic conference
09 Jun. 2021 - ほぼ公的観測下の繰り返し囚人のジレンマにおける協力のダイナミクス
五十嵐瞭平
Oral presentation, Japanese, 人工知能学会全国大会, Domestic conference
09 Jun. 2021 - 見間違えのある繰り返し囚人のジレンマにおける協力の発生と振動
岩崎敦
Invited oral presentation, Japanese, 日本オペレーションズ・リサーチ学会2021年春季シンポジウム, Invited, Domestic conference
01 Mar. 2021 - 私的観測下の繰り返し囚人のジレンマにおける協力のダイナミクス
西野上和真
Oral presentation, Japanese, 第１９回情報科学技術フォーラム（選奨論文）, 情報処理学会, オンライン, Domestic conference
01 Sep. 2020 - 見間違え付き繰り返しゲームにおける協力的均衡とダイナミクス
西野上 和真; 岩崎 敦
Oral presentation, Japanese, 日本OR学会秋季研究発表会, 日本OR学会, 東広島芸術文化ホール（広島県東広島市）, Domestic conference
12 Sep. 2019 - 地域上限制約付きマッチングの効率性改善に関する研究
前島 萌; 岩崎 敦
Oral presentation, Japanese, 日本OR学会秋季研究発表会, 日本OR学会, 名古屋市立大学（愛知県名古屋市）, Domestic conference
07 Sep. 2018 - 見間違えのある繰り返しゲームにおける戦略のダイナミクス
浅野 真宏; 岩崎 敦
Oral presentation, Japanese, 日本OR学会秋季研究発表会, 日本OR学会, 名古屋市立大学（愛知県名古屋市）, Domestic conference
07 Sep. 2018 - 見間違えのある繰り返しゲームにおける戦略のダイナミクス
森吉 竜太郎
Oral presentation, Japanese, 日本OR学会春季研究発表会, 日本OR学会, 関西大学吹田キャンパス（大阪府吹田市）, Domestic conference
14 Sep. 2017 - グラフ縮約を用いたテロ組織監視計画の計算に関する研究
名波 伸将
Oral presentation, Japanese, 日本OR学会春季研究発表会, 日本OR学会, 関西大学吹田キャンパス（大阪府吹田市）, Domestic conference
14 Sep. 2017 - ゲーム理論を用いた警備計画における最適な乱択化に関する研究
島野雄貴
Oral presentation, Japanese, 日本OR学会春季研究発表会, 日本OR学会, 慶應義塾大学矢上キャンパス（神奈川県横浜市港北区日吉）, Domestic conference
17 Mar. 2016 - マッチングメカニズムの戦略的側面とその展開
岩崎敦
Oral presentation, Japanese, 経営情報学会2015年秋季全国研究発表会, Invited, 経営情報学会, 沖縄コンベンションセンター（沖縄県宜野湾市真志喜）, Domestic conference
29 Nov. 2015 - 最適化と繰り返しゲーム：動的環境における意思決定
岩崎敦
Invited oral presentation, Japanese, 第27回RAMPシンポジウム, Invited, 国立大学法人 静岡大学, Domestic conference
16 Oct. 2015 - モンテカルロシミュレーションを用いたレッドゾーン内における最適な戦略推定
島野雄貴; 岩崎敦
Oral presentation, Japanese, 第34回ゲーム情報学研究会, Domestic conference
04 Jul. 2015 - ゲーム理論的マッチングメカニズムとその応用
岩崎敦
Public discourse, Japanese, 第152回アルゴリズム研究会, Invited, Domestic conference
03 Mar. 2015 - Can local caution restore global tacit collusion?: Repeatedmultimarket contact with observation errors
Atsushi Iwasaki; Tadashi Sekiguchi; Shun Yamamoto; Makoto Yokoo
Oral presentation, English, Proceedings of the AAAI 2015 SPRING SYMPOSIA, International conference
2015 - マッチングとその応用
岩崎敦
Public discourse, Japanese, 第2回 ORセミナー 『技術者のためのゲーム理論の基礎』, Invited, Domestic conference
06 Dec. 2014 - Interactive Algorithm for Multi-objective Constraint Optimization.
Tenda Okimoto; Yongjoon Joe; Atsushi Iwasaki; Toshihiro Matsui; Katsutoshi Hirayama; Makoto Yokoo
Oral presentation, English, Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP 2012)
2012 - Automated Equilibrium Analysis of Repeated Games with Private Monitoring: A POMDP Approach
Yongjoon Joe; Atsushi Iwasaki; Michihiro Kandori; Ichiro Obara; Makoto Yokoo
Oral presentation, English, the proceedings of the 11th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2012)
2012 - False-name-proofness in online mechanisms
Taiki Todo; Takayuki Mouri; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems(AAMAS '12)
2012 - Handling Negative Value Rules in MC-net-based Coalition Structure Generation
Suguru Ueda; Takato Hasegawa; Naoyuki Hashimoto; Naoki Ohta; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, proceedings of the 11th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2012)
2012 - Strategy-proof mechanisms for two-sided matching with minimum and maximum quotas
Suguru Ueda; Daniel Fragiadakis; Atsushi Iwasaki; Peter Troyan; Makoto Yokoo
Oral presentation, English, proceedings of the 11th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2012)
2012 - Finding Core Utilizing Dual Solution in Synergy Coalition Group Representation
Suguru Ueda; Makoto Kitaki; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 3rd Workshop on Cooperatiove Games in Multiagent System(CoopMAS-2012)
2012 - A Compact Representation Scheme of Coalitional Games Based on Multi-Terminal Zero-Suppressed Binary Decision Diagrams
Yuko Sakurai; Suguru Ueda; Atsushi Iwasaki; Shin-Ichi Minato; Makoto Yokoo
Oral presentation, English, the proceedings of the 14th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2011),
2011 - Pseudo-tree-based Incomplete Algorithm for Distributed Constraint Optimization with Quality Bounds
Tenda Okimoto; Yongjoon Joe; Atsushi Iwasaki; Makoto Yokoo; Boi Faltings
Oral presentation, English, the proceedings of the 17th International Conference on Principles and Practice of Constraint Programming(CP-2011)
2011 - Generalizing Envy-Freeness toward Group of Agents
Taiki Todo; Runcong Li; Xuemei Hu; Takayuki Mouri; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI-2011)
2011 - Concise Characteristic Function Representations in Coalitional Games Based on Agent Types
Suguru Ueda; Makoto Kitaki; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI-2011)
2011 - Real-time solving of quantified CSPs based on Monte-Carlo game tree search
Satomi Baba; Yongjoon Joe; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11)
2011 - False-name bidding in first-price combinatorial auctions with incomplete information
Atsushi Iwasaki; Makoto Yokoo; Atsushi Katsuragi
Oral presentation, English, the proceedings of the 10th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2011)
2011 - False-name-proof mechanism design without money
Taiki Todo; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 10th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2011)
2011 - Pseudo-Tree-Based Algorithm for Approximate Distributed Constraint Optimization with Quality Bounds
Tenda Okimoto; Yongjoon Joe; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the tenth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2011)
2011 - Concise Characteristic Function Representations in Coalitional Games Based on Agent Types
Suguru Ueda; Makoto Kitaki; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 10th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2011)
2011 - Extension of MC-net-based Coalition Structure Generation: Handling Negative Rules and Externalities
Ryo Ichimura; Takato Hasegawa; Suguru Ueda; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the Proceedings of the Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011)
2011 - False-name-proofness in Facility Location Problem on the Real Line
Taiki Todo; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 6th International Workshop On Internet And Network Economics (WINE-2010)
2010 - the proceedings of the 6th International Workshop On Internet And Network Economics (WINE-2010)
Taiki Todo; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 2010 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT-2010)
2010 - Coalition Structure Generation Based on Distributed Constraint Optimization
Suguru Ueda; Atsushi Iwasaki; Makoto Yokoo; Marius Calin Silaghi; Katsutoshi Hirayama; Toshihiro Matsui
Oral presentation, English, the proceedings of the 24th National Conference on Artificial Intelligence (AAAI-2010)
2010 - Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms
Atsushi Iwasaki; Vincent Conitzer; Yoshifusa Omori; Yuko Sakurai; Taiki Todo; Mingyu Guo; Makoto Yokoo
Oral presentation, English, the proceedings of the 9th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2010),
2010 - Cooperative Problem Solving against Adversary: Quantified Distributed Constraint Satisfaction Problem
Satomi Baba; Atsushi Iwasaki; Makoto Yokoo; Marius Silaghi; Katsutoshi Hirayama; Toshihiro Matsui
Oral presentation, English, the proceedings of the 9h International Joint Conference on Autonomous Agents and Multi-Agent System (AAMAS-2010)
2010 - Effect of DisCSP Variable-Ordering Heuristics in Scale-free Networks
Tenda Okimoto; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 13th International Conference on Pronciples and Practice of Multi-agent Systems(PRIMA-2010)
2010 - Characterization of Strategy-proof, Revenue Monotone Combinatorial Auction Mechanisms and Connection with False-name-proofness
Taiki Todo; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 5th International Workshop On Internet And Network Economics (WINE-2009)
2009 - Coalition Structure Generation Utilizing Compact Characteristic Function Representations
Naoki Ohta; Vincent Conitzer; Ryo Ichimura; Yuko Sakurai; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP-2009)
2009 - Characterizing False-name-proof Allocation Rules in Combinatorial Auctions
Taiki Todo; Atsushi Iwasaki; Makoto Yokoo; Yuko Sakurai
Oral presentation, English, the proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2009)
2009 - Sequential Partition Mechanism for Strongly Budget-Balanced Redistribution
uko Sakurai; Yasumasa Saito; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2009)
2009 - Introducing Communication in Dis-POMDPs with Finite State Machines
Yuki Iwanari; Makoto Tasaki; Makoto Yokoo; Atsushi Iwasaki; Yuko Sakurai
Oral presentation, English, the proceedings of the 2009 IEEE/WIC/ACM International Conference on Intelligent Agent Technology(IAT-2009)
2009 - Secure Keyword Auction: Preserving Privacy of Bidding Prices and CTRs
Yuko Sakurai; Makoto Yokoo; Atsushi Iwasaki; Koutarou Suzuki
Oral presentation, English, the proceedings of the 2009 IEEE/WIC/ACM International Conference on Intelligent Agent Technology(IAT-2009)
2009 - Keyword Auction Protocol for Dynamically Adjusting the Number of Advertisements
YukoSakurai; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 2008 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT-2008)
2008 - Beyond quasi-linear utility: strategy/false-name-proof multi-unit auction protocols
Yuko Sakurai; Yasumasa Saito; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 2008 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT-2008)
2008 - Anonymity-proof Shapley value: extending shapley value for coalitional games in open environments
Naoki Ohta; Vincent Conitzer; Yasufumi Satoh; Atsushi Iwasaki; Makoto Yokoo
Oral presentation, English, the proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2008)
2008 - False-Name-Proof Mechanisms for Hiring a Team
Atsushi Iwasaki; David Kempe; Yasumasa Saito; Mahyar Salek; Makoto Yokoo
Oral presentation, English, the proceedings of the 3rd International Workshop On Internet And Network Economics (WINE-2007)
2007 - Multiagent Planning with Trembling-hand Perfect Equilibrium in Multiagent POMDPs
Yuichi Yabu; Makoto Yokoo; Atsushi Iwasaki
Oral presentation, English, the proceedings of the 10th Pacific Rim International Workshop on Multi-agents (PRIMA-2007), Lecture Notes in Computer Science 2413,
2007 - Making VCG More Robust in Combinatorial Auctions via Submodular Approximation
Makoto Yokoo; Atsushi Iwasaki
Oral presentation, English, the proceedings of the 22nd National Conference on Artificial Intelligence (AAAI-2007)
2007 - A Compact Representation Scheme for Coalitional Games in Open Anonymous Environments
Naoki Ohta; Atsushi Iwasaki; Makoto Yokoo; Koki Maruono; Vincent Conitzer; Tuomas Sandholm
Oral presentation, English, the proceedings of the 21st National Conference on Artificial Intelligence (AAAI-2006)
2006 - False-name-proof Combinatorial Auction Protocol:Groves Mechanism with Submodular Approximation
Makoto Yokoo; Toshihiro Matsutani; Atsushi Iwasaki
Oral presentation, English, the proceedings of the 5th In- ternational joint Conference on Autonomous Agents and Multiagent Systems(AAMAS-2006)
2006 - Coalitional Games in Open Anonymous Environments
Makoto Yokoo; Vincent Conitzer; Tuomas Sandholm; Naoki Ohta; Atsushi Iwasaki
Oral presentation, English, the proceedings of the 5th International Joint Conferences on Artificial Intelligence(IJCAI-2005)
2005 - A New Strategy-Proof Greedy-Allocation Combinatorial Auction Protocol and Its Extension to Open Ascending Auction Protocol
Takayuki Ito; Makoto Yokoo; Atsushi Iwasaki; Shigeo Matsubara
Oral presentation, English, the proceedings of the 20th National Conference on Artificial Intelligence (AAAI-2005)
2005 - Reinforcement Learning on Monopolistic Intermediary Games: Subject Experiments and Simulation
Atsushi Iwasaki; Kazuhito Ogawa; Makoto Yokoo; Sobei H. Oda
Oral presentation, English, The Fourth International Workshop on Agent-based Approaches in Economic and Social Complex Systems (AESCS-2005)
2005 - Stability of the Truth-telling strategy in Multi-unit Option Allocation Auctions: Laboratory Experimentation
Atsushi Iwasaki; Masafumi Matsuda; Makoto Yokoo
Oral presentation, English, the proceedings of the 6th workshop on game theoretic and decision theoretic agents (GTDT-2004) at the third international joint conference on Autonomous agents and multiagent systems (AAMAS-2004)
2004 - A Robust Open Ascending-price Multi-unit Auction Protocol against False-name Bids
Atsushi Iwasaki; Makoto Yokoo; Kenji Terada
Oral presentation, English, the proceedings of the 4th ACM Conference on Electric Commerce
2003
Courses
- オペレーションズ・リサーチ基礎
Oct. 2020 - Present
The University of Electro-Communications - Operations Research II
Oct. 2020 - Present
The University of Electro-Communications - Game Theory
Oct. 2020 - Present
The University of Electro-Communications - 大学院技術英語
Apr. 2021 - Sep. 2023
The University of Electro-Communications - 輪講A
The University of Electro-Communications - 輪講A
電気通信大学 - オペレーションズリサーチ基礎
The University of Electro-Communications - オペレーションズリサーチ基礎
電気通信大学 - オペレーションズリサーチ第二
The University of Electro-Communications - オペレーションズリサーチ第二
電気通信大学 - Operations Research II
The University of Electro-Communications - オペレーションズ・リサーチII
電気通信大学 - Game theory
The University of Electro-Communications - ゲーム理論
電気通信大学 - Management informatics 2
The University of Electro-Communications - 経営情報システム論２
電気通信大学
Affiliated academic society
Research Themes
- Resource Allocation Mechanism for Multiagent Systems: Theory and Practice
岩崎敦
CyberAgent, Inc, Principal investigator
Apr. 2024 - May 2025 - Sequential Decision Making with Imperfect Information: Machine Learning and Information Theory
岩崎 敦
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Challenging Research (Exploratory), Principal investigator, 23K17547
Jun. 2023 - Mar. 2025 - Toward Establishing Data-Driven Incentive Engineering
岩崎 敦; 野田 俊也
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (A), 21H04890
Apr. 2021 - Mar. 2025 - Resource Allocation Mechanism for Multiagent Systems: Theory and Practice
岩崎敦
CyberAgent, Inc, Principal investigator
Apr. 2023 - Mar. 2024 - Sequential Decision Making under Imperfect Information: A POMDP approach
本研究では，情報系諸分野の理論を探索して，不完全情報下における逐次的意思決定の分析手法を開拓することを目的とする．具体的には，私的観測というお互いの行動を正確に観測できない不完全観測下で繰り返し行われる意思決定をゲーム理論の枠組みで考え，そのゲームの帰結 (均衡) を求める．これは部分観測可能マルコフ決定過程に帰着できることが知られているが，解析可能な定式化や解法は未だ見つかっていない．そこで，近年発展が著しい機械学習理論／制御理論／情報理論といった諸分野の理論から，大規模な問題に適用可能な，精度保証つきの近似解法を構築する．
30 Jul. 2020 - 31 Mar. 2022 - Establishing a Practical Theory of Market Design
Yokoo Makoto
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyushu University, Grant-in-Aid for Scientific Research (A), In this project, we conducted theoretical researches on general market design. We published 32 articles in international journals and 33 papers from proceedings of international conferences, and 18 invited talks. We also conducted 14 international joint researches in total. During the project, PI and Co-PIs have received several community/conference awards, including the Commendation for Science and Technology by MEXT., 17H00761
01 Apr. 2017 - 31 Mar. 2020 - ゲーム理論的資源配分メカニズムの定量的評価基盤の構築
岩崎敦
01 Apr. 2017 - 31 Mar. 2020 - 不完全情報下における動学ゲームの計量経済学的推定技術の設計・評価
岩崎敦
01 Apr. 2017 - 31 Mar. 2020 - ゲーム理論的資源配分メカニズムの定量的評価基盤の構築
岩崎敦
01 Apr. 2017 - 31 Mar. 2019 - 不完全情報下における動学ゲームの計量経済学的推定技術の設計・評価
岩崎敦
01 Apr. 2017 - 31 Mar. 2019 - 最適化にもとづく電力市場メカニズム設計のための理論的基盤の構築
岩崎敦
01 Apr. 2014 - 31 Mar. 2017 - 持続可能な発展のための資源配分メカニズム設計理論の構築
横尾 真
31 May 2012 - 31 Mar. 2017 - 岩崎 敦准教授に対する研究助成
アイ・システム株式会社, 岩崎 敦准教授に対する研究助成
2017 - 岩崎 敦准教授に対する研究助成
富士通研究所, 岩崎 敦准教授に対する研究助成
2017 - Foundation of Parametric Mechanism Design Technique via Quantifier Elimination
YOKOO MAKOTO; TODO Taiki; IWASAKI Atsushi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyushu University, Grant-in-Aid for Challenging Exploratory Research, In this project, we proposes an alternative automated mechanism design approach called parametric mechanism design via quantifier elimination (PMD-QE), which utilizes QE, a symbolic formula manipulation technique. In PMD-QE, we first develop a skeleton of mechanisms, which is characterized by a set of parameters, e.g., critical values for auction. The range of parameters where the given constraints are satisfied is automatically identified by QE. To demonstrate the potential of this idea, we identified a non-trivial dominant-strategy incentive compatible mechanism that maximizes the sellers revenue by appropriately setting those parameters, for a setting where a bidder has a publicly known budget limit. Some part of the contribution appeared in the proceedings of AAMAS-15, which is the top-tier international conference in the field of multi-agent systems, and presented at a poster session., 26540118
01 Apr. 2014 - 31 Mar. 2016 - 岩崎 敦准教授に対する研究助成
アイ・システム株式会社, 岩崎 敦准教授に対する研究助成
2016 - 消耗財ダブルオークションにおける収益最大化メカニズムの設計と評価
宮下 和雄
01 Apr. 2012 - 31 Mar. 2015 - 岩崎 敦准教授に対する研究助成
アイ・システム株式会社, 岩崎 敦准教授に対する研究助成
2015 - 岩崎 敦准教授に対する研究助成
富士通研究所, 岩崎 敦准教授に対する研究助成
2014 - Toward designing collusion-proof combinatorial procurement mechanisms
IWASWAKI Atsushi; YOKOO Makoto
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research (C), This research project aims to models procurement auction mechanisms (rules or protocols) in the presence of a buyer and several (potentially) collusive bidders, propose a novel mechanism whose outcome is not affected through collusion (collusion-proof), and develop a technique for adjusting the performance. First, we extend a single-item auction mechanism to a multi-unit one where multiple identical items are sold and bidders may collude. This reveals that a collusion-proof mechanism is equivalent to the one that minimize buyer's payments in expectation. Second, we propose an alternative technology that automatically designs a mechanism via quantifier elimination and successfully construct a novel class of such a payment-minimizing mechanism for a restricted environment where a buyer is required to buy an item for sale. We further explore another case where sellers face the budget limits and find another class of desirable mechanisms., 23500184
2011 - 2013 - Automated design of social choice rules by optimization and rule extraction
YOKOO Makoto; IWASAKI Atsushi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyushu University, Grant-in-Aid for Challenging Exploratory Research, The goal of this research project is to develop a method for automatically generating social choice rules that can be applied to large-scale problem instances by combining existing automated mechanism design techniques (which can be applied only for small-scare problem instances) and rule discovery techniques. In this research, we first develop an important core technology for achieving this goal, i.e., a method for extracting social choice rules that satisfy desirable properties based on the results obtained by automated mechanism design. This result was presented at Forum on Information Technology (FIT) and obtained the best paper award (Funai best paper award). Furthermore, the existing automated mechanism design techniques use integer programming to obtain optimal rules for a given criterion. As a result, the types of participants must be represented as a set of discrete values. We develop a new method for directly obtaining social choice rules based on another optimization technique called quantifier elimination, which can handle non-linear, continuous variables., 23650073
2011 - 2012 - Development of Theory of Mechanism Design for Information Network Economics
YOKOO Makoto; SUGAWARA Toshiharu; WATANABE Takahiro; KIKUCHI Hiroaki; ODA Hidenori; IZUMI Kiyoshi; MATSUBARA Shigeo; YAMAKI Hirofumi; IWASAKI Atsushi; SAKURAI Yuko; ITO Takayuki
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyushu University, Grant-in-Aid for Scientific Research (A), We have developed the mechanism generators which automatically generate the mechanism that can satisfy the given conditions. Especially, we proposed component mechanisms stored in mechanism data bases and also developed the technologies of automated mechanism design which are fundamental to mechanism generators.As our research results, we presented 68 papers at international/domestic conferences and published 54 papers in international/domestic journals. We received the best student award in 2008 and the best student award runner up in 2009 at Int. Conf. on AutonomousAgents and Multiagent Systems (AAMAS), which is one of the top international conferences in the research field of multiagent systems. Furthermore, in 2008, we received the best paper award at IEEE/WIC/ACM Int. Conf. on Intelligent Agent Technology (IAT). Our paper on the automated mechanism design technologies received Funai best paper award at FIT2011, which is a major domestic conference on information technologies., 20240015
2008 - 2012 - Toward designing combinatorial auction mechanisms for dynamic and uncertain environments
第7回マイクロソフトリサーチCORE連携研究プログラム, 岩崎 敦准教授に対する研究助成
2011 - Design and Implementation of e-Business Support Mechanisms based on Computational Mechanism Design Theories
ITO Takayuki; OZONO Tadachika; IWASAKI Atsushi; YOKOO Makoto; FUKUTA Naoki; MATSUBARA Shigeo
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Nagoya Institute of Technology, Grant-in-Aid for Scientific Research (B), In this research, we designed, implemented and evaluated several e-business support systems based on computational mechanism design theories and other theories. In terms of computaional mechanism design theories, we proposed and designed the interdependent valua auctions and complex automated negotiation mechanisms. Also, we designed and implemented aim-oriented recommendation systems, trust evaluation system for auctions, and franchise business task allocation systems. We confirmed that these systems can work effectively by conducting some experiments., 18300049
2006 - 2009 - 開環境での協力ゲームにおける新しい解概念の提案
横尾 真; 岩崎 敦
日本学術振興会, 科学研究費助成事業, 九州大学, 萌芽研究, 本研究では,インターネット等め開環境での協力ゲームにおける新しい解概念を提案することを目的とする.具体的には,ネットワークでの匿名性を用いて,参加者が談合を行ったり,架空の名義を用いるといった不正行為を行うことが可能な場合でも,そのような不正行為の影響を受けない利益の配分方法を考案する.また,提案する解概念に関しては,解を求めるための計算のコストを考慮し,動的な変化に対応して迅速に解を求めることを可能とする.本年度は,昨年度に提案した匿名操作不可能シャプレイ値をマルチエージェントシステムのトップレベルの国際会議であるAAMAS2008にて発表した.さらにこの論文は学生優秀論文賞を獲得した. 一方で,利己的なエージェント間で協調関係を結ぶことが可能な協力ゲームにおいて,社会的に望ましい協調関係(提携)を形作ること,すなわち提携構造の形成は,重要な研究分野である.提携構造形成問題(CSG, Coalition Structure Generation)では,エージェントの集合を,社会的余剰(効用の総和)が最大化されるように分割する.すなわち,事前に適切な提携の候補を表現した上で,不正行為の影響を受けない利益の配分方法を考える. しかし,協力ゲームでは,エージェントが形成する提携に対して,その効用を与える関数(特性関数)が存在するが,任意の特性関数の表記量は指数的に増加するため,多くのエージェントが存在する協力ゲームでは,現実的な時間で提携構造形成問題の解を発見することは困難である.そこで,特性関数の特徴的な構造を利用した簡略記述法であるMC-nets (Marginal Contribution networks)およびSCG (Synergy Coalition Group)を利用して,提携構造形成問題を従来よりはるかに高速に解くことができることを明らかにした.なお,この研究成果は12月にDuke大学のVincet Conitzer氏を招聘して進めた成果である., 19650004
2007 - 2008 - Implementing an Electronic Commerce Mechanism based on Software Agents
OZONO Tadachika; ITO Takayuki; YOKOO Makoto; IWASAKI Atsushi; FUKUTA Naoki; MATSUO Tokuro; MATSUBARA Shigeo
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Nagoya Institute of Technology, Grant-in-Aid for Scientific Research (B), 本研究では, ゲーム理論をツールとして用いることによって, 財の質に注目した効率的な電子商取引メカニズムを理論的に設計し, 具体的に実機上にシステムとして実装することを目的として, Web上のエージェントに基づくシステム構築技術, オークションヘルプシステム, および, オークション勝者の並列高速近似アルゴリズムを実現した. 本システムではソフトウェアエージェントによって, ユーザのオークションでのWWW上でのインタラクションを効果的に支援することが可能になった., 17300046
2005 - 2008 - Market Mechanism and Institutional Design in Durable Goods Recycling
ODA Hidenori; YASUGI Mariko; UEDA Kanji; KITAMURA Ryuichi; YOKOO Yokoo; IIDA Yoshio; IWASAKI Iwasaki; IYORI Kouhei; OGAWA Kazuhito; NISHINO NARIAKI
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyoto Sangyo University, Grant-in-Aid for Scientific Research (B), 本研究課題は, 耐久消費財リサイクル市場を理論的に記述し, 被験者実験やシミュレーションを通じて, 耐久消費財の生産, 循環のための市場の構造分析から, 社会的に望ましい市場制度設計の問題について研究を進めた. 結果として, 消費者と処理業者を仲介するディーラーの存在がリサイクル効率を高くする傾向が示された. さらに, 環境配慮行動の意思決定分析や社会制度に関わる実験を実施し, 耐久消費財リサイクル問題に対して総合的に研究を行った., 17310029
2005 - 2008 - Design and Evaluation of Internet Auction Protocols robust against cheatings
YOKOO Makoto; IWASAKI Atsushi; AMAMIYA Makoto; MINE Tsunenori; ODA Hidenori; OGAWA Kazuhito
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyushu University, Grant-in-Aid for Scientific Research (B), This project designs and examines combinatorial auction protocols which are(almost)robust against a variety of cheatings on the Internet. We focused on a data transfer on ad hoc networks, such as P2P networks and distributed sensor networks. We first show that existing auction protocols are influenced by false-name manipulations. More precisely, an owner of nodes can pretend that a node is in fact a set of multiple nodes, or all of which must be purchased from different owners. We proposed and analyzed a false-name-proof mechanism, where an owner may have multiple elements. We presented those results at WI- 2007 On the other hand, we developed the Agent-Community-based Peer-to-Peer Information Retrieval(ACP2P)method. This method uses agent communities to manage and look up information of interest to users. An agent works as a delegate of its user and searches for information that the user wants by communicating with other agents. We presented those results at WI-2007 In addition, we conducted multi-agent simulations and subject experiments in recycle markets, monopolistic intermediary markets, and so on. Though those results depend on a specific market situation, we extended subject's decision-making models and successfully reproduce subject behavior in the multi-agent simulations. Also, we presented lots of papers in false-name-proof auction protocol and cooperative games in journals and conferences. Finally,as an integration of our results,we study automated mechanism design,as a mechanism design technique,for new mechanisms on the Internet Mechanism has traditionally been designed manually for classes of problems.In automated mechanism design,a mechanism can be automatically designed using constrained optimization technique. Our results are expected to develop and examine more rapidly and better mechanisms for actual human and massively multiagent systems., 17300049
2005 - 2007 - 情報財の流通/取引メカニズムの設計に関する企画調査
横尾 真; 岩崎 敦; 渡辺 隆裕; 松原 繁夫; 和泉 潔; 伊藤 孝行
日本学術振興会, 科学研究費助成事業, 九州大学, 基盤研究(C), 本企画調査では,情報財の流通/取引メカニズムの設計に関する海外の研究動向を調査すると共に,国内で当該研究テーマに興味を持つ研究者を集めて議論を行うことにより,工学や社会科学という枠を越えた交流を深め,当該研究テーマに関する研究を活性化し,当該研究テーマを特定領域研究の研究領域として発展させることを目的とする. 今年度は6,7,9,10月に4回の研究集会を行った.情報セキュリティ技術やゲーム理論/経済学といった様々な分野の専門家を招聘し,情報財の新しい流通/取引のメカニズムに関して議論を行った.その結果,新たな特定領域研究の研究領域として,「情報ネットワーク経済のためのメカニズム設計技術の確立」を申請するにいたった.これは「情報ネットワーク経済」を情報ネットワークが深く関連する経済活動と定義し,情報ネットワーク経済において,取引や価格設定のメカニズムを設計するための技術を確立することを目的とした.具体的には,ユーザ(メカニズムの設計者)の要求条件に応じて,要求条件を満たす結果を与えるメカニズムを自動的に生成するメカニズムジェネレータ,および,与えられたメカニズムに対して,メカニズムを適用した結果を予測し,結果の安定性,不正行為に対する頑健性等を検証するメカニズムチェッカの開発を目指している. 加えて,3月にもデータマイニングや実験経済学の専門家を招聘し,これまでの検討に対するフィードバックを得た.加えて.メカニズムデザインに関する図書および記事論文を発表している., 18630004
2006 - 2006 - 複数均衡をもつゲーム/メカニズムにおける適応的学習理論の構築と実験的検証
岩崎 敦
日本学術振興会, 科学研究費助成事業, 九州大学, 若手研究(B), 本研究では,プレイヤにとって複数均衡をもつゲーム/メカニズムの実験的検証を通じて,人間が,ゲーム/メカニズムの構造や相手の行動を観察し,自分および相手の行動などの情報交換の影響を比較し,その意思決定過程を記述する適応的学習理論を構築する. とくに今年度は昨年度提案した「損失回避(Loss avoidance)」の概念を精緻化した「確定的な損失回避(certain loss avoidance)」および「不確定な損失回避(possible loss avoidance)」が実験結果に現れることを2つの国際会議で発表した.さらに新たに「均衡における損失回避(equilibrium loss avoidance)」を検証する被験者実験を実施した.この新しい概念は負の利得を与える戦略の組み合わせが均衡解となっているとき,その均衡解にいたる戦略を回避する概念である.これに関してはそれほど強くはないが,被験者がこの原理に基づいて行動する傾向を確認した.これらの研究成果はワーキングペーパーとして発表するとともに前半部分をGames and Economic Behaviorに投稿している. さらに,適応的学習理論の適用として,プレイヤが仕入価格と販売価格を選択する独占的仲介市場における価格形成に対する強化学習の再現性を吟味した論文をAgent-Based Approaches in Economics and Social Complex Systems IVに発表した.関連する研究業績として,架空の名義を用いた不正行為に頑健なオークションプロトコルや協力ゲームの解概念に関する研究を学術論文および国際会議にて発表した., 17700155
2005 - 2006 - Model of false-name-proof negotiation protocol for networked resources and its evaluation
SUGAWARA Toshiharu; YOKOO Makoto; MATSUBARA Shigeo; IWASAKI Atsushi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Nippon Telegraph and Telephone Corporation, NTT Communication Science Laboratories, Grant-in-Aid for Scientific Research (C), This research aims to evaluate the market-based fair and efficient protocol, in order to apply it to the allocations of networked resources for its future applications to this domain. In ad hoc networks used in P2P and the decentralized sensor network, for example, individual nodes are owned by different persons and designed based different specifications. In this case, it is necessary to consider the incentives, that is, reward, to transmit data to each node appropriately. The auction protocol is often used for the decision of this reward. However, by using the fake (false-name) node or by conspiring with other nodes, a certain node can acquire the reward illegally in conventional protocols. We theoretically showed that this type of illegal behaviors cannot be prevented even in Vickrey-Clarke-Groves protocol (VCG) in the research period by this grant. We then proposed Reserve-Cost protocol (RC), which is the extension of VCG by introducing the penalty proportional to the number of agents (nodes) who manage the network route. We also clarified that the RC is false-name proof, that is, the fairness of RC protocol is not influenced by the false-name bids. In addition, we also showed that RC is more efficient than VCG about 60-80% by small-scale network simulation. Moreover, it is necessary for agents to decide, by using some protocols such as auctions, where to receive/send data based on locally available information in an actual network. This corresponds to the selection of an awarder to some degree when multiple bidding agents (this corresponds to servers in this case) are identified as the appropriate for awarders. In this research, we investigated and analyzed the phenomenon occurring when such a resource allocation protocol was used in a large-scale multi-agent system such as network. In this type of systems, many demands like the resource allocation on the network occurs simultaneously from many different agents independently, thus the entire efficiency falls down. We also identified that a little bit of fluctuation can significantly improved the entire performance by avoiding concentration., 17500102
2005 - 2006
Media Coverage
- AI Lab、機械学習分野のトップカンファレンス「ICML 2024」にて、過去最多となる5本の論文採択
Other than myself, サイバーエージェント, サイバーエージェントAILAB, https://www.cyberagent.co.jp/news/detail/id=30359, Internet
19 Jun. 2024 - AI Lab、機械学習分野のトップカンファレンス「AISTATS 2023」にて2本の主著論文採択
サイバーエージェント, Internet
Apr. 2023 - AI Lab、機械学習分野のトップカンファレンス「UAI2022」にて主著論文採択ーマルチエージェント環境における学習を安定化させる手法を提案ー
サイバーエージェント, Internet
Jul. 2022 - AI Lab、人工知能分野のトップカンファレンス「IJCAI」にて2本の共著論文採択ーマッチング問題および推薦システムにおける性能向上に繋がる手法を提案ー
サイバーエージェント, Internet
Jun. 2022
Academic Contribution Activities
- Games, Agents and Incentives 2024 Program Comittee
Peer review etc, Peer review, 20 Feb. 2024 - 31 Dec. 2024 - AAMAS2024 program comittee
Academic society etc, Peer review, IFAAMAS, 01 Sep. 2023 - 31 Aug. 2024 - Workshop on Social Choice and Learning Algorithms 2024 Program Comittee
Academic society etc, Peer review, 15 Feb. 2024 - 01 Jun. 2024 - ゲーム理論ワークショップ
Academic society etc, Planning etc, ゲーム理論ワークショッププログラム委員会, 01 Sep. 2023 - 31 Mar. 2024 - IJCAI2024 program comittee
Academic society etc, Peer review, IJCAI, 01 Apr. 2023 - 31 Mar. 2024 - ゲーム理論ワークショップ
Others, Feb. 2023 - IJCAI2023 program comittee
Academic society etc, Peer review, IJCAI
Others
- アイ・システム株式会...
アイ・システム株式会社顧問
2021 - 2021 - アイ・システム株式会...
アイ・システム株式会社顧問
2020 - 2020 - 理化学研究所革新知能統合研究センター，マルチエージェント最適化チーム，チームリーダー（兼任）
2019 - 2019 - アイ・システム株式会社顧問
2019 - 2019 - アイ・システム株式会社顧問
2018 - 2018 - 理化学研究所革新知能統合研究センター，マルチエージェント最適化チーム，チームリーダー（兼任）
2018 - 2018 - 理化学研究所革新知能統合研究センター，マルチエージェント最適化チーム，チームリーダー（兼任）
2017 - 2017 - アイ・システム株式会社顧問
2017 - 2017
