2022-10-06T14:18:48Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001415472017-03-31T05:36:57Z05471:07854:08225
Low-Complexity Exploration in Utility HypergraphsLow-Complexity Exploration in Utility Hypergraphseng[Special Issue of Students' and Young Researchers' Papers] interdependent issues, nonlinear utility, hyper-graph, Max-Sum, entropyhttp://id.nii.ac.jp/1001/00141516/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=141547&item_no=1&attribute_id=1&file_no=1Copyright (c) 2015 by the Information Processing Society of JapanDepartment of Computer Science and Engineering, Nagoya Institute of TechnologyDepartment of Computer Science and Engineering, Nagoya Institute of TechnologyRafik, HadfiTakayuki, ItoA novel representation for nonlinear utility spaces is provided, by adopting a modular decomposition of the issues and the constraints. The idea is that constraint-based utility spaces are nonlinear with respect to issues, but linear with respect to the constraints. The result is a mapping from a utility space into an issue-constraint hypergraph. Exploring the utility space is therefore reduced to a message passing mechanism along the hyperedges by means of utility propagation. The optimal contracts are efficiently found using a variation of the Max-Sum algorithm. Particularly, we use a power-law heuristic that lowers the search cost when exploring the utility hypergraph. We experimentally evaluate the model using parameterized random nonlinear utility spaces, showing that it can handle a large family of complex utility spaces using several exploration strategies. The complexity of the generated utility spaces is evaluated using the information theoretic notion of entropy. The optimal search strategy allows a better scaling of the model for complex utility spaces.A novel representation for nonlinear utility spaces is provided, by adopting a modular decomposition of the issues and the constraints. The idea is that constraint-based utility spaces are nonlinear with respect to issues, but linear with respect to the constraints. The result is a mapping from a utility space into an issue-constraint hypergraph. Exploring the utility space is therefore reduced to a message passing mechanism along the hyperedges by means of utility propagation. The optimal contracts are efficiently found using a variation of the Max-Sum algorithm. Particularly, we use a power-law heuristic that lowers the search cost when exploring the utility hypergraph. We experimentally evaluate the model using parameterized random nonlinear utility spaces, showing that it can handle a large family of complex utility spaces using several exploration strategies. The complexity of the generated utility spaces is evaluated using the information theoretic notion of entropy. The optimal search strategy allows a better scaling of the model for complex utility spaces.AA00700121Journal of information processing2321761842015-03-151882-66522015-03-20