1 Purpose

This standalone RPubs note explains the game-theory backbone behind a decentralized scheduling framework for electromagnetic follow-up of gravitational-wave events.

We begin from elementary game theory and gradually move toward the telescope scheduling framework:

\[ \text{simple game} \rightarrow \text{best response} \rightarrow \text{Nash equilibrium} \rightarrow \text{potential game} \rightarrow \text{marginal-contribution utility} \rightarrow \text{telescope scheduling} \rightarrow \text{Shapley credit allocation}. \]

The aim is to make the theory teachable to students who may know physics/astronomy but may not yet know operations research or game theory.

2 Motivating story: the lost umbrella

Suppose an umbrella is lost somewhere on campus. We do not know the exact place. But we have a probability map:

\[ \Pr(\text{Library})=0.45,\quad \Pr(\text{Canteen})=0.25,\quad \Pr(\text{Auditorium})=0.20,\quad \Pr(\text{Garden})=0.10. \]

Several guards can search.

If all guards search Library, the most probable region is covered, but the effort is duplicated. If guards coordinate, they may cover Library, Canteen, and Auditorium in a more balanced way.

This is the philosophy of gravitational-wave follow-up.

Umbrella story	GW follow-up
Lost umbrella	Electromagnetic counterpart
Campus probability map	GW sky-localization map
Guard	Telescope/observatory
Search place	Sky tile
Search time	Observation time slot
Search success chance	Conditional detection probability
Repeated search	Overlapping observation
Fair credit to guards	Shapley credit to telescopes

Bengali-English:

Umbrella কোথায় আছে exact জানা নেই, কিন্তু probability map আছে. GW event-এর source কোথায় আছে exact জানা নেই, কিন্তু sky localization map আছে. Guard যেমন campus search করে, telescope তেমন sky tile observe করে.

3 What is a game?

A finite game has four ingredients:

Players: the decision makers.
Strategies: choices available to each player.
Payoffs/utilities: numerical reward after everyone chooses.
Strategy profile: the full list of choices.

For \(K\) players,

\[ s=(s_1,\ldots,s_K) \]

is a strategy profile, and player \(k\)’s payoff is

\[ u_k(s_1,\ldots,s_K). \]

Bengali-English:

Game theory-তে game মানে sports/gambling নয়. এখানে game মানে interacting decision problem. একজন player কী করবে, তার payoff depend করে অন্যরা কী করছে তার উপর.

4 A first game: two-guard coordination

Two guards can search either Library or Canteen. Library is more probable, but duplicate search is wasteful.

coordination_game <- expand.grid(
  Guard1 = c("Library", "Canteen"),
  Guard2 = c("Library", "Canteen"),
  stringsAsFactors = FALSE
)

coordination_game <- coordination_game %>%
  mutate(
    u1 = case_when(
      Guard1 == "Library" & Guard2 == "Library" ~ 4,
      Guard1 == "Library" & Guard2 == "Canteen" ~ 7,
      Guard1 == "Canteen" & Guard2 == "Library" ~ 5,
      Guard1 == "Canteen" & Guard2 == "Canteen" ~ 3
    ),
    u2 = case_when(
      Guard1 == "Library" & Guard2 == "Library" ~ 4,
      Guard1 == "Library" & Guard2 == "Canteen" ~ 5,
      Guard1 == "Canteen" & Guard2 == "Library" ~ 7,
      Guard1 == "Canteen" & Guard2 == "Canteen" ~ 3
    ),
    total = u1 + u2,
    label = paste0("(", u1, ", ", u2, ")")
  )

kable(coordination_game, caption = "Two-guard coordination game. Cell entries are payoffs (Guard 1, Guard 2).")

Two-guard coordination game. Cell entries are payoffs (Guard 1, Guard 2).
Guard1	Guard2	u1	u2	total	label
Library	Library	4	4	8	(4, 4)
Canteen	Library	5	7	12	(5, 7)
Library	Canteen	7	5	12	(7, 5)
Canteen	Canteen	3	3	6	(3, 3)

ggplot(coordination_game, aes(Guard2, Guard1, fill = total)) +
  geom_tile() +
  geom_text(aes(label = label), size = 6) +
  labs(
    title = "Two-guard payoff matrix",
    subtitle = "Splitting search can reduce duplication and increase total value.",
    x = "Guard 2 chooses",
    y = "Guard 1 chooses",
    fill = "Total payoff"
  )

