C++代码实现MATLAB中的shapley函数功能

// shapley.cpp
// 整合：通用特征函数 Shapley + MATLAB 风格包装 + 加权多数博弈 Shapley-Shubik
#include <vector>
#include <cmath>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <iomanip>

// ==================== 工具函数：手写 popcount（可移植） ====================
static int popcount32(unsigned int x) {
int c = 0;
while (x) { x &= x – 1; ++c; }
return c;
}

// ==================== 1. 通用特征函数 Shapley 计算 ====================
// 输入: v: 长度为 2^n 的数组, v[mask] 表示联盟 mask 的价值
// (mask 的第 i 位为 1 表示包含玩家 i，从 0 开始编号)
// 输出: 长度为 n 的 Shapley 值向量
std::vector<double> computeShapley(const std::vector<double>& v) {
int n = 0;
while ((1u << n) < v.size()) ++n;
if ((1u << n) != v.size())
throw std::invalid_argument("v.size() must be 2^n");

std::vector<double> phi(n, 0.0);

// 预计算阶乘
std::vector<double> fact(n + 1, 1.0);
for (int i = 1; i <= n; ++i) fact[i] = fact[i – 1] * i;
double n_fact = fact[n];

for (int i = 0; i < n; ++i) {
double sum = 0.0;
int mask_i = 1 << i;

// 枚举所有不包含玩家 i 的联盟 S
for (int S = 0; S < (1 << n); ++S) {
if (S & mask_i) continue;
int s = popcount32((unsigned)S);
int S_with_i = S | mask_i;

double marginal = v[S_with_i] – v[S];
double weight = fact[s] * fact[n – s – 1] / n_fact;
sum += weight * marginal;
}
phi[i] = sum;
}
return phi;
}

// ==================== 2. MATLAB 风格包装 ====================
// 输入: v 长度 2^n – 1，按二进制数顺序存放非空联盟价值
// （与 MATLAB shapley(v) 的 'right' 约定一致）
std::vector<double> shapleyMatlabStyle(const std::vector<double>& v) {
int n = 0;
while ((1u << n) – 1 < v.size()) ++n;
std::vector<double> v_full(1u << n, 0.0);
for (size_t mask = 1; mask < (1u << n); ++mask) {
v_full[mask] = v[mask – 1];
}
return computeShapley(v_full);
}

// ==================== 3. 加权多数博弈（Shapley-Shubik 指数） ====================
int g_n = 0;
int g_quota = 0;
std::vector<int> g_weights;
std::vector<bool> g_used;
std::vector<double> g_power;
long long g_total_permutations = 0;

void dfsShapleyShubik(int depth, int current_weight,
bool pivot_found, int pivot) {
if (depth == g_n) {
if (pivot_found) g_power[pivot] += 1.0;
++g_total_permutations;
return;
}
for (int i = 0; i < g_n; ++i) {
if (g_used[i]) continue;
g_used[i] = true;
int new_weight = current_weight + g_weights[i];
if (!pivot_found && new_weight >= g_quota) {
dfsShapleyShubik(depth + 1, new_weight, true, i); // i 成为关键玩家
} else {
dfsShapleyShubik(depth + 1, new_weight, pivot_found, pivot);
}
g_used[i] = false;
}
}

std::vector<double> computeShapleyShubik(const std::vector<int>& weights, int quota) {
g_n = (int)weights.size();
g_quota = quota;
g_weights = weights;
g_used.assign(g_n, false);
g_power.assign(g_n, 0.0);
g_total_permutations = 0;

dfsShapleyShubik(0, 0, false, –1);

if (g_total_permutations > 0) {
for (double& p : g_power) p /= (double)g_total_permutations;
}
return g_power;
}

// ==================== main：三个 Demo ====================
int main() {
std::cout << std::fixed << std::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})=1
std::vector<double> v = {0, 0, 0, 1, 0, 1, 0, 1};
auto phi = computeShapley(v);
std::cout << "=== Demo 1: General Coalition Game ===\\n";
std::cout << "phi = [";
for (size_t i = 0; i < phi.size(); ++i)
std::cout << phi[i] << (i + 1 < phi.size() ? ", " : "");
std::cout << "]\\n\\n";

// —- 演示 2：MATLAB 风格输入（去掉空集，长度 2^n – 1） —-
std::vector<double> v_matlab = {0, 0, 1, 0, 1, 0, 1}; // 与 Demo 1 同一博弈
auto phi_m = shapleyMatlabStyle(v_matlab);
std::cout << "=== Demo 2: MATLAB-style Input ===\\n";
std::cout << "phi = [";
for (size_t i = 0; i < phi_m.size(); ++i)
std::cout << phi_m[i] << (i + 1 < phi_m.size() ? ", " : "");
std::cout << "]\\n\\n";

// —- 演示 3：加权多数博弈（5 人简单多数） —-
std::vector<int> weights = {1, 1, 1, 1, 1};
int quota = 3; // 达到 3 票即获胜
auto power = computeShapleyShubik(weights, quota);
std::cout << "=== Demo 3: Weighted Majority Game (5 players, simple majority) ===\\n";
std::cout << "power = [";
for (size_t i = 0; i < power.size(); ++i)
std::cout << power[i] << (i + 1 < power.size() ? ", " : "");
std::cout << "]\\n";
std::cout << "total permutations = " << g_total_permutations << "\\n";

return 0;
}