Automated design of social choice rules by optimization and rule extraction

通过优化和规则提取自动设计社会选择规则

• 批准号: 23650073
• 负责人: YOKOO Makoto
• 金额: $ 2.33万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Challenging Exploratory Research
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2012
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23650073/
• 关键词: ゲーム理論; 最適化; メカニズムデザイン; オークション; 架空名義操作; インターネットオークション; 架空名義入札

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.

本研究项目的目标是开发一种方法，通过结合现有的自动化机制设计技术（仅适用于小规模问题实例）和规则发现技术，自动生成社会选择规则，可以应用于大规模的问题实例。在这项研究中，我们首先开发了实现这一目标的重要核心技术，即，一种根据自动化机构设计的结果，提取满足期望属性的社会选择规则的方法。这一成果在信息技术论坛（FIT）上发表，并获得了最佳论文奖（船井最佳论文奖）。此外，现有的自动化机构设计技术使用整数规划来获得针对给定准则的最优规则。因此，参与者的类型必须表示为一组离散值。我们开发了一种新的方法，直接获得社会选择规则的基础上，另一种优化技术称为量词消除，它可以处理非线性，连续变量。

项目成果

BnB-ADOPT_P : 分散制約最適化問題におけるハイブリッド型の解法の提案

BnB-ADOPT_P：分布式约束优化问题混合求解方法的提出

• 发表时间: 2012
• 作者: 沖本天太;山本将;櫻井祐子;横尾真;井上克巳
• 通讯作者: 井上克巳

MC-netsを用いた提携構造形成アルゴリズムの拡張：負の利得と外部性の導入

使用 MC-nets 扩展联盟结构形成算法：引入负收益和外部性

• 发表时间: 2011
• 期刊: 電子情報通信学会論文誌
• 作者: 一村 良;長谷川 隆人;上田 俊;岩崎 敦;横尾 真
• 通讯作者: 横尾 真

Concise Characteristic Function Representations in Coalitional Games Based on Agent Types

基于Agent类型的联盟博弈简明特征函数表示

• 发表时间: 2011
• 作者: Suguru Ueda;Makoto Kitaki,Atsushi Iwasaki;Makoto Yokoo
• 通讯作者: Makoto Yokoo

Automated Equilibrium Analysis of Repeated Games with Private Monitoring: A POMDP Approach

使用私人监控进行重复博弈的自动均衡分析：POMDP 方法

• 作者: Yongjoon Joe;Atsushi Iwasaki;Michihiro Kandori;Ichiro Obara;and Makoto Yokoo
• 通讯作者: and Makoto Yokoo

自動メカニズムデザインを利用した組合せオークションのルール抽出アルゴリズムの提案

使用自动机制设计的组合拍卖规则提取算法的提案

• 发表时间: 2012
• 期刊: 情報処理学会論文誌
• 作者: 毛利貴之;杉町勇和;東藤大樹;岩崎敦;横尾真
• 通讯作者: 横尾真