5 Best response

A best response is the best strategy of one player given what the other players are doing.

For player \(k\),

\[ s_k^\star \]

is a best response to \(s_{-k}\) if

\[ u_k(s_k^\star,s_{-k}) \geq u_k(s_k,s_{-k}) \quad \text{for all alternative }s_k. \]

Bengali-English:

অন্যরা যা করছে সেটা fixed ধরে, আমার সবচেয়ে ভালো response কী — সেটাই best response.

find_nash_2player <- function(df, p1_col, p2_col, u1_col, u2_col) {
  out <- df
  out$best_response_1 <- FALSE
  out$best_response_2 <- FALSE

  for (s2 in unique(df[[p2_col]])) {
    idx <- df[[p2_col]] == s2
    out$best_response_1[idx] <- df[[u1_col]][idx] == max(df[[u1_col]][idx])
  }

  for (s1 in unique(df[[p1_col]])) {
    idx <- df[[p1_col]] == s1
    out$best_response_2[idx] <- df[[u2_col]][idx] == max(df[[u2_col]][idx])
  }

  out$nash <- out$best_response_1 & out$best_response_2
  out
}

coordination_nash <- find_nash_2player(
  coordination_game,
  "Guard1", "Guard2", "u1", "u2"
)

coordination_nash %>%
  select(Guard1, Guard2, u1, u2, best_response_1, best_response_2, nash) %>%
  kable(caption = "Best-response and Nash-equilibrium check for the two-guard game.")

Best-response and Nash-equilibrium check for the two-guard game.
Guard1	Guard2	u1	u2	best_response_1	best_response_2	nash
Library	Library	4	4	FALSE	FALSE	FALSE
Canteen	Library	5	7	TRUE	TRUE	TRUE
Library	Canteen	7	5	TRUE	TRUE	TRUE
Canteen	Canteen	3	3	FALSE	FALSE	FALSE

6 Nash equilibrium

A Nash equilibrium is a profile where every player is best-responding simultaneously.

\[ u_k(s_k^\star,s_{-k}^\star) \geq u_k(s_k,s_{-k}^\star) \quad \text{for every player } k. \]

Bengali-English:

Nash equilibrium মানে এমন অবস্থা যেখানে কেউ একা strategy change করে নিজের payoff বাড়াতে পারে না.

ggplot(coordination_nash, aes(Guard2, Guard1, fill = nash)) +
  geom_tile() +
  geom_text(aes(label = label), size = 6) +
  labs(
    title = "Nash equilibrium cells",
    subtitle = "A TRUE cell means both guards are simultaneously best-responding.",
    x = "Guard 2 chooses",
    y = "Guard 1 chooses",
    fill = "Nash?"
  )

7 Selfish behaviour may be collectively poor

Now think of two observatories. Each can either coordinate or act selfishly.

selfish_game <- expand.grid(
  Observatory1 = c("Coordinate", "Selfish"),
  Observatory2 = c("Coordinate", "Selfish"),
  stringsAsFactors = FALSE
)

selfish_game <- selfish_game %>%
  mutate(
    u1 = case_when(
      Observatory1 == "Coordinate" & Observatory2 == "Coordinate" ~ 6,
      Observatory1 == "Selfish" & Observatory2 == "Coordinate" ~ 8,
      Observatory1 == "Coordinate" & Observatory2 == "Selfish" ~ 1,
      Observatory1 == "Selfish" & Observatory2 == "Selfish" ~ 3
    ),
    u2 = case_when(
      Observatory1 == "Coordinate" & Observatory2 == "Coordinate" ~ 6,
      Observatory1 == "Selfish" & Observatory2 == "Coordinate" ~ 1,
      Observatory1 == "Coordinate" & Observatory2 == "Selfish" ~ 8,
      Observatory1 == "Selfish" & Observatory2 == "Selfish" ~ 3
    ),
    total = u1 + u2,
    label = paste0("(", u1, ", ", u2, ")")
  )

selfish_nash <- find_nash_2player(
  selfish_game,
  "Observatory1", "Observatory2", "u1", "u2"
)

selfish_nash %>%
  select(Observatory1, Observatory2, u1, u2, total, best_response_1, best_response_2, nash) %>%
  kable(caption = "A simple selfish-observatory game.")

