// shapley.cpp// 整合通用特征函数 Shapley MATLAB 风格包装 加权多数博弈 Shapley-Shubik#includevector#includecmath#includeiostream#includenumeric#includestdexcept#includeiomanip// 工具函数手写 popcount可移植 staticintpopcount32(unsignedintx){intc0;while(x){xx-1;c;}returnc;}// 1. 通用特征函数 Shapley 计算 // 输入: v: 长度为 2^n 的数组, v[mask] 表示联盟 mask 的价值// (mask 的第 i 位为 1 表示包含玩家 i从 0 开始编号)// 输出: 长度为 n 的 Shapley 值向量std::vectordoublecomputeShapley(conststd::vectordoublev){intn0;while((1un)v.size())n;if((1un)!v.size())throwstd::invalid_argument(v.size() must be 2^n);std::vectordoublephi(n,0.0);// 预计算阶乘std::vectordoublefact(n1,1.0);for(inti1;in;i)fact[i]fact[i-1]*i;doublen_factfact[n];for(inti0;in;i){doublesum0.0;intmask_i1i;// 枚举所有不包含玩家 i 的联盟 Sfor(intS0;S(1n);S){if(Smask_i)continue;intspopcount32((unsigned)S);intS_with_iS|mask_i;doublemarginalv[S_with_i]-v[S];doubleweightfact[s]*fact[n-s-1]/n_fact;sumweight*marginal;}phi[i]sum;}returnphi;}// 2. MATLAB 风格包装 // 输入: v 长度 2^n - 1按二进制数顺序存放非空联盟价值// 与 MATLAB shapley(v) 的 right 约定一致std::vectordoubleshapleyMatlabStyle(conststd::vectordoublev){intn0;while((1un)-1v.size())n;std::vectordoublev_full(1un,0.0);for(size_t mask1;mask(1un);mask){v_full[mask]v[mask-1];}returncomputeShapley(v_full);}// 3. 加权多数博弈Shapley-Shubik 指数 intg_n0;intg_quota0;std::vectorintg_weights;std::vectorboolg_used;std::vectordoubleg_power;longlongg_total_permutations0;voiddfsShapleyShubik(intdepth,intcurrent_weight,boolpivot_found,intpivot){if(depthg_n){if(pivot_found)g_power[pivot]1.0;g_total_permutations;return;}for(inti0;ig_n;i){if(g_used[i])continue;g_used[i]true;intnew_weightcurrent_weightg_weights[i];if(!pivot_foundnew_weightg_quota){dfsShapleyShubik(depth1,new_weight,true,i);// i 成为关键玩家}else{dfsShapleyShubik(depth1,new_weight,pivot_found,pivot);}g_used[i]false;}}std::vectordoublecomputeShapleyShubik(conststd::vectorintweights,intquota){g_n(int)weights.size();g_quotaquota;g_weightsweights;g_used.assign(g_n,false);g_power.assign(g_n,0.0);g_total_permutations0;dfsShapleyShubik(0,0,false,-1);if(g_total_permutations0){for(doublep:g_power)p/(double)g_total_permutations;}returng_power;}// main三个 Demo intmain(){std::coutstd::fixedstd::setprecision(6);// ---- 演示 1通用合作博弈 ----// 玩家位映射bit0玩家1, bit1玩家2, bit2玩家3// v(∅)0, v({1})0, v({2})0, v({1,2})1, v({3})0,// v({1,3})1, v({2,3})0, v({1,2,3})1std::vectordoublev{0,0,0,1,0,1,0,1};autophicomputeShapley(v);std::cout Demo 1: General Coalition Game \n;std::coutphi [;for(size_t i0;iphi.size();i)std::coutphi[i](i1phi.size()?, :);std::cout]\n\n;// ---- 演示 2MATLAB 风格输入去掉空集长度 2^n - 1 ----std::vectordoublev_matlab{0,0,1,0,1,0,1};// 与 Demo 1 同一博弈autophi_mshapleyMatlabStyle(v_matlab);std::cout Demo 2: MATLAB-style Input \n;std::coutphi [;for(size_t i0;iphi_m.size();i)std::coutphi_m[i](i1phi_m.size()?, :);std::cout]\n\n;// ---- 演示 3加权多数博弈5 人简单多数 ----std::vectorintweights{1,1,1,1,1};intquota3;// 达到 3 票即获胜autopowercomputeShapleyShubik(weights,quota);std::cout Demo 3: Weighted Majority Game (5 players, simple majority) \n;std::coutpower [;for(size_t i0;ipower.size();i)std::coutpower[i](i1power.size()?, :);std::cout]\n;std::couttotal permutations g_total_permutations\n;return0;}