A simple selfish-observatory game.
Observatory1	Observatory2	u1	u2	total	best_response_1	best_response_2	nash
Coordinate	Coordinate	6	6	12	FALSE	FALSE	FALSE
Selfish	Coordinate	8	1	9	TRUE	FALSE	FALSE
Coordinate	Selfish	1	8	9	FALSE	TRUE	FALSE
Selfish	Selfish	3	3	6	TRUE	TRUE	TRUE

ggplot(selfish_nash, aes(Observatory2, Observatory1, fill = total)) +
  geom_tile() +
  geom_text(aes(label = label), size = 6) +
  geom_point(
    data = selfish_nash %>% filter(nash),
    aes(Observatory2, Observatory1),
    inherit.aes = FALSE,
    shape = 21,
    size = 9,
    stroke = 1.4
  ) +
  labs(
    title = "Nash need not maximize total scientific value",
    subtitle = "The circled cell is Nash, but both coordinating has higher total payoff.",
    x = "Observatory 2",
    y = "Observatory 1",
    fill = "Total payoff"
  )

Teaching message:

Nash equilibrium alone is not enough. We need to design utilities so that local telescope incentives align with global scientific welfare.

8 Moving to gravitational-wave follow-up

In GW follow-up:

player \(k\): telescope/observatory \(k\);
strategy \(S_k\): telescope \(k\)’s feasible observation plan;
profile \(S=(S_1,\ldots,S_K)\);
aggregate schedule \(\bar S=\bigcup_k S_k\);
global welfare \(\Phi(\bar S)\).

The marginal-contribution utility is

\[ u_k(S_k,S_{-k}) = \Phi\left(\bigcup_{i=1}^K S_i\right) - \Phi\left(\bigcup_{i\neq k}S_i\right). \]

Meaning:

Telescope \(k\)’s utility is the extra scientific welfare added by telescope \(k\), after accounting for what the others already do.

Bengali-English:

Telescope \(k\) থাকলে total value কত, telescope \(k\) বাদ দিলে total value কত — differenceটাই telescope \(k\)-এর marginal contribution.

9 Detection objective

Let \(h\) be a sky pixel or campus region. Let \(\pi_h\) be the probability that the source/umbrella is in \(h\).

Let \(a\) be an observation/search action. Let \(q_{ah}\) be the conditional detection probability.

For a set of actions \(S\),

\[ F(S) = \sum_h \pi_h \left[ 1-\prod_{a\in S}(1-q_{ah}) \right]. \]

The cost-adjusted welfare is

\[ \Phi(S)=F(S)-C(S), \qquad C(S)=\sum_{a\in S}c_a. \]

Bengali-English:

\(F(S)\) হলো scientific detection value. \(C(S)\) হলো telescope time/resource cost. \(\Phi(S)\) হলো net welfare.

10 Toy telescope scheduling game

We now create a fully self-contained toy example.

regions <- data.frame(
  region = c("Library", "Canteen", "Auditorium", "Garden"),
  pi = c(0.45, 0.25, 0.20, 0.10),
  x = c(0.18, 0.78, 0.38, 0.82),
  y = c(0.82, 0.72, 0.28, 0.20)
)

players <- data.frame(
  player = c("Telescope_A", "Telescope_B", "Telescope_C"),
  effectiveness = c(0.70, 0.58, 0.50),
  cost = c(0.030, 0.025, 0.020)
)

kable(regions, caption = "Toy probability map.")

Toy probability map.
region	pi	x	y
Library	0.45	0.18	0.82
Canteen	0.25	0.78	0.72
Auditorium	0.20	0.38	0.28
Garden	0.10	0.82	0.20

kable(players, caption = "Toy telescope players.")

Toy telescope players.
player	effectiveness	cost
Telescope_A	0.70	0.030
Telescope_B	0.58	0.025
Telescope_C	0.50	0.020

ggplot(regions, aes(x, y)) +
  geom_point(aes(size = pi), alpha = 0.75) +
  geom_text(aes(label = paste0(region, "\n", pi)), nudge_y = 0.07, size = 4) +
  coord_equal(xlim = c(0, 1), ylim = c(0, 1)) +
  labs(
    title = "Toy campus/sky probability map",
    subtitle = "Point size represents posterior probability.",
    x = "Toy x",
    y = "Toy y",
    size = "Probability"
  )

11 Action library and \(q_{ah}\)

Each telescope chooses one region. If telescope \(k\) chooses region \(h\), then \(q_{ah}\) equals its effectiveness for that region; for other regions it is zero.

make_action_id <- function(player, choice) {
  paste(player, choice, sep = "__")
}

actions <- expand.grid(
  player = players$player,
  choice = regions$region,
  stringsAsFactors = FALSE
) %>%
  left_join(players, by = "player") %>%
  mutate(action = make_action_id(player, choice))

Q <- matrix(0, nrow = nrow(actions), ncol = nrow(regions))
rownames(Q) <- actions$action
colnames(Q) <- regions$region

for (i in seq_len(nrow(actions))) {
  Q[i, actions$choice[i]] <- actions$effectiveness[i]
}

actions %>%
  select(action, player, choice, effectiveness, cost) %>%
  kable(caption = "Toy action library.")

Toy action library.
action	player	choice	effectiveness	cost
Telescope_A__Library	Telescope_A	Library	0.70	0.030
Telescope_B__Library	Telescope_B	Library	0.58	0.025
Telescope_C__Library	Telescope_C	Library	0.50	0.020
Telescope_A__Canteen	Telescope_A	Canteen	0.70	0.030
Telescope_B__Canteen	Telescope_B	Canteen	0.58	0.025
Telescope_C__Canteen	Telescope_C	Canteen	0.50	0.020
Telescope_A__Auditorium	Telescope_A	Auditorium	0.70	0.030
Telescope_B__Auditorium	Telescope_B	Auditorium	0.58	0.025
Telescope_C__Auditorium	Telescope_C	Auditorium	0.50	0.020
Telescope_A__Garden	Telescope_A	Garden	0.70	0.030
Telescope_B__Garden	Telescope_B	Garden	0.58	0.025
Telescope_C__Garden	Telescope_C	Garden	0.50	0.020

12 Functions \(F(S)\), \(C(S)\), and \(\Phi(S)\)

F_value <- function(action_set, Q, pi_vec) {
  action_set <- unique(action_set)
  if (length(action_set) == 0) return(0)
  Qs <- Q[action_set, , drop = FALSE]
  detect_by_region <- 1 - apply(1 - Qs, 2, prod)
  sum(pi_vec * detect_by_region)
}

C_value <- function(action_set, actions) {
  action_set <- unique(action_set)
  if (length(action_set) == 0) return(0)
  sum(actions$cost[match(action_set, actions$action)])
}

Phi_value <- function(action_set, Q, pi_vec, actions) {
  F_value(action_set, Q, pi_vec) - C_value(action_set, actions)
}

13 Enumerating all profiles

There are \(4^3=64\) possible profiles.

choices <- regions$region

profiles <- expand.grid(
  Telescope_A = choices,
  Telescope_B = choices,
  Telescope_C = choices,
  stringsAsFactors = FALSE
)

profile_to_actions <- function(row) {
  c(
    make_action_id("Telescope_A", row[["Telescope_A"]]),
    make_action_id("Telescope_B", row[["Telescope_B"]]),
    make_action_id("Telescope_C", row[["Telescope_C"]])
  )
}

profiles$F <- apply(profiles, 1, function(z) {
  F_value(profile_to_actions(as.list(z)), Q, regions$pi)
})

profiles$Cost <- apply(profiles, 1, function(z) {
  C_value(profile_to_actions(as.list(z)), actions)
})

profiles$Phi <- profiles$F - profiles$Cost

profiles %>%
  arrange(desc(Phi)) %>%
  head(10) %>%
  round_df() %>%
  kable(caption = "Top 10 strategy profiles by net welfare.")

Top 10 strategy profiles by net welfare.
Telescope_A	Telescope_B	Telescope_C	F	Cost	Phi
Library	Canteen	Auditorium	0.5600	0.075	0.4850
Library	Auditorium	Canteen	0.5560	0.075	0.4810
Canteen	Library	Auditorium	0.5360	0.075	0.4610
Canteen	Library	Library	0.5305	0.075	0.4555
Library	Canteen	Library	0.5275	0.075	0.4525
Auditorium	Library	Canteen	0.5260	0.075	0.4510
Library	Library	Canteen	0.5183	0.075	0.4433
Canteen	Auditorium	Library	0.5160	0.075	0.4410
Library	Canteen	Canteen	0.5125	0.075	0.4375
Auditorium	Canteen	Library	0.5100	0.075	0.4350

ggplot(profiles, aes(Phi)) +
  geom_histogram(bins = 18, alpha = 0.8) +
  labs(
    title = "Distribution of net welfare over all strategy profiles",
    subtitle = "Even a small game has good and bad schedules.",
    x = "Net welfare Phi",
    y = "Number of profiles"
  )

14 Selfish local choice versus global best

A selfish telescope may maximize only its own local value:

\[ \pi_h\times\text{effectiveness}_k-c_k. \]

local_best <- actions %>%
  mutate(local_value = regions$pi[match(choice, regions$region)] * effectiveness - cost) %>%
  group_by(player) %>%
  slice_max(local_value, n = 1, with_ties = FALSE) %>%
  ungroup()

selfish_actions <- local_best$action

global_best <- profiles %>% arrange(desc(Phi)) %>% slice(1)
global_best_actions <- profile_to_actions(as.list(global_best[1, c("Telescope_A", "Telescope_B", "Telescope_C")]))

comparison <- data.frame(
  method = c("Selfish local choices", "Global best profile"),
  F = c(F_value(selfish_actions, Q, regions$pi), F_value(global_best_actions, Q, regions$pi)),
  Cost = c(C_value(selfish_actions, actions), C_value(global_best_actions, actions)),
  Phi = c(Phi_value(selfish_actions, Q, regions$pi, actions),
          Phi_value(global_best_actions, Q, regions$pi, actions)),
  choices = c(
    paste(actions$choice[match(selfish_actions, actions$action)], collapse = ", "),
    paste(actions$choice[match(global_best_actions, actions$action)], collapse = ", ")
  )
)

comparison %>%
  round_df() %>%
  kable(caption = "Selfish local choices versus global best profile.")

Selfish local choices versus global best profile.
method	F	Cost	Phi	choices
Selfish local choices	0.4216	0.075	0.3466	Library, Library, Library
Global best profile	0.5600	0.075	0.4850	Library, Canteen, Auditorium

comparison_long <- comparison %>%
  select(method, F, Phi) %>%
  pivot_longer(cols = c(F, Phi), names_to = "metric", values_to = "value")

ggplot(comparison_long, aes(method, value, fill = metric)) +
  geom_col(position = "dodge") +
  coord_flip() +
  labs(
    title = "Selfish local choice versus global best",
    subtitle = "Independent decisions may over-concentrate on the highest-probability region.",
    x = "Method",
    y = "Value",
    fill = "Metric"
  )

15 Potential game

A game is an exact potential game if there exists a potential function \(\Psi\) such that for every unilateral deviation,

\[ u_k(s_k',s_{-k})-u_k(s_k,s_{-k}) = \Psi(s_k',s_{-k})-\Psi(s_k,s_{-k}). \]

In the telescope game, we use

\[ \Psi(S_1,\ldots,S_K) = \Phi\left(\bigcup_{k=1}^K S_k\right). \]

Because the utility is marginal contribution, each telescope’s utility improvement equals the improvement of the global potential.

Bengali-English:

Local improvement আর global scientific improvement একই direction-এ যায়. এটাই potential game-এর beauty.

16 Best-response dynamics

Start from a duplicated schedule: all telescopes choose Library. Then let each telescope best-respond sequentially.

profile_actions <- function(choice_vec) {
  out <- character(0)
  for (nm in names(choice_vec)) {
    out <- c(out, make_action_id(nm, choice_vec[[nm]]))
  }
  out
}

utility_player <- function(choice_vec, player_name, Q, pi_vec, actions) {
  all_actions <- profile_actions(choice_vec)
  other_vec <- choice_vec[names(choice_vec) != player_name]
  other_actions <- profile_actions(other_vec)

  Phi_value(all_actions, Q, pi_vec, actions) -
    Phi_value(other_actions, Q, pi_vec, actions)
}

best_response_update <- function(choice_vec, player_name, choices, Q, pi_vec, actions) {
  vals <- data.frame(choice = choices, utility = NA_real_)

  for (i in seq_along(choices)) {
    cand <- choice_vec
    cand[[player_name]] <- choices[i]
    vals$utility[i] <- utility_player(cand, player_name, Q, pi_vec, actions)
  }

  choice_vec[[player_name]] <- vals$choice[which.max(vals$utility)]
  list(profile = choice_vec, table = vals)
}

run_best_response <- function(initial_profile, choices, Q, pi_vec, actions, max_rounds = 8) {
  current <- initial_profile
  hist <- data.frame(
    step = integer(),
    player = character(),
    Telescope_A = character(),
    Telescope_B = character(),
    Telescope_C = character(),
    Phi = numeric(),
    changed = logical(),
    stringsAsFactors = FALSE
  )

  step <- 0
  for (r in seq_len(max_rounds)) {
    any_changed <- FALSE

    for (p in names(current)) {
      old <- current[[p]]
      br <- best_response_update(current, p, choices, Q, pi_vec, actions)
      current <- br$profile
      changed <- old != current[[p]]
      if (changed) any_changed <- TRUE

      step <- step + 1
      hist <- rbind(
        hist,
        data.frame(
          step = step,
          player = p,
          Telescope_A = current[["Telescope_A"]],
          Telescope_B = current[["Telescope_B"]],
          Telescope_C = current[["Telescope_C"]],
          Phi = Phi_value(profile_actions(current), Q, pi_vec, actions),
          changed = changed,
          stringsAsFactors = FALSE
        )
      )
    }

    if (!any_changed) break
  }

  list(final_profile = current, history = hist)
}

initial_profile <- c(
  Telescope_A = "Library",
  Telescope_B = "Library",
  Telescope_C = "Library"
)

br_out <- run_best_response(
  initial_profile = initial_profile,
  choices = choices,
  Q = Q,
  pi_vec = regions$pi,
  actions = actions,
  max_rounds = 8
)

br_out$history %>%
  round_df() %>%
  kable(caption = "Best-response path from an initially duplicated profile.")

Best-response path from an initially duplicated profile.
step	player	Telescope_A	Telescope_B	Telescope_C	Phi	changed
1	Telescope_A	Canteen	Library	Library	0.4555	TRUE
2	Telescope_B	Canteen	Library	Library	0.4555	FALSE
3	Telescope_C	Canteen	Library	Auditorium	0.4610	TRUE
4	Telescope_A	Canteen	Library	Auditorium	0.4610	FALSE
5	Telescope_B	Canteen	Library	Auditorium	0.4610	FALSE
6	Telescope_C	Canteen	Library	Auditorium	0.4610	FALSE

ggplot(br_out$history, aes(step, Phi)) +
  geom_line(linewidth = 1) +
  geom_point(aes(shape = changed), size = 3) +
  labs(
    title = "Potential-game best-response dynamics",
    subtitle = "As telescopes best-respond, the global potential rises and stabilizes.",
    x = "Update step",
    y = "Global potential / net welfare Phi",
    shape = "Changed?"
  )

17 Equilibrium profile

final_profile_df <- data.frame(
  telescope = names(br_out$final_profile),
  final_choice = as.character(br_out$final_profile),
  action = profile_actions(br_out$final_profile)
)

final_actions <- final_profile_df$action

final_profile_df %>%
  kable(caption = "Final equilibrium profile.")

Final equilibrium profile.
telescope	final_choice	action
Telescope_A	Canteen	Telescope_A__Canteen
Telescope_B	Library	Telescope_B__Library
Telescope_C	Auditorium	Telescope_C__Auditorium

data.frame(
  expected_detection = F_value(final_actions, Q, regions$pi),
  cost = C_value(final_actions, actions),
  net_welfare = Phi_value(final_actions, Q, regions$pi, actions)
) %>%
  round_df() %>%
  kable(caption = "Scientific value of the final equilibrium profile.")

Scientific value of the final equilibrium profile.
expected_detection	cost	net_welfare
0.536	0.075	0.461

18 Centralized greedy warm start

If a global planner can choose at most \(B\) actions, it solves:

\[ \max_{S\subseteq\mathcal A,\ |S|\leq B} F(S). \]

Since \(F\) has diminishing returns, greedy is a strong reference.

centralized_greedy <- function(actions, Q, pi_vec, B = 3) {
  chosen <- character(0)
  hist <- data.frame(step = integer(), added = character(), F = numeric(), Phi = numeric())

  for (step in seq_len(B)) {
    current_F <- F_value(chosen, Q, pi_vec)
    best_gain <- -Inf
    best_a <- NA_character_

    for (a in actions$action) {
      if (a %in% chosen) next

      # One action per telescope in this toy example.
      candidate <- c(chosen, a)
      candidate_players <- actions$player[match(candidate, actions$action)]
      if (any(duplicated(candidate_players))) next

      gain <- F_value(candidate, Q, pi_vec) - current_F
      if (gain > best_gain) {
        best_gain <- gain
        best_a <- a
      }
    }

    if (is.na(best_a)) break
    chosen <- c(chosen, best_a)

    hist <- rbind(
      hist,
      data.frame(
        step = step,
        added = best_a,
        F = F_value(chosen, Q, pi_vec),
        Phi = Phi_value(chosen, Q, pi_vec, actions)
      )
    )
  }
  list(schedule = chosen, history = hist)
}

greedy_out <- centralized_greedy(actions, Q, regions$pi, B = 3)

greedy_out$history %>%
  round_df() %>%
  kable(caption = "Centralized greedy warm-start schedule.")

Centralized greedy warm-start schedule.
step	added	F	Phi
1	Telescope_A__Library	0.315	0.285
2	Telescope_B__Canteen	0.460	0.405
3	Telescope_C__Auditorium	0.560	0.485

ggplot(greedy_out$history, aes(step, Phi)) +
  geom_line(linewidth = 1) +
  geom_point(size = 3) +
  labs(
    title = "Centralized greedy warm start",
    subtitle = "Greedy adds the action with the largest current marginal gain.",
    x = "Greedy step",
    y = "Net welfare Phi"
  )

Bengali-English:

Greedy warm start একটি strong centralized reference. Decentralized game-এর performance এই reference-এর সঙ্গে compare করা যায়.

19 Scheduling and credit are different

Scheduling asks:

\[ \text{Which telescope observes which tile at which time?} \]

Credit asks:

\[ \text{After the campaign, how much did each telescope contribute?} \]

A telescope may be important because:

it acted early;
it covered a region others could not see;
it provided useful redundancy;
it avoided unnecessary duplication.

Raw participation is not equal to marginal scientific contribution.

20 Shapley value

Let \(v(T)\) be the value of a coalition \(T\) of telescopes. The Shapley value of telescope \(k\) is the average marginal contribution of \(k\) over all possible orders in which telescopes could join.

\[ \varphi_k(v) = \sum_{T\subseteq\mathcal K\setminus\{k\}} \frac{|T|!(K-|T|-1)!}{K!} \left[ v(T\cup\{k\})-v(T) \right]. \]

Bengali-English:

Telescope আগে join করলে contribution একরকম হতে পারে, পরে join করলে আরেকরকম. Shapley value সব possible joining order average করে fair credit দেয়.

all_permutations <- function(x) {
  if (length(x) == 1) return(list(x))
  out <- list()
  for (i in seq_along(x)) {
    rest <- x[-i]
    sub <- all_permutations(rest)
    for (s in sub) out[[length(out) + 1]] <- c(x[i], s)
  }
  out
}

realized_shapley <- function(profile_vec, Q, pi_vec, actions) {
  players <- names(profile_vec)
  perms <- all_permutations(players)
  credit <- setNames(rep(0, length(players)), players)

  for (perm in perms) {
    coalition_actions <- character(0)
    old_value <- Phi_value(coalition_actions, Q, pi_vec, actions)

    for (p in perm) {
      new_actions <- unique(c(coalition_actions, make_action_id(p, profile_vec[[p]])))
      new_value <- Phi_value(new_actions, Q, pi_vec, actions)
      credit[p] <- credit[p] + (new_value - old_value)
      coalition_actions <- new_actions
      old_value <- new_value
    }
  }

  credit / length(perms)
}

shap <- realized_shapley(br_out$final_profile, Q, regions$pi, actions)

shapley_table <- data.frame(
  telescope = names(shap),
  final_choice = as.character(br_out$final_profile[names(shap)]),
  shapley_credit = as.numeric(shap)
) %>%
  arrange(desc(shapley_credit))

shapley_table %>%
  round_df() %>%
  kable(caption = "Realized Shapley credit for the final equilibrium schedule.")

Realized Shapley credit for the final equilibrium schedule.
telescope	final_choice	shapley_credit
Telescope_B	Library	0.236
Telescope_A	Canteen	0.145
Telescope_C	Auditorium	0.080

ggplot(shapley_table, aes(reorder(telescope, shapley_credit), shapley_credit)) +
  geom_col() +
  coord_flip() +
  labs(
    title = "Shapley credit allocation",
    subtitle = "Credit is based on average marginal contribution, not mere participation.",
    x = "Telescope",
    y = "Shapley credit"
  )

21 Shapley properties

The Shapley value has three important fairness properties.

21.1 Efficiency

\[ \sum_{k\in\mathcal K}\varphi_k(v)=v(\mathcal K). \]

The total value is exactly distributed among players.

21.2 Symmetry

If two players always contribute identically, they receive equal credit.

21.3 Dummy property

If a player adds zero marginal value to every coalition, its Shapley value is zero.

Bengali-English:

Shapley value total value নষ্ট করে না, identical role হলে identical credit দেয়, আর zero contribution হলে zero credit দেয়.

22 Final conceptual bridge to GW follow-up

In the real gravitational-wave follow-up problem:

\[ F_e(S) = \sum_{h\in\mathcal H_e} \pi_{eh} \left[ 1-\prod_{a\in S}(1-q_{ah}) \right]. \]

Here:

\(\pi_{eh}\): posterior probability that event \(e\)’s source is in sky pixel \(h\);
\(q_{ah}\): probability that action \(a\) detects the electromagnetic counterpart if the source is in pixel \(h\);
\(S\): selected telescope–tile–time actions;
\(F_e(S)\): posterior-weighted detection value;
\(C(S)\): telescope-time/resource cost;
\(\Phi_e(S)=F_e(S)-C(S)\): net scientific welfare.

The game-theoretic scheduler uses

\[ u_k(S_k,S_{-k}) = \Phi_e\left(\bigcup_i S_i\right) - \Phi_e\left(\bigcup_{i\neq k}S_i\right). \]

That is:

each telescope receives utility equal to its exact marginal contribution to global welfare.

This creates an exact potential game with potential

\[ \Psi_e(S_1,\ldots,S_K) = \Phi_e\left(\bigcup_i S_i\right). \]

Therefore, unilateral improvements by telescopes correspond to improvements in global welfare.

23 Take-home message

The full philosophy is:

\[ \text{probability map} \rightarrow \text{scientific value} \rightarrow \text{resource allocation} \rightarrow \text{decentralized game} \rightarrow \text{fair credit}. \]

In one Bengali-English classroom sentence:

Greedy tells us where a central planner should search, potential games tell us how autonomous telescopes can coordinate, and Shapley value tells us how to fairly assign scientific credit after the campaign.

24 Exercises for students

Change Library probability from \(0.45\) to \(0.60\). Does duplication become more attractive?
Increase the cost of Telescope A. Does it still receive high Shapley credit?
Add a fourth telescope. How does the best-response path change?
Add a fifth region with small probability. Does greedy ever select it?
Change telescope effectiveness values. Which telescope becomes most important?
Compare selfish local choice and potential-game equilibrium.
Explain why scheduling and credit allocation are different questions.
Explain the umbrella analogy in your own words.

From Simple Game Theory to Decentralized GW Follow-up Scheduling

Standalone RPubs teaching note with Bengali-English motivation, toy simulations, and plots

Debashis Chatterjee

09 July 2026

1 Purpose

2 Motivating story: the lost umbrella

3 What is a game?

4 A first game: two-guard coordination

5 Best response

6 Nash equilibrium

7 Selfish behaviour may be collectively poor

8 Moving to gravitational-wave follow-up

9 Detection objective

10 Toy telescope scheduling game

11 Action library and \(q_{ah}\)

12 Functions \(F(S)\), \(C(S)\), and \(\Phi(S)\)

13 Enumerating all profiles

14 Selfish local choice versus global best

15 Potential game

16 Best-response dynamics

17 Equilibrium profile

18 Centralized greedy warm start

19 Scheduling and credit are different

20 Shapley value

21 Shapley properties

21.1 Efficiency

21.2 Symmetry

21.3 Dummy property

22 Final conceptual bridge to GW follow-up

23 Take-home message

24 Exercises for students