# Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous
Hedonic Games

Andrei Constantinescu  ETH Zürich, Zürich, Switzerland<EMAIL_ADDRESS>Pascal Lenzner  Hasso Plattner Institute, Potsdam, Germany,
<EMAIL_ADDRESS>Rebecca Reiffenhäuser  University of Amsterdam,
Amsterdam, The Netherlands<EMAIL_ADDRESS>Daniel Schmand
University of Bremen, Bremen, Germany<EMAIL_ADDRESS>Giovanna
Varricchio  University of Calabria, Rende, Italy,
<EMAIL_ADDRESS>
###### Abstract

A decade ago, Gerhard Woeginger posed an open problem that became well-known
as “Gerhard’s Hiking Problem”: Consider a group of $n$ people that want to go
hiking; everyone expresses preferences over the size of their hiking group in
the form of an interval between $1$ and $n$. Is it possible to efficiently
assign the $n$ people to a set of hiking subgroups so that every person
approves the size of their assigned subgroup? The problem is also known as
efficiently deciding if an instance of an anonymous Hedonic Game with interval
approval preferences admits a wonderful partition.

We resolve the open problem in the affirmative by presenting an $O(n^{5})$
time algorithm for Gerhard’s Hiking Problem. Our solution is based on
employing a dynamic programming approach for a specific rectangle stabbing
problem from computational geometry. Moreover, we propose natural more
demanding extensions of the problem, e.g., maximizing the number of satisfied
people, and show that they are also efficiently solvable. Additionally, we
precisely map the boundary of tractability for the wonderful partition problem
by proving that finding such a partition becomes NP-hard if non-interval
approval size sets of size two are allowed. This closes a gap in the
complexity landscape, since hardness was only known for the case with non-
interval approval size sets of size at most 3. Last but not least, we employ
our solution to efficiently compute a partition that maximizes the egalitarian
welfare for anonymous single-peaked Hedonic Games.

##  1 Introduction

Suppose there are $n$ attendees of a workshop, who aim to go for a joint hike
during a break. Keeping the whole group together is logistically challenging,
so typically the attendees split into smaller subgroups that will do the hike
together, separately from the others. It is natural that different attendees
might have different preferences for the sizes of the subgroups they will
eventually join. In particular, each attendee $i$ reports an interval
$[\ell_{i},r_{i}]$ signifying that they will be content if they are in a group
of size $s\in[\ell_{i},r_{i}]$. The organizers of the hike now face the
following problem: Is there a polynomial time algorithm that determines
whether there is a partition of the attendees into subgroups such that they
are all content with the sizes of their subgroups?

Figure 1: Gerhard Woeginger, Oberwolfach, 2011. [19]

In 2013, Gerhard Woeginger famously phrased this problem to explain an open
problem stemming from his work on anonymous Hedonic Games [20]. It is one of
the very nice problems that Gerhard used to explain during various occurrences
such as a small break at the coffee machine, while waiting in a seminar room,
or even during a joint walk.111Gerhard’s way of explaining open research
questions in an easily accessible way has been extraordinarily motivating. In
particular, this work would not have started without Gerhard meeting the
fourth author at the RWTH Aachen University canteen and explaining the problem
exactly in this way. We hope with this work to also contribute to the recent
line of publications celebrating the life and work of Gerhard Woeginger, see
[16]. As this is one of the problem he explained to many people, it became
known as Gerhard’s _Hiking Problem_.

In this work we answer Woeginger’s question in the affirmative by exploiting a
tight connection to a variant of the rectangle stabbing problem from
computational geometry that can be solved in polynomial time via elegant
dynamic programming.

Using Woeginger’s motivation of the problem, many natural extensions arise
that we introduce in this paper. If the sought partition does not exist, then
what is the maximum number of attendees that can be satisfied with their group
sizes, or what is the minimum number of attendees to exclude such that the
remaining ones can be partitioned to all become satisfied? Note that these two
questions are subtly not the same. We show that these more demanding problems
can also be solved efficiently.

Complementing our positive results, we also consider the case where the
approved group sizes do not form intervals. For this, it was already known
that the problem is NP-hard even if each attendee has at most three different
approved group sizes that need not form an interval. The case where every
person only approves of one group size is a special case of our interval
setting, and hence can be solved in polynomial time.222It also admits a direct
algorithm: check whether for all $i$ the number of agents approving only of
size $i$ is divisible by $i.$ This leaves a gap in the complexity landscape
for the case where each attendee has at most two approved group sizes that do
not form an interval. We close this gap by showing that the latter problem is
in fact NP-hard, i.e. even if every attendee has exactly two approved group
sizes.

Finally, we discuss the relationship between the hiking problem and the
problem of maximizing the egalitarian welfare in (general) anonymous Hedonic
Games. We show that the two problems are polynomial time equivalent: It is
possible to reduce each one to the other in poly-time via a Turing reduction.
Moreover, in the case where the preferences of the agents in the anonymous
Hedonic Game instance are single-peaked, we prove that computing a maximum
egalitarian welfare partition is possible in polynomial time.

##  2 Related Work

_Hedonic Games_ (HGs), introduced by Dreze and Greenberg in [10], model multi-
agent systems where selfish agents have to be split into coalitions and have
preferences over the possible outcomes. Such games are said to be hedonic as
agents’ preferences only depend on the coalition they belong to, and not on
how the other agents are grouped. Hedonic Games have been widely studied (see
[5] for a survey) and numerous prominent subclasses have been identified based
on properties of agents’ preferences or other possible constraints: [6, 8, 1,
17, 11, 2]. Simple examples of such classes are anonymous HGs [7], where the
preferences of the agents depend only on the size of their coalition and not
on who are the participants, or HGs with approval-based (Boolean) preferences
[4], where agents have binary values for the coalitions. Gerhard’s Hiking
Problem resides in the intersection of these classes.

The HGs literature has typically focused on the existence and computation of
stable or optimal solution concepts, see, e.g., [8]. The most desirable, ideal
partition is the one where every agent is assigned to one of her best
coalitions – the so-called perfect (or wonderfully stable) partition [3].
Unfortunately, such a solution rarely exists and the related decision or
computation problem is usually hard [3, 18]. Even in simple cases such as for
anonymous approval-based HGs, it is NP-complete to determine the existence of
a perfect partition [9, 20]. Such a result holds true even if the number of
approved coalition sizes of each agent is at most $3$.333This can be deduced
from the proof of Theorem 5.2 in [20] and the fact that  E X A C T C O V E R B
Y 3 - S E T S is NP-hard even if each element of the ground set occurs in at
most $3$ triples [14]. For a formal definition of  E X A C T C O V E R B Y 3 -
S E T S we refer to Section 5.

In our paper, we show the tractability of computing a perfect partition for
instances with interval approvals as formulated by Woeginger [20]. To this
aim, we provide a simple dynamic program that relies on the approach used in
[12] to solve a capacitated rectangle stabbing problem from computational
geometry. Here, the goal is to cover a set of rectangles with a minimum subset
of a given set of lines, each intersecting (i.e., potentially _covering_) some
of the rectangles. Each line has a maximum number of rectangles it can cover,
and to cover all rectangles, one is allowed to use multiple copies of each
line.

##  3 Preliminaries

The hiking problem as formulated by Gerhard Woeginger is a special case of
anonymous Hedonic Games with approval-based preferences.

In an anonymous hedonic game with approval-based preferences we are given a
set $N$ of $n$ agents to be partitioned into coalitions. Each agent $i\in N$
reports an approval set $S_{i}\subseteq[n]$ representing the approved group
sizes for agent $i$. In particular, agent $i$ wants to be in some group of
size $s$ such that $s\in S_{i}.$ An approval set $S_{i}$ is said to be an
_interval_ if $S_{i}=\\{\ell_{i},\ell_{i}+1,\dots,r_{i}\\}$ for some
$1\leq\ell_{i}\leq r_{i}\leq n$. The agents have to be split into coalitions,
i.e., subsets of the agent set. This induces a _partition_ $\pi$ of the set of
agents $N$. We denote by $\pi(i)$ the coalition agent $i$ belongs to in the
partition $\pi$. We follow the notation in Woeginger’s survey paper [20] and
call a partition $\pi$ _wonderful_ if each agent approves of the size of their
coalition in $\pi$, i.e., for each agent $i$, $|\pi(i)|\in S_{i}$. This leads
to the following natural computational problem:

W O N D E R F U L - P A R T I T I O N Input: A set $N$ of agents and size
approval sets $(S_{i})_{i\in N}.$ Problem: Decide whether there exists a
wonderful partition of the agents. If yes, compute one.

Gerhard’s Hiking Problem is  W O N D E R F U L - P A R T I T I O N for the
case of interval approval sets:

W O N D E R F U L - P A R T I T I O N - I N T E R V A L S (  H I K I N G )
Input: A set $N$ of agents and for each agent $i\in N$ two numbers
$\ell_{i}\leq r_{i}$ such that $S_{i}=\\{\ell_{i},\ldots,r_{i}\\}.$ Problem:
Decide whether there exists a wonderful partition of the agents. If yes,
compute one.

In our paper, we also consider natural extensions of the hiking problem, to be
introduced later.

##  4 Efficiently Solving Gerhard’s Hiking Problem and Extensions

In this section, we prove that  W O N D E R F U L - P A R T I T I O N - I N T
E R V A L S can be solved in polynomial time by casting the problem as a
version of capacitated rectangle stabbing, which can be efficiently solved via
an elegant dynamic programming approach introduced by Even, Levi, Rawitz,
Schieber, Shahar, and Srividenko [12]. Note that this reduction from our
partition problem to a version of rectangle stabbing draws a powerful new
connection between the problem types that is not limited to our specific
problem version, but is possible in more generality; e.g., it can be adapted
to the variant where there can be at most one group of each size. We use the
central observations of their work to derive a tailored dynamic programming
solution to  W O N D E R F U L - P A R T I T I O N - I N T E R V A L S , the
definition and analysis of which will then also power our results on the more
demanding problem variants discussed in the introduction.

###  4.1 Dynamic Programming for Gerhard’s Hiking Problem

Consider an instance of  W O N D E R F U L - P A R T I T I O N - I N T E R V A
L S , i.e., a set $N$ consisting of $n$ agents, without loss of generality
$N=[n]$, and $n$ pairs $(\ell_{i},r_{i})_{i\in N}$ such that agent $i\in[n]$
approves of sizes $S_{i}=\\{\ell_{i},\ldots,r_{i}\\}$. We are interested in
checking whether there exists a wonderful partition of the agents; i.e., one
where every agent approves of their coalition size. For consistent tie-
breaking reasons, throughout this section we write $i\prec j$ for two distinct
agents $i,j\in[n]$ if either $r_{i}<r_{j},$ or $r_{i}=r_{j}$ and $i<j.$ Note
that $\prec$ is a well-defined strict linear order and, without loss of
generality, assume that agents are ordered so that $1\prec\ldots\prec n.$

As the main technical ingredient of our approach, given a subset
$N^{\prime}\subseteq N$ of agents, we say that a wonderful partition $\pi$ of
$N^{\prime}$ is _earliest-due-date_ if for any two agents $i\prec j$ it does
not hold that $\ell_{i}\leq|\pi(j)|<|\pi(i)|.$ This terminology is borrowed
from the scheduling literature, and based on the following well-known
observation: let us view the agents’ allowed intervals of coalition sizes on
an axis labeled with the natural numbers $1,\ldots,n$, and consider an
arbitrary collection of coalition sizes we might decide on using, in non-
decreasing order of coalition size. Then, going in this order, it is always
safe to include those agents first whose right interval endpoints are the
smallest: in said order of coalitions, they are the ones that stop being
servable first, making an earliest-due-date approach impose the least
restrictions on later assignments. In other words, whenever a wonderful
partition into the given coalition sizes exists, there also exists one that is
earliest-due-date. We prove this formally below for completeness. Note that,
to make the process well-defined, instead of comparing agents by right
endpoints, we compare them by $\prec$.

######  Lemma 1.

If a subset $N^{\prime}\subseteq N$ of agents admits a wonderful partition,
then it admits an earliest-due-date wonderful partition.

###### Proof.

Consider a wonderful partition $\pi$ of $N^{\prime}.$ If it satisfies the
required property, then we are done, otherwise, consider $i,j\in N^{\prime}$
such that $i\prec j$ and $\ell_{i}\leq|\pi(j)|<|\pi(i)|.$ These conditions
imply that $|\pi(j)|\in[\ell_{i},r_{i}]$ and $|\pi(i)|\in[\ell_{j},r_{j}].$
Hence, one can construct a new wonderful partition $\pi^{\prime}$ from $\pi$
by exchanging the groups of agents $i$ and $j$; i.e.,
$\pi^{\prime}(i)=(\pi(j)\setminus\\{j\\})\cup\\{i\\}$ and
$\pi^{\prime}(j)=(\pi(i)\setminus\\{i\\})\cup\\{j\\}.$ Subsequently, set
$\pi\leftarrow\pi^{\prime}$ and repeat the same procedure until the required
condition is satisfied. To complete the proof, we need to show that this is
eventually the case. To do so, since $1\prec\ldots\prec n,$ each exchange
strictly increases the sequence $(|\pi(n)|,\ldots,|\pi(1)|)$
lexicographically. Because this sequence is bounded from above by
$(n,\ldots,n),$ the process eventually ends. ∎

Hence, from now on, we will only seek earliest-due-date wonderful partitions.
This crucial restriction, which we have shown to be without loss of
generality, will allow us to ultimately bootstrap a dynamic programming
algorithm that determines a wonderful partition if one exists.

To construct our algorithm, we first show that earliest-due-date partitions
admit an attractive recursive decomposition. Consider an earliest-due-date
wonderful partition $\pi$ of the agents (if any exist), and consider the size
of the coalition that agent $n$ is a part of; i.e., $|\pi(n)|.$ Moreover,
consider an arbitrary agent $i\neq n.$ Agent $i$ is part of a coalition of
size $|\pi(i)|.$ Because $\pi$ is earliest-due-date, by definition it can not
be the case that $\ell_{i}\leq|\pi(n)|<|\pi(i)|,$ so either
$|\pi(n)|<\ell_{i}$ or $|\pi(i)|\leq|\pi(n)|$ holds.

######  Lemma 2.

Consider an earliest-due-date wonderful partition $\pi$ of $N.$ Partition the
agents as $N=N_{-}\cup N_{+}\cup\\{n\\},$ where $N_{-}=\\{i\in
N\setminus\\{n\\}\mid\ell_{i}\leq|\pi(n)|\\}$ and $N_{+}=\\{i\in
N\setminus\\{n\\}\mid\ell_{i}>|\pi(n)|\\},$ then it holds that:

  1. 1.

For all $i\in N_{-}$ we have $|\pi(i)|\leq|\pi(n)|$;

  2. 2.

For all $i\in N_{+}$ we have $|\pi(i)|>|\pi(n)|.$

###### Proof.

For (2) note that any $i\in N_{+}$ by definition satisfies
$\ell_{i}>|\pi(n)|.$ Since we have the requirement that
$|\pi(i)|\in[\ell_{i},r_{i}],$ this means that
$|\pi(i)|\geq\ell_{i}>|\pi(n)|,$ as desired.

For (1), consider some $i\in N_{-}.$ By definition, we have that
$\ell_{i}\leq|\pi(n)|.$ Assume for a contradiction that $|\pi(i)|>|\pi(n)|.$
This implies that $\ell_{i}\leq|\pi(n)|<|\pi(i)|.$ Since $r_{i}\leq r_{n}$ and
by the sorting criterion we also have $i\prec n$, this contradicts that $\pi$
is earliest-due-date. ∎

Notably, the same result holds true if we work with a subset of the agents
$N^{\prime}\subsetneq N$ and $n$ is replaced with the agent $a\in N^{\prime}$
with maximum $r_{a}.$

Armed as such, to build intuition, Lemma 2 tells us that no two agents
$a_{-}\in N_{-}$ and $a_{+}\in N_{+}$ can go into the same group, so a first
attempt at a recursive algorithm looking for a wonderful partition of $N,$ to
be later optimized by memorization/dynamic programming, would proceed as
follows: start with $N^{\prime}=N$; at each step, identify the agent $a\in
N^{\prime}$ maximizing $r_{a}$ and exhaust over all possibilities for
$|\pi(a)|$; for each one, write $N^{\prime}=N^{\prime}_{-}\cup
N^{\prime}_{+}\cup\\{a\\}$ as defined in Lemma 2 and recurse with
$N^{\prime}_{-}$ and $N^{\prime}_{+}$. We will specify the details of the
process such that, if the recursive calls yield wonderful partitions of
$N^{\prime}_{-}$ and $N^{\prime}_{+}$, a wonderful partition of $N$ can also
be constructed by incorporating agent $a$ into them. Of course, the last step
of reasoning is incorrect, since one needs to make sure that a group of size
$|\pi(a)|$ with one space available indeed exists, and this information needs
to be somehow propagated across recursive calls. Moreover, it is unclear what
the number of sets $N^{\prime}$ reachable by the recursion is. This has to be
polynomially bounded so that memorization/dynamic programming leads to a
polynomial-time algorithm.

Let us first address the second issue outlined above, namely the size of the
state space. This turns out to be relatively simple: define
$N(x_{1},x_{2},i)=\\{j\in N\mid j\leq i\text{ and
}\ell_{j}\in[x_{1},x_{2}]\\}.$ Then, we can adapt the recursive approach:
instead of storing $N^{\prime}$ explicitly, start with $x_{1}=1$ and
$x_{2}=n$, as well as $i=n,$ from which implicitly
$N^{\prime}=N(x_{1},x_{2},i)$. At each step we will first check whether $i$,
which by the sorting criterion is the largest agent maximizing $r_{i}$, is in
$N^{\prime}=N(x_{1},x_{2},i)$; i.e., whether $\ell_{i}\in[x_{1},x_{2}].$ If
not, then $N(x_{1},x_{2},i)=N(x_{1},x_{2},i-1)$ and we simply recurse with the
same $x_{1},x_{2}$ and $i^{\prime}=i-1.$ Otherwise, $i$ is the largest agent
in $N^{\prime}$ maximizing $r_{i}$, so we can exhaust as before over all
possible values for $|\pi(i)|$ and perform two recursive calls in each case:
one with $(x_{1}^{\prime},x_{2}^{\prime},i^{\prime})=(x_{1},|\pi(i)|,i-1)$ and
one with $(x_{1}^{\prime},x_{2}^{\prime},i^{\prime})=(|\pi(i)|+1,x_{2},i-1)$.
We have yet to solve the correctness issue, but we have made progress: the
state space now consists of triples $(x_{1},x_{2},i)$ such that $1\leq
x_{1}\leq x_{2}\leq n$ and $1\leq i\leq n,$ which there are $O(n^{3})$ of.

Let us now turn our attention to ensuring correctness. To do so, we need to
investigate more closely how to ensure that the group of size $|\pi(i)|$ of
agent $i$ (recall that we only exhaust over its size, not over which agents
are in it) exists and is used to its full capacity in the solution constructed
by the recursion. There is one crucial guarantee given by Lemma 2 that we have
so far not exploited. Namely, the recursive call with $(x_{1},|\pi(i)|,i-1)$
should only use groups of sizes $s\in[x_{1},|\pi(i)|]$ and the one with
$(x_{1}^{\prime},x_{2}^{\prime},i^{\prime})=(|\pi(i)|+1,x_{2},i-1)$ should
only use groups of sizes $s\in[|\pi(i)|+1,x_{2}].$ In general, state
$(x_{1},x_{2},i)$ should only consider groups of sizes $s\in[x_{1},x_{2}].$
This can be ensured by requiring that the exhausted value for $|\pi(i)|$
additionally satisfies $x_{1}\leq|\pi(i)|\leq x_{2}.$ This small, seemingly
inconsequential, refinement of the approach will ultimately allow us to
propagate information about incomplete groups across states in the recursion.
Before describing how this is done in general, to build more intuition, let us
consider the first level of the recursion, namely $(x_{1},x_{2},i)=(1,n,n).$
At this level, the algorithm exhausts over the possible values for
$|\pi(n)|\in[\ell_{n},r_{n}].$ For each possibility, in the ensuing recursive
call with $(x_{1}^{\prime},x_{2}^{\prime},i^{\prime})=(|\pi(n)|+1,n,n-1)$ all
used groups will be of size at least $|\pi(n)|+1>|\pi(n)|$ so nothing special
needs to be done in this case since those agents can not be part of agent
$n$’s group. However, in the other call, having
$(x_{1}^{\prime},x_{2}^{\prime},i^{\prime})=(1,|\pi(n)|,n-1)$ some
$|\pi(n)|-1$ other agents will need to share a group of size $|\pi(n)|$ with
agent $n,$ and this is not yet modeled by our approach. To model this effect
across recursive calls, we introduce a fourth variable $0\leq k<x_{2}$ to the
state of our recursive algorithm; i.e., each state is now of the form
$(x_{1},x_{2},i,k).$ This variable intuitively signifies that there exists
(from upward in the recursion) an incomplete group, currently of size $k,$
whose final size should be $x_{2}.$ With this setup, the starting top-level
call will now be with $(x_{1},x_{2},i,k)=(1,n,n,0).$ For each value of
$|\pi(n)|,$ the two resultant recursive calls will be with
$(x_{1}^{\prime},x_{2}^{\prime},i^{\prime},k^{\prime})=(1,|\pi(n)|,n-1,1)$444Strictly
speaking, this should be
$(x_{1}^{\prime},x_{2}^{\prime},i^{\prime},k^{\prime})=(1,|\pi(n)|,n-1,1\
\mathrm{mod}\ |\pi(n)|)$. We omit this detail from the higher-level exposition
to improve readability. and
$(x_{1}^{\prime},x_{2}^{\prime},i^{\prime},k^{\prime})=(|\pi(n)|+1,n,n-1,0).$
Note how the former call has $k^{\prime}=1$, signifying that we just “opened a
new (incomplete) group of size one, whose final size should be
$x_{2}^{\prime}=|\pi(n)|$” The fundamental reason why such an approach can
work is that in any node of the recursion tree, there is at most a single
incomplete group to keep track of. Note that this fact crucially depends on
each call $(x_{1},x_{2},i,k)$ only considering partitions into groups of sizes
between $x_{1}$ and $x_{2}.$ We still need to describe what the transitions
are for general calls $(x_{1},x_{2},i,k)$ given the newly added parameter $k$.
We leave the details for the formal version following below, but in rough
lines, the call for $N_{-}$ creates a new group; i.e., $k^{\prime}=1$; while
the call for $N_{+}$ keeps the currently open one; i.e., $k^{\prime}=k$; the
exception comes when $|\pi(i)|=x_{2},$ in which case the call for $N_{-}$ adds
to the same group, possibly closing the group; i.e.,
$k^{\prime}=(k+1)\pmod{x_{2}}$; and no call for $N_{+}$ is generated.

######  Theorem 3.

Deciding whether a wonderful partition exists and computing one if so can be
achieved in $O(n^{5})$ time.

###### Proof.

We show how to solve the decision version, constructing a wonderful partition
for yes-instances can be subsequently achieved by standard techniques. We
proceed by dynamic programming (DP). Define the Boolean DP array
$\mathit{dp}[x_{1},x_{2},i,k]$ for $1\leq x_{1}\leq x_{2}\leq n,$ $0\leq i\leq
n$ and $0\leq k<x_{2},$ with the meaning $\mathit{dp}[x_{1},x_{2},i,k]=1$ if
and only if there exists a wonderful partition of agents in $N(x_{1},x_{2},i)$
using only groups of sizes in $[x_{1},x_{2}]$ and assuming that we start with
an incomplete group of current size $k$ which has to have final size $x_{2}.$
Naturally, if $k=0$ this means starting with no partially filled group. The
final answer will be available at the end in $\mathit{dp}[1,n,n,0].$ To
compute the DP table, we use the following recurrence relations and base cases
(using a hyphen as stand-in for any group size):

  1. 1.

$\mathit{dp}[-,-,0,0]=1$;

  2. 2.

$\mathit{dp}[-,-,0,k]=0$ if $k\neq 0$;

  3. 3.

$\mathit{dp}[x_{1},x_{2},i,k]=\mathit{dp}[x_{1},x_{2},i-1,k]$ if
$\ell_{i}\notin[x_{1},x_{2}]$;

  4. 4.

$\mathit{dp}[x_{1},x_{2},i,k]=\bigvee_{x=\ell_{i}}^{\min(x_{2},r_{i})}F_{x}$
if $\ell_{i}\in[x_{1},x_{2}],$ where

$F_{x}:=\left\\{\begin{array}[]{ll}\mathit{dp}[x_{1},x_{2},i-1,(k+1)\
\mathrm{mod}\ x_{2}]&x=x_{2}\\\ \mathit{dp}[x_{1},x,i-1,1\ \mathrm{mod}\
x]\land\mathit{dp}[x+1,x_{2},i-1,k]&x<x_{2}.\\\ \end{array}\right.$

The first three cases are immediate from the definition of the DP. For the
last case, we iterate over $x\in[\ell_{i},\max(x_{2},r_{i})]$ which is the
size of the group that agent $i$ goes into. There are two cases: if $x=x_{2},$
then we put $i$ into the group of current size $k$ and final size $x_{2}$ that
we assumed to have at our disposal; this increases the size of the group by
one, or completes it if $k=x_{2}-1$; otherwise, $x<x_{2},$ and we recurse into
partitioning agents in $N(x_{1},x,i-1)$ into groups of sizes between $x_{1}$
and $x,$ and $N(x+1,x_{2},i-1)$ into groups of sizes between $x+1$ and
$x_{2}.$ For the first call, this generates a new group of size $1$ (unless
$x=1$), while for the latter, this keeps the previously open group of current
size $k$ and final size $x_{2}$ that we assumed to have.

To compute the DP table in an acyclic fashion, it suffices to iterate through
$i$ in ascending order. The complexity of the approach is $O(n^{5})$ because
there are $O(n^{4})$ states and computing the value for states of type (4)
requires iterating through $O(n)$ values of $x.$ ∎

###  4.2 Extensions

Using a similar dynamic programming approach, we can solve the following
natural extension of the hiking problem:

H I K I N G - M I N - D E L E T E Input: A set $N$ of agents and for each
agent $i\in N$ two numbers $\ell_{i}\leq r_{i}$ such that
$S_{i}=\\{\ell_{i},\ldots,r_{i}\\}.$ Problem: Compute a set
$N^{\prime}\subseteq N$ of minimum size such that $N\setminus N^{\prime}$ has
a wonderful partition. Output $N^{\prime}$ and a wonderful partition of
$N\setminus N^{\prime}.$

The approach relies on essentially the same recursive reasoning as before,
except that we now also consider the possibility of “ignoring” an agent $i$
and hence recursing with
$(x_{1}^{\prime},x_{2}^{\prime},i^{\prime},k^{\prime})=(x_{1},x_{2},i-1,k).$
Moreover, instead of making the recursion return whether a wonderful partition
is possible or not, we make it return the minimum number of agents that need
to be removed so that this is possible. In light of this, the “ignore $i$”
recursive call incurs a cost of 1 removed agent. The details are formalized in
the following.

######  Theorem 4.

H

I

K

I

N

G

-

M

I

N

-

D

E

L

E

T

E

is solvable in $O(n^{5})$ time.

###### Proof.

Our approach will be along the same lines as the one used to prove Theorem 3.
As before, it suffices to show how to compute the minimum size of
$N^{\prime},$ as computing such a set $N^{\prime}$ and a corresponding
wonderful partition for $N\setminus N^{\prime}$ follow by standard techniques.
Define the integer-valued DP array $\mathit{dp}[x_{1},x_{2},i,k]$ for $1\leq
x_{1}\leq x_{2}\leq n,$ $0\leq i\leq n$ and $0\leq k<x_{2},$ with the meaning
that $\mathit{dp}[x_{1},x_{2},i,k]$ contains the minimum number of agents
which need to be removed from $N(x_{1},x_{2},i)$ so that the remaining agents
admit a wonderful partition into groups of sizes in $[x_{1},x_{2}]$ assuming
that we start with an incomplete group of current size $k$ which has to have
final size $x_{2}.$ Note that, in contrast to the previous DP, the value 0
corresponds to removing no agents, which is the best possible outcome, while
previously it corresponded to the need for removing at least one agent. The
final answer will be available at the end in $\mathit{dp}[1,n,n,0].$ To
compute the DP table, we use the following recurrence relations and base
cases:

  1. 1.

$\mathit{dp}[-,-,0,0]=0$;

  2. 2.

$\mathit{dp}[-,-,0,k]=\infty$ if $k\neq 0$;

  3. 3.

$\mathit{dp}[x_{1},x_{2},i,k]=\mathit{dp}[x_{1},x_{2},i-1,k]$ if
$\ell_{i}\notin[x_{1},x_{2}]$;

  4. 4.

$\mathit{dp}[x_{1},x_{2},i,k]=\min\\{1+\mathit{dp}[x_{1},x_{2},i-1,k],X\\}$ if
$\ell_{i}\in[x_{1},x_{2}]$, where $X:=\min\\{F_{x}\mid\ell_{i}\leq
x\leq\min(x_{2},r_{i})\\}$ and

$F_{x}:=\left\\{\begin{array}[]{ll}\mathit{dp}[x_{1},x_{2},i-1,(k+1)\
\mathrm{mod}\ x_{2}]&x=x_{2}\\\ \mathit{dp}[x_{1},x,i-1,1\ \mathrm{mod}\
x]+\mathit{dp}[x+1,x_{2},i-1,k]&x<x_{2}.\\\ \end{array}\right.$

The reasoning stays largely the same as before, with the only real difference
being the new $1+\mathit{dp}[x_{1},x_{2},i-1,k]$ term, which accounts for
discarding agent $i,$ incurring a cost of 1 corresponding to removing an
agent. ∎

Another similar, yet subtly distinct, natural variant of Gerhard’s Hiking
Problem is the following:

H I K I N G - M A X - S A T I S F I E D Input: A set $N$ of agents and for
each agent $i\in N$ two numbers $\ell_{i}\leq r_{i}$ such that
$S_{i}=\\{\ell_{i},\ldots,r_{i}\\}.$ Problem: Compute a partition $\pi$ of $N$
maximizing the number of agents approving of their coalition sizes.

Indeed,  H I K I N G - M A X - S A T I S F I E D and  H I K I N G - M I N - D
E L E T E are related, in that if $N^{\prime}$ is a minimum-size set of agents
such that $N\setminus N^{\prime}$ has a wonderful partition, then it is also
possible to satisfy at least $n-|N^{\prime}|$ agents in a partition of $N.$
This is because agents in $N^{\prime}$ can be put together in a group in
tandem to a wonderful partition of $N\setminus N^{\prime}$ to get a partition
of $N$ with at least $n-|N^{\prime}|$ satisfied agents. However, it might be
possible to satisfy more than $n-|N^{\prime}|$ agents if unsatisfied agents do
not all go into the same group.

Hence, solving this variant of the problem introduces new challenges that
require further insight. Let us fix a number $k$ and ask whether it is
possible to satisfy at least $|N|-k$ agents. If the answer is affirmative, we
also want a partition achieving this. To solve  H I K I N G - M A X - S A T I
S F I E D , we will binary search for the smallest $0\leq k\leq|N|$ for which
the answer is affirmative, call it $k^{*}$, and then recover a partition for
$k^{*}.$ It remains to show how to solve the problem for a fixed value of $k.$
To do so, we need to adjust the angle from which we look at the problem. In
particular, instead of looking for a partition satisfying at least $k$ agents,
we will look for a size-$k$ subset $N^{\prime}\subseteq N$ (corresponding to
$k$ agents which we do not require to be satisfied) such that $(N\setminus
N^{\prime})\cup D_{k}$ admits a wonderful partition, where $D_{k}$ is a set of
$k$ dummy agents happy with any group size. Intuitively, $k$ agents are
replaced with dummies not minding their group size. Because it is always no
worse to remove agents from $N$ in contrast to removing agents from $D_{k},$
it is enough to ask to remove exactly $k$ agents from $N\cup D_{k}$ such that
the remaining agents admit a wonderful partition. Checking whether this is
possible and finding a corresponding wonderful partition reduces to the
following more general problem, which we will show can be solved in polynomial
time.

H I K I N G - X - D E L E T E Input: A set $N$ of agents, for each agent $i\in
N$ two numbers $\ell_{i}\leq r_{i}$ such that
$S_{i}=\\{\ell_{i},\ldots,r_{i}\\},$ and also a number $0\leq x\leq|N|.$
Problem: Compute a set $N^{\prime}\subseteq N$ of size $x$ such that
$N\setminus N^{\prime}$ has a wonderful partition. Output $N^{\prime}$ and a
wonderful partition of $N\setminus N^{\prime}.$

We now show how to solve  H I K I N G - X - D E L E T E in polynomial time. We
can once again try to attack the problem recursively with our usual state
$(x_{1},x_{2},i,k).$ Just like we did for  H I K I N G - M I N - D E L E T E ,
we will have recursive calls for ignoring an agent; i.e., adding it to the set
$N^{\prime}$ of removed agents.555Note that previously we used $N^{\prime}$ to
denote $N(x_{1},x_{2},i)$ when discussing the recursive algorithm for the
original hiking problem. We do not keep this notation here. In order to ensure
that exactly $x$ agents are removed, we add another variable $r$ to the state
of the recursion: $(x_{1},x_{2},i,k,r),$ where $r$ is how many agents we want
to remove. The top-level call will be invoked with $r=x.$ The recursive
approach for  H I K I N G - M I N - D E L E T E now translates relatively
swiftly to the new setting. The main difference is the case where a state of
the form $(x_{1},x_{2},i,k,-)$ with $\ell_{i}\in[x_{1},x_{2}]$ performs two
recursive calls to $(x_{1},x,i-1,1,-)$ and $(x+1,x_{2},i-1,k,-).$ In
particular, say the state is $(x_{1},x_{2},i,k,r),$ then what should be the
values $r^{\prime}$ and $r^{\prime\prime}$ for the two recursive calls?
Intuitively, there is no fixed answer, since it could be that we remove more
agents in the first or in the second call. In fact, we have full freedom over
how to split the $r$ removals across the two calls as long as
$r^{\prime}+r^{\prime\prime}=r.$ Hence, we will iterate over all options
$0\leq r^{\prime}\leq r$ and set $r^{\prime\prime}=r-r^{\prime},$ and in each
case call recursively with $(x_{1},x,i-1,1,r^{\prime})$ and
$(x+1,x_{2},i-1,k,r^{\prime\prime}).$

######  Theorem 5.

H

I

K

I

N

G

-

X

-

D

E

L

E

T

E

is solvable in $O(n^{7})$ time.

###### Proof.

As before, it suffices to check feasibility, a solution can then be recovered
using standard techniques. Define the Boolean DP array
$\mathit{dp}[x_{1},x_{2},i,k,r]$ for $1\leq x_{1}\leq x_{2}\leq n,$ $0\leq
i\leq n,$ $0\leq k<x_{2},$ and $0\leq r\leq x$ with the meaning that
$\mathit{dp}[x_{1},x_{2},i,k,r]=1$ if and only if there exist $r$ agents that
can be removed from $N(x_{1},x_{2},i)$ such that the remaining agents admit a
wonderful partition into groups of sizes in $[x_{1},x_{2}]$ assuming that we
start with an incomplete group of current size $k$ which has to have final
size $x_{2}.$ At the end, $\mathit{dp}[1,n,n,0,x]$ will be 1 if and only if it
is possible to remove $x$ agents from $N$ such that the remaining agents admit
a wonderful partition. To compute the DP table, we use the following
recurrence relations and base cases:

  1. 1.

$\mathit{dp}[-,-,0,0,0]=1$;

  2. 2.

$\mathit{dp}[-,-,0,k,r]=0$ if $k\neq 0$ or $r\neq 0$;

  3. 3.

$\mathit{dp}[x_{1},x_{2},i,k,r]=\mathit{dp}[x_{1},x_{2},i-1,k,r]$ if
$\ell_{i}\notin[x_{1},x_{2}]$;

  4. 4.

$\mathit{dp}[x_{1},x_{2},i,k,r]=\mathit{dp}[x_{1},x_{2},i-1,k,r-1,d]\lor
X$666Only $X$ for $r=0$ as otherwise we would be referring to the invalid
value $r=-1.$ if $\ell_{i}\in[x_{1},x_{2}]$, where
$X:=\bigvee_{x=\ell_{i}}^{\min(x_{2},r_{i})}F_{x}$ and

$F_{x}:=\left\\{\begin{array}[]{ll}\mathit{dp}[x_{1},x_{2},i-1,(k+1)\
\mathrm{mod}\ x_{2},r]&x=x_{2}\\\
\bigvee_{r^{\prime}=0}^{r}\big{(}\mathit{dp}[x_{1},x,i-1,1\ \mathrm{mod}\
x,r^{\prime}]&\\\
\quad\land\mathit{dp}[x+1,x_{2},i-1,k,r-r^{\prime}]\big{)}&x<x_{2}.\\\
\end{array}\right.$

We explain the four cases separately: for cases (1) and (2) we have $i=0$;
i.e., the set of yet-to-be-considered agents is empty, so $k=r=0$ is necessary
and sufficient for the table to store a 1, signifying feasibility. As before,
case (3) straightforwardly ignores an agent that is not part of the current
set of active agents.

The more interesting case is case (4). First, the
$\mathit{dp}[x_{1},x_{2},i-1,k,r-1]$ term corresponds to removing an agent,
and it only applies to $r\geq 1$, as in the footnote. This decreases $r$ by 1
since we have just removed an agent. The
$X:=\bigvee_{x=\ell_{i}}^{\min(x_{2},r_{i})}F_{x}$ term is more involved. The
selection of $\ell_{i}\leq x\leq\min(x_{2},r_{i})$ corresponds to selecting
the size of the group that agent $i$ will be part of. For $x=x_{2},$ the
analysis is similar to our previous DPs. For $x<x_{2},$ on the other hand, we
moreover split the $r$ agent removals into $r^{\prime}$ removals for the first
recursive call and $r^{\prime\prime}=r-r^{\prime}$ for the second. Whether
both calls are successful is represented by the expression
$\mathit{dp}[x_{1},x,i-1,1\ \mathrm{mod}\
x,r^{\prime}]\land\mathit{dp}[x+1,x_{2},i-1,k,r^{\prime\prime}].$

As before, to compute the DP table in an acyclic fashion, it suffices to
iterate through $i$ in ascending order. The complexity of the approach is
$O(n^{7})$ because there are $O(n^{5})$ states and computing the value for
states of type (4) requires iterating through $O(n^{2})$ values for $(x,r).$ ∎

Using the previously-described binary search approach we get a solution for  H
I K I N G - M A X - S A T I S F I E D that runs only a $O(\log n)$ factor
slower than the runtime for  H I K I N G - X - D E L E T E .

######  Theorem 6.

H

I

K

I

N

G

-

M

A

X

-

S

A

T

I

S

F

I

E

D

is solvable in $O(n^{7}\log n)$ time.

It is possible to improve this further to $O(n^{6}\log n).$ We leave the
details for a future version of the paper, but in rough lines, this is
achieved as follows:

  1. 1.

Remove the need to binary search. This is possible because the DP for the
instance of  H I K I N G - X - D E L E T E constructed for $x=|N|$ actually
contains all the information required to answer for every $x<|N|.$ This is
because in general to go from the instance constructed for $x=x_{0}$ to the
instance constructed for $x=x_{0}+1$ one has to add a single additional dummy
agent which goes last in the sorted order. This removes an $O(\log n)$ factor.

  2. 2.

Notice that, for fixed values of $x_{1},x_{2},i,k,x$ the operations performed
in computing (4) implicitly resemble an $(\lor,\land)$-convolution. This can
be optimized using fast polynomial multiplication to get $O(n\log n)$ instead
of $O(n^{2})$. Overall, this turns one $O(n)$ factor into an $O(\log n)$
factor.

##  5 Hardness Results

We have shown that whenever the approval set of each agent is an interval,
solving  W O N D E R F U L - P A R T I T I O N is possible in polynomial time.
Clearly, whenever the agents have approval sets of size $1$ the existence of a
wonderful partition is polynomial as well: This can also be seen as a special
case of interval instances. In general, the approval sets are not necessarily
intervals, and without any assumption on the structure of the approval sets,
the  W O N D E R F U L - P A R T I T I O N problem is NP-complete even if the
size of the approval set is at most $3$. This follows from the hardness proof
of Woeginger [20] and the fact that the  E X A C T C O V E R B Y 3 - S E T S
problem (see below for the definition) is NP-hard even if every element of the
ground set appears in exactly three triples and triples overlap only in at
most one element [14].

In this section, we precisely map the boundary of tractability of the  W O N D
E R F U L - P A R T I T I O N problem with respect to the size of the approval
sets. While the case with approval sets of size 1 can be solved in polynomial
time, we now show NP-completeness if the approval sets have size at most 2.

######  Theorem 7.

Deciding  W O N D E R F U L - P A R T I T I O N is NP-complete, even if the
approval sets are of size exactly 2.

Let us start by observing that the wonderful partition problem, when
restricted to the case of approval sets of size exactly 2, is equivalent to a
graph-theoretic problem we call  O R I E N T A T I O N . For this, we write
$d^{+}(v)$ to denote the in-degree of a vertex $v\in V$ in a directed graph
$\vec{G}=(V,\vec{E})$.

O R I E N T A T I O N Input: An undirected graph $G=(V,E)$ with $V=[n],$
admitting parallel edges but no self-loops. Question: Does there exist an
orientation of the edges $\vec{G}$ such that $d^{+}(i)\equiv 0\pmod{i}$ for
each $i\in V$?

We now show that the two problems are equivalent. Indeed, an instance of  W O
N D E R F U L - P A R T I T I O N where all agents approve exactly two sizes
can be transformed into an equivalent instance of  O R I E N T A T I O N by
representing each agent approving sizes $i,j\in[n]$ by an undirected edge
$(i,j)$. Orienting this edge to either node $i$ or node $j$ models that the
respective agent is part of a partition of size $i$ or $j$, respectively. If
$d^{+}(i)=k\cdot i$ for some $k\geq 1$ then this means that $k$ partitions
with size $i$ will be created. Conversely, an instance of  O R I E N T A T I O
N with $m$ edges can be transformed to an instance of  W O N D E R F U L - P A
R T I T I O N with $m$ agents, where each edge $(i,j)$ corresponds to an agent
with approval set $\\{i,j\\}.$

Using the equivalence between the  W O N D E R F U L - P A R T I T I O N
problem and the  O R I E N T A T I O N problem, we will prove Theorem 7 by
reducing  E X A C T C O V E R B Y 3 - S E T S (  X 3 C ) to Orientation.  X 3
C is well-known to be NP-hard [13] and it is defined as follows:

E X A C T C O V E R B Y 3 - S E T S ( X 3 C ) Input: A ground set
$X=\\{x_{1},\dots,x_{3k}\\}$ and a collection $\mathcal{C}$ of 3-element
subsets (triples) of $X$. Question: Does there exist a subset
$\mathcal{C}^{\prime}\subseteq\mathcal{C}$ such that
$\bigcup_{C\in\mathcal{C}^{\prime}}C=X$ and $|\mathcal{C}^{\prime}|=k$, i.e.,
$\mathcal{C}^{\prime}$ is an exact cover of $X$?

###### Proof of Theorem 7.

Let us assume that $|\mathcal{C}|=q$ and let us enumerate all the triples as
$C_{1},\dots,C_{q}$. For simplicity, we fix $p=3k$. Notice that any element
$x$ in the ground set can be contained in at most ${p-1\choose 2}<p^{2}$
triples. Let us denote by $\delta$ the highest number of such occurrences.

Our reduction is as follows:

  * •

For each element in the ground set $x_{i}\in X$, for $i\in[p]$, we create an
_element gadget_ which consists of two nodes having value $i\cdot\delta$ and
$i\cdot\delta+1$, respectively. Such two nodes are connected by
$i\cdot\delta-1$ many edges. We may refer to these edges as
element-($x_{i}$)-edges. Moreover, we call node $i\cdot\delta$ the
element-($x_{i}$)-node.

  * •

For each triple $C_{j}\in\mathcal{C}$, for $j\in[q]$, we create a _triple
gadget_ which consists of two nodes having value $p\cdot\delta+4j$ and
$p\cdot\delta+4j-3$, respectively. Such two nodes are connected by
$p\cdot\delta+4j-3$ many edges. We will refer to these edges as
triple-($C_{j}$)-edges. Moreover, we call node $p\cdot\delta+4j$ the
triple-($C_{j}$)-node.

  * •

Finally, for each $x_{i}\in X$ and $C_{j}\in\mathcal{C}$ such that $x_{i}\in
C_{j}$, we connect the nodes $i\cdot\delta$ and $p\cdot\delta+4j$ with one
edge.

Clearly, the reduction is polynomial. Moreover, the constructed graph is well-
defined (there is no overlap in labeling gadgets corresponding to different
compounds). See Figure 2 for an example.

$p\cdot\delta+4j-3$$p\cdot\delta+4j$$C_{j}$-node$i\cdot\delta$$x_{i}$-node$i\cdot\delta+1$$p\cdot\delta+4j^{\prime}$$C_{j^{\prime}}$-node$p\cdot\delta+4j^{\prime}-3$
$C_{j}$-gadget $C_{j^{\prime}}$-gadget
$x_{i}$-gadget$p\cdot\delta+4j-3$$1$$p\cdot\delta+4j^{\prime}-3$$\delta\cdot
i-1$

Figure 2: Gadgets – On the left, above (resp. below) the triple gadget for
$C_{j}$ (resp. $C_{j^{\prime}}$); on the right, the element gadget for
$x_{i}$. The picture shows the set-up of the gadgets if element $x_{i}$ is
contained in $C_{j}$ but not in $C_{j^{\prime}}$. Labels on edges represent
the number of parallel edges between two nodes.

The idea is to determine the exact cover by means of the orientation of edges
connecting elements and triple gadgets. Specifically, whenever a triple
$C_{j}$ is in the covering set, the three edges connecting the gadget $C_{j}$
with the corresponding element gadgets must all be oriented towards the
corresponding element node. In turn, if $C_{j}$ is not in the covering set,
the orientation of these edges must be towards the triple-($C_{j}$)-node.

Having this interpretation in mind, it follows that whenever an exact cover
exists, an orientation of $G$ exists as well. In particular, for any triple
$C_{j}$ in the covering set we can orient all edges incident to the
triple-($C_{j}$)-node away from the triple-($C_{j}$)-node, and in the opposite
direction, otherwise. Moreover, every element edge is directed towards the
corresponding element node.

It remains to show the other direction, i.e., that whenever an orientation
exists, an exact cover exists as well.

The rest of this proof is established by the following observations:

  1. 1.

In any feasible orientation, the element edges are always oriented toward the
element node. Otherwise, the orientation won’t be feasible since the non-
element node endpoint of every element edge has a label that is higher than
the number of its incident edges.

  2. 2.

Denote by $t_{i}$ the number of triples containing $x_{i}$, the
element-($x_{i}$)-node has $i\cdot\delta-1+t_{i}$ incident edges. By (1), the
in-degree in a feasible orientation is at least $i\cdot\delta-1$. Since
$t_{i}\leq\delta$, in a feasible orientation of $G$ the in-degree of
$i\cdot\delta$ is exactly its value. As a consequence, there is only one
incoming edge from triple gadgets, and therefore each element is covered by
exactly one triple.

  3. 3.

Last but not least, in a feasible orientation, a triple cannot be only
partially used. Specifically, for a triple $C_{j}$ with triple-($C_{j}$)-node
$v$ either all edges incident to $v$ must be oriented to $v$ or all incident
edges must be oriented away from $v$. This is ensured by the fact that in any
feasible orientation the in-degree of a triple $C_{j}$ is either $0$ or
$p\cdot\delta+4j$.

This concludes the proof. ∎

##  6 Wonderful and Maximum Egalitarian Partitions

Here we exploit the connection between  W O N D E R F U L - P A R T I T I O N
and the problem of maximizing the egalitarian welfare in anonymous Hedonic
Games. Let us consider an anonymous Hedonic Game instance where each agent
expresses their satisfaction with coalition sizes by means of a utility
function, that is, for each $i\in N$ there exists a mapping
$u_{i}:[n]\rightarrow\mathbb{R}_{\geq 0}$. Recall that an instance of  W O N D
E R F U L - P A R T I T I O N can be considered a binary instance of anonymous
Hedonic Games. The egalitarian welfare of a partition $\pi$ is defined as
$\min_{i\in N}u_{i}(|\pi(i)|)$, i.e., it is the minimum utility obtained by
any of the agents under partition $\pi$. We call the problem of finding the
value of the maximum egalitarian welfare  M A X - E G A L I T A R I A N .

######  Proposition 8.

W

O

N

D

E

R

F

U

L

-

P

A

R

T

I

T

I

O

N

and  M A X - E G A L I T A R I A N for anonymous Hedonic Games are polynomial
time equivalent.

###### Proof.

On the one hand, a  W O N D E R F U L - P A R T I T I O N instance is a yes
instance if  M A X - E G A L I T A R I A N is $1$ and it is a no instance
otherwise.

On the other hand, if we have a  M A X - E G A L I T A R I A N instance there
are at most $n^{2}$ distinct values $u_{i}(j)$. Assume there are $k$ distinct
values and let us sort them from the highest to the lowest, namely,
$v_{1}>\dots>v_{k}$. For each value $v_{h}$ we can define a binary instance
where a coalition of size $j\in[n]$ is approved by agent $i$ if and only if
$u_{i}(j)\geq v_{h}$. We can therefore determine if there exists a partition
having egalitarian welfare of at least $v_{h}$ by solving  W O N D E R F U L -
P A R T I T I O N on the just described instance. Clearly, if there exists a
partition having an egalitarian welfare of at least $v$ then there exists a
partition having an egalitarian welfare of value at least $v^{\prime}$ for
each $0\leq v^{\prime}\leq v$. Conversely, if there is no partition having an
egalitarian welfare of at least $v$ then there is no partition having an
egalitarian welfare of at least $v^{\prime\prime}$, for each
$v^{\prime\prime}\geq v$. Therefore, we can use binary search among the
possible values $v_{1}\dots v_{k}$ to find the maximum value $v$ such that a
partition having an egalitarian welfare of at least $v$ exists. This solves  M
A X - E G A L I T A R I A N . ∎

######  Corollary 9.

If  W O N D E R F U L - P A R T I T I O N can be decided in time $T(n)$, then
M A X - E G A L I T A R I A N can be solved in
$O((n^{2}+T(n))\cdot\log_{2}n)$.

Given the polynomial time equivalence between these two problems, it follows
that solving  M A X - E G A L I T A R I A N for anonymous Hedonic Games is in
general computationally intractable. Nevertheless, there exists a special
class of anonymous Hedonic Games that can be solved using our dynamic
programming approach for  W O N D E R F U L - P A R T I T I O N described in
Section 4.1.

An anonymous Hedonic Games instance is said to be _naturally single-peaked_ if
for every agent $i\in N$ there exists a _peak_ $p_{i}\in[n]$ such that
$h<k\leq p_{i}$ or $h>k\geq p_{i}$ imply that $u_{i}(k)>u_{i}(h)$ holds.
Roughly speaking, the closer to $p_{i}$ the coalition size of $i$ is the
better the utility of agent $i$.

######  Theorem 10.

The maximum egalitarian welfare for anonymous naturally single-peaked Hedonic
Games can be computed in time $O(n^{5}\log_{2}n)$.

###### Proof.

We can use a similar idea as in the polynomial time reduction from  M A X - E
G A L I T A R I A N to  W O N D E R F U L - P A R T I T I O N , as described
in Proposition 8. In  M A X - E G A L I T A R I A N we are looking for a
partition that maximizes the utility of the agent having the lowest utility.
Here, since we consider naturally single-peaked preferences, the utility of an
agent $i$ is increased the closer the size of their assigned group $|\pi(i)|$
is to their ideal group size $p_{i}$ (the peak value of agent $i$). We can now
fix some distances $\Delta,\Delta^{\prime}$ and define that any agent $i$
approves their assigned group size if it is in the interval
$[p_{i}-\Delta,p_{i}+\Delta^{\prime}]$. This defines an instance of  W O N D E
R F U L - P A R T I T I O N - I N T E R V A L S .

Now, by trying for all possible values of $\Delta,\Delta^{\prime}$ and
applying Corollary 9 and Theorem 3, the statement follows. ∎

## Acknowledgments

We would like to thank the Schloss Dagstuhl-Leibniz-Zentrum für Informatik who
hosted the event “Computational Social Dynamics” (Seminar 22452) in November
2022 [15], where the work leading to this paper was started. We are grateful
to Martin Hoefer, Sigal Oren, and Roger Wattenhofer for organizing this event.
We additionally thank Roger Wattenhofer for the useful discussions concerning
this work.

The fifth author is grateful for the support by the PNRR MIUR project FAIR -
Future AI Research (PE00000013), and the DFG, German Research Foundation,
grant (Ho 3831/5-1).

## References

  * [1] José Alcalde and Pablo Revilla.  Researching with whom? Stability and manipulation.  Journal of Mathematical Economics, 40(8):869–887, 2004.
  * [2] Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Dominik Peters.  Fractional hedonic games.  ACM Transactions on Economics and Computation, 7(2):1–29, 2019\.
  * [3] Haris Aziz, Felix Brandt, and Paul Harrenstein.  Pareto optimality in coalition formation.  Games and Economic Behavior, 82:562–581, 2013.
  * [4] Haris Aziz, Paul Harrenstein, Jérôme Lang, and Michael Wooldridge.  Boolean hedonic games.  In Fifteenth International Conference on the Principles of Knowledge Representation and Reasoning, 2016.
  * [5] Haris Aziz and Raul Savani.  Hedonic games.  In Handbook of Computational Social Choice. Handbook of Computational Social Choice. Cambridge University Press, 2016.
  * [6] Coralio Ballester.  Np-completeness in hedonic games.  Games and Economic Behavior, 49(1):1–30, 2004.
  * [7] Suryapratim Banerjee, Hideo Konishi, and Tayfun Sönmez.  Core in a simple coalition formation game.  Social Choice and Welfare, 18:135–153, 2001.
  * [8] Anna Bogomolnaia and Matthew O. Jackson.  The stability of hedonic coalition structures.  Games and Economic Behavior, 38(2):201–230, 2002.
  * [9] Andreas Darmann, Edith Elkind, Sascha Kurz, Jérôme Lang, Joachim Schauer, and Gerhard Woeginger.  Group activity selection problem with approval preferences.  International Journal of Game Theory, 47(3):767–796, 2018.
  * [10] Jacques H Dreze and Joseph Greenberg.  Hedonic coalitions: Optimality and stability.  Econometrica: Journal of the Econometric Society, pages 987–1003, 1980.
  * [11] Edith Elkind and Michael J. Wooldridge.  Hedonic coalition nets.  In 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary, May 10-15, 2009, Volume 1, pages 417–424, 2009.
  * [12] Guy Even, Retsef Levi, Dror Rawitz, Baruch Schieber, Shimon Shahar, and Maxim Sviridenko.  Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs.  ACM Transactions on Algorithms, 4(3):34:1–34:17, 2008.
  * [13] Michael R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  1979\.
  * [14] Teofilo F. Gonzalez.  Clustering to minimize the maximum intercluster distance.  Theoretical Computer Science, 38:293–306, 1985.
  * [15] Martin Hoefer, Sigal Oren, Roger Wattenhofer, and Giovanna Varricchio.  Computational Social Dynamics (Dagstuhl Seminar 22452).  Dagstuhl Reports, 12(11):28–44, 2023.
  * [16] Jan Karel Lenstra, Franz Rendl, Frits Spieksma, and Marc Uetz.  In memoriam Gerhard Woeginger.  Journal of Scheduling, 25(5):503–505, 2022.
  * [17] Martin Olsen.  Nash stability in additively separable hedonic games and community structures.  Theory of Computing Systems, 45:917–925, 2009.
  * [18] Dominik Peters.  Complexity of hedonic games with dichotomous preferences.  In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 579–585. AAAI Press, 2016.
  * [19] Renate Schmid, 2011.  © by Mathematisches Forschungsinstitut Oberwolfach gGmbH [Online; accessed November 01, 2023]. Published under CC-BY-SA 2.0.
  * [20] Gerhard Woeginger.  Core stability in hedonic coalition formation.  In International Conference on Current Trends in Theory and Practice of Computer Science, pages 33–50. Springer, 2013.


###### Abstract

The Bargman-Wigner equations are generalized to include chiral symmetry based
on the irreps of the Poincaré group, and the chirial Bargmann-Wigner equations
are derived for spin-1 massive fields. By specifying the chiral basis, the
chiral Bargmann-Wigner equations are reduced to the Proca-like equation, which
is coupled by chirality to an auxiliary equation for spin-0 massive field. The
coupling is a new phenomenon whose physical implications for the Higgs field
and dark matter are discussed.

Chiral Bargmann-Wigner Equations for Spin-1 Massive Fields

T. B Watson and Z. E. Musielak

##  1 Introduction

In the Bargmann-Wigner formalism [1], all possible relativistic equations are
derived by using the unitary representations of the Poincaré group classified
by Wigner [2,3]. A field of rest mass $m$ and spin $s\leq 1/2$ is described by
a symmetric multispinor for which the Bargmann-Wigner (BW) equations are
derived [1]. For special cases of $s=1/2$, $s=1$ and $s=3/2$, the BW equations
reduce to the Dirac [4], Proca [5] and Rarita-Schwinger [6] equations,
respectively; however, for $s=2$, see [7]. The BW equations are coupled first-
order partial differential equation with the original Dirac operator
($\hat{D}=i\gamma^{\mu}\partial_{\mu}-m$) acting on multispinor wavefunctions.

To generalize the Dirac equation, different modifications were made to the
Dirac operator. Physical reasons for these modifications range from attempts
to unify leptons and quarks [8-10] and account for the three families of
elementary particles [11-15], to including ad hoc a pseudoscalar mass [16] and
extending the Dirac equation to distances comparable to the Planck length
[17]. The main procedures giving such generalizations have been identified as
the Takuoka-Sen-Gupta [18-20], Weinberg-Tucker-Hammer [21-23] and Barut
[11,12] formalisms [24]. Since each formalism leads to different forms of the
Dirac equations and their opertaors $\hat{D}$, the corresponding modifications
of the BW equations have also been accomplished [25].

Recently, we derived the Dirac equation with chiral symmetry (DECS) by using
the irreducible representations (irreps) of the Poincaré group $\mathcal{P}\
=\ SO(3,1)\otimes_{s}T(3+1)$, with $SO(3,1)$ being a non-invariant Lorentz
group of rotations and boosts and $T(3+1)$ an invariant subgroup of spacetime
translations, and the group including reversal of parity and time [3]. The
derived DECS [26] can be written

$(i\gamma^{\mu}\partial_{\mu}-me^{-2i\alpha\gamma^{5}})\psi=0\ ,$ (1)

where $\alpha$ is the chiral angle and $\psi$ represents a four-component
spinor that transforms as one of the irreps of $T(3+1)\in{\mathcal{P}}$
extended by parity, and each of its components satisfies the Klein-Gordon
equation [27,28]. We demonstrated that the chiral rotation of a massive field
is equivalent to an alternative choice of chiral basis, and that the Dirac
equation is obtained by factorization of the Klein-Gordon equation if, and
only if, a specific choice of chirial basis is selected [26].

The nonstandard factorizations of the Klein-Gordon equation resulting from
different choices of chiral bases redistribute the mass available to the field
between the left- and right-chiral components, which allows identifying the
mass term in the DECS with pseudo-scalar mass. The presence of this pseudo-
scalar mass results in pseudo-scalar Higgs that can be used to explain
smallness of neutrino masses and also properties dark matter particles [26].

In this Letter, we extend the DECS beyond spin-1/2 particles and generalize
the BW equations to include chiral symmetry. Our method to derive the chiral
Bargmann-Wigner (CBW) equations is based on the irreps of the Poincaré group
$\mathcal{P}$. The derived CBW equations are valid for spin-1 massive fields.
By specifying the chiral basis, the CBW equations reduce to the Proca-like
equation [5] that is coupled to an auxiliary equation for spin-0 massive field
is obtained. The resulting coupling is caused by chirality and it is a new
phenomenon, whose physical implications are discussed.

##  2 Bargmann-Wigner equations with chiral symmetry

We may extend the usefulness of DECS beyond spin-1/2 particles by using
multispinors considered in the Bargmann-Wigner formalism [1]. We begin by
observing that the at-rest solutions of Eq. (1) may be written as

$\psi^{(\pm)}=\omega^{(\pm)}(\alpha)e^{\mp imt}\ ,$ (2)

where $(+)\in\\{(1),(2)\\}$ indicate positive energy solutions and
$(-)\in\\{(3),(4)\\}$ indicate negative energies. Then, these spinors take the
form

$\omega^{(1)}(\alpha)=\begin{bmatrix}\cos{\alpha}\\\ 0\\\ i\sin{\alpha}\\\
0\\\ \end{bmatrix},\;\omega^{(2)}(\alpha)=\begin{bmatrix}0\\\ \cos{\alpha}\\\
0\\\ i\sin{\alpha}\\\ \end{bmatrix},\;$
$\omega^{(3)}(\alpha)=\begin{bmatrix}i\sin{\alpha}\\\ 0\\\ \cos{\alpha}\\\
0\\\ \end{bmatrix},\;\omega^{(4)}(\alpha)=\begin{bmatrix}0\\\ i\sin{\alpha}\\\
0\\\ \cos{\alpha}\\\ \end{bmatrix}$ (3)

It is easily to verify that spinors $\omega^{(1)}$ and $\omega^{(3)}$ are
$+\frac{1}{2}$ eigenstates of the spin projection operator $\hat{S}^{3}$ and
$\omega^{(2)}$ and $\omega^{(4)}$ are similarly $-\frac{1}{2}$ eigenstates.
Moreover, all of these states have a definite propagation mass.

We may now define the general set of positive energy multispinors of spin-1
from the tensor product of the spinors of spin-1/2 as follows

$\omega^{(1,1)}(\alpha,\beta)=\omega^{(1)}(\alpha)\otimes\omega^{(1)}(\beta)\
,$ (4)
$\omega^{(1,2)}(\alpha,\beta)=\omega^{(2,1)}(\alpha,\beta)=\omega^{(1)}(\alpha)\otimes\omega^{(2)}(\beta)+\omega^{(2)}(\alpha)\otimes\omega^{(1)}(\beta)\
,$ (5)

and

$\omega^{(2,2)}(\alpha,\beta)=\omega^{(2)}(\alpha)\otimes\omega^{(2)}(\beta)\
,$ (6)

where $\beta$ is the chiral angle assosciated with the chiral basis of the
second bispinor of our representation. It must be noted that different chiral
angles can be paired together in a single spinor as they are all valid
eigenstates of momentum and spin as can be seen by observing these
multispinors are eigenstates of the following spin operator (with indices
included for clarity)

$\big{(}\hat{S}^{3}\big{)}^{\mu\nu}_{\mu^{\prime}\nu^{\prime}}=\big{(}\hat{S}^{3}\big{)}^{\mu}_{\mu^{\prime}}\delta^{\nu}_{\nu^{\prime}}+\big{(}\hat{S}^{3}\big{)}^{\nu}_{\nu^{\prime}}\delta^{\mu}_{\mu^{\prime}}\
,$ (7)

and satisfy their respective at-rest DECS

$(\gamma^{0}-e^{-2i\alpha})^{\mu}_{\mu^{\prime}}\omega^{(+,+)}_{\mu\nu}(\alpha,\beta)=0\
,$ (8)

and

$(\gamma^{0}-e^{-2i\beta})^{\nu}_{\nu^{\prime}}\omega^{(+,+)}_{\mu\nu}(\alpha,\beta)=0\
,$ (9)

for $(+,+)\in\\{(1,1),(1,2),(2,2)\\}$. We may then move from the rest frame to
an arbitrary momentum state by boosting each spinor

$\omega^{(+,+)}_{\mu\nu}(\alpha,\beta;p^{\mu})=\Lambda(\alpha,p^{\mu})^{\mu}_{\mu^{\prime}}\Lambda(\beta,p^{\mu})^{\nu}_{\nu^{\prime}}\omega^{(+,+)}_{\mu\nu}(\alpha,\beta)\
.$ (10)

We note that the form of $\Lambda(\alpha,p^{\mu})$ differs non-trivially from
the form when $\alpha=0$. We omit a more detailed discussion of this form as,
for our purposes, the existence of such a transformation is sufficient. We
next define the symmetric and anti-symmetric positive energy multispinors and
find

$\Omega^{(+,+)}_{\mu\nu}(\alpha,\beta;p^{\mu})=\frac{1}{2}\big{(}\omega^{(+,+)}_{\mu\nu}(\alpha,\beta;p^{\mu})+\omega^{(+,+)}_{\mu\nu}(\beta,\alpha;p^{\mu})\big{)}\
,$ (11)

and

$\widetilde{\Omega}^{(+,+)}_{\mu
c}(\alpha,\beta;p^{\mu})=\frac{1}{2}\big{(}\omega^{(+,+)}_{\mu\nu}(\alpha,\beta;p^{\mu})-\omega^{(+,+)}_{\mu\nu}(\beta,\alpha;p^{\mu})\big{)}\
,$ (12)

such that the full symmetric and anti-symmetric positive energy solutions are
given by

$\psi^{(+)}_{\mu\nu}(\alpha,\beta,x^{\mu})=\sum_{(+,+)}\int
C_{1}^{(+,+)}(p^{\mu})\Omega^{(+,+)}_{\mu\nu}(\alpha,\beta;p^{\mu})e^{-ip_{\mu}x^{\mu}}d^{3}p\
,$ (13)

and

$\widetilde{\psi}^{(+)}_{\mu\nu}(\alpha,\beta,x^{\mu})=\sum_{(+,+)}\int
C_{2}^{(+,+)}(p^{\mu})\widetilde{\Omega}^{(+,+)}_{\mu\nu}(\alpha,\beta;p^{\mu})e^{-ip_{\mu}x^{\mu}}d^{3}p\
,$ (14)

where the sum is over $(+,+)\in\\{(1,1),(1,2),(2,2)\\}$.

Similar arguments for negative energy solutions lead to the construction of
the negative energy multispinors. Notationally this is achieved via a simple
index substitution $(+,+)\rightarrow(-,-)\in\\{(3,3),(3,4),(4,4)\\}$ and
flipping the sign of the exponential. With this complete set of states, we may
identify the most general symmetric and antisymmetric multispinors

$\Psi_{\mu\nu}(\alpha,\beta;x^{\mu})=a_{1}\psi^{(+)}_{\mu\nu}(\alpha,\beta,x^{\mu})+b_{1}\psi^{(-)}_{\mu\nu}(\alpha,\beta,x^{\mu}),$
(15)

and

$\widetilde{\Psi}_{\mu\nu}(\alpha,\beta;x^{\mu})=a_{2}\widetilde{\psi}^{(+)}_{\mu\nu}(\alpha,\beta,x^{\mu})+b_{2}\widetilde{\psi}^{(-)}_{\mu\nu}(\alpha,\beta,x^{\mu})$
(16)

that satisfy the following four coupled equations

$[i\gamma^{\mu}\partial_{\mu}-m\cos(\alpha-\beta)e^{-i(\alpha+\beta)\gamma^{5}}]^{\mu/\nu}_{\mu^{\prime}/\nu^{\prime}}\Psi_{\mu\nu}(\alpha,\beta;x^{\mu})$
$\hskip
18.06749pt=[-im\sin(\alpha-\beta)\gamma^{5}e^{-i(\alpha+\beta)\gamma^{5}}]^{\mu/\nu}_{\mu^{\prime}/\nu^{\prime}}\widetilde{\Psi}_{\mu\nu}(\alpha,\beta;x^{\mu})\
,$ (17)

and

$[i\gamma^{\mu}\partial_{\mu}-m\cos(\alpha-\beta)e^{-i(\alpha+\beta)\gamma^{5}}]^{\mu/\nu}_{\mu^{\prime}/\nu^{\prime}}\widetilde{\Psi}_{\mu\nu}(\alpha,\beta;x^{\mu})$
$\hskip
18.06749pt=[-im\sin(\alpha-\beta)\gamma^{5}e^{-i(\alpha+\beta)\gamma^{5}}]^{\mu/\nu}_{\mu^{\prime}/\nu^{\prime}}\Psi_{\mu\nu}(\alpha,\beta;x^{\mu})\
,$ (18)

where the summed indices have been combined for brevity.

Isolating either multispinor yields

$[\partial^{\mu}\partial_{\mu}+m^{2}]^{\mu}_{\mu^{\prime}}\Psi_{\mu\nu}(\alpha,\beta;x^{\mu})=0\
,$ (19)

and

$[\partial^{\mu}\partial_{\mu}+m^{2}]^{\mu}_{\mu^{\prime}}\widetilde{\Psi}_{\mu\nu}(\alpha,\beta;x^{\mu})=0\
,$ (20)

which demonstrates that each element of our multispinors satisfy the Klein-
Gordon equation. These are new BW equations with chiral symmetry (CBW
equations) for spin-1 massive fields, and they reduce to the BW equations when
$\alpha=\beta$ in which case $\widetilde{\Psi}$ vanishes. This shows that
chiral symmetry requires additional equation for $\widetilde{\Psi}$. The
effects of this additional equation on the Proca equation [5] are now
considered and discussed.

##  3 New insights into the Proca Equation

The CBW equations allows us to identify representations of spin-1 fields
consistent with those degrees of freedom observed in the DECS. Using [29], we
relate these representations to those known in the particle physics. Let
$\hat{C}=i\gamma^{2}\gamma^{0}$ and
$\sigma^{\mu\nu}=\frac{i}{2}[\gamma^{\mu},\gamma^{\nu}]$, then the Clifford
basis is the following set of ten symmetric matrices
$\\{\gamma^{\mu}\hat{C},\hat{\sigma}^{\mu\nu}\hat{C}\\}$, and the six anti-
symmetric matrices
$\\{\gamma^{\mu}\gamma^{5}\hat{C},i\gamma^{5}\hat{C},\hat{C}\\}$ that allow
expanding the multi-spinors in this basis, and obtian

$\Psi=mA_{\sigma}\gamma^{\sigma}\hat{C}+\frac{1}{2}F_{\sigma\tau}\hat{\sigma}^{\sigma\tau}\hat{C}\
,$ (21)

and

$\widetilde{\Psi}=\rho
e^{-i\theta\gamma^{5}}\hat{C}+mB_{\sigma}\gamma^{\sigma}\gamma^{5}\hat{C}\ ,$
(22)

where $\rho$ is a scalar field, $\theta$ is a scalar parameter, $A^{\mu}$ and
$B^{\mu}$ are vector fields, and $F^{\mu\nu}$ is an antisymmetric tensor.

Writing the CBW equations in matrix form, we find the four linearly
independent combinations

$i\partial_{\mu}\big{(}\gamma^{\mu}\Psi+\Psi(\gamma^{\mu})^{T}\big{)}-m\cos{(\alpha-\beta)}\big{\\{}\Psi,e^{-i(\alpha+\beta)\gamma^{5}}\big{\\}}$
$\hskip 72.26999pt-
im\sin{(\alpha-\beta)}\big{[}\widetilde{\Psi},\gamma^{5}e^{-i(\alpha+\beta)\gamma^{5}}\big{]}=0\
,$ (23)
$i\partial_{\mu}\big{(}\gamma^{\mu}\widetilde{\Psi}+\widetilde{\Psi}(\gamma^{\mu})^{T}\big{)}-m\cos{(\alpha-\beta)}\big{\\{}\widetilde{\Psi},e^{-i(\alpha+\beta)\gamma^{5}}\big{\\}}$
$\hskip 72.26999pt-
im\sin{(\alpha-\beta)}\big{[}\Psi,\gamma^{5}e^{-i(\alpha+\beta)\gamma^{5}}\big{]}=0\
,$ (24)
$i\partial_{\mu}\big{(}\gamma^{\mu}\Psi-\Psi(\gamma^{\mu})^{T}\big{)}+m\cos{(\alpha-\beta)}\big{[}\Psi,e^{-i(\alpha+\beta)\gamma^{5}}\big{]}$
$\hskip
72.26999pt+im\sin{(\alpha-\beta)}\big{\\{}\widetilde{\Psi},\gamma^{5}e^{-i(\alpha+\beta)\gamma^{5}}\big{\\}}=0\
,$ (25)

and

$i\partial_{\mu}\big{(}\gamma^{\mu}\widetilde{\Psi}-\widetilde{\Psi}(\gamma^{\mu})^{T}\big{)}+m\cos{(\alpha-\beta)}\big{[}\widetilde{\Psi},e^{-i(\alpha+\beta)\gamma^{5}}\big{]}$
$\hskip
72.26999pt+im\sin{(\alpha-\beta)}\big{\\{}\Psi,\gamma^{5}e^{-i(\alpha+\beta)\gamma^{5}}\big{\\}}=0\
.$ (26)

Then, substituting the matrix expansions of the multispinors and exploiting
the linear independence of the basis matrices, we obtain our constraints.
Among these are the requirement that the fields $\rho$ and $B_{\mu}$ vanish
and $\theta=0$ unless we enforce $\theta=\pi/2-\alpha-\beta\ $. With this
condition, we define the rotated fields

${\begin{bmatrix}A^{\prime}_{\mu}\\\ iB^{\prime}_{\mu}\\\
\end{bmatrix}}={\begin{bmatrix}\cos{(\alpha-\beta)}&\sin{(\alpha-\beta)}\\\
-\sin{(\alpha-\beta)}&\cos{(\alpha-\beta)}\\\
\end{bmatrix}}{\begin{bmatrix}A_{\mu}\\\ iB_{\mu}\\\ \end{bmatrix}}$ (27)

and summarize the set of constraint equations as

$\displaystyle
F_{\sigma\tau}\cos{(\alpha+\beta)}+\frac{1}{2}\partial^{\sigma}F^{\mu\nu}\epsilon_{\mu\nu\sigma\tau}\sin{(\alpha+\beta)}-(\partial_{\sigma}A^{\prime}_{\tau}-\partial_{\tau}A^{\prime}_{\sigma})$
$\displaystyle=0\ ,$ (28)
$\displaystyle\partial_{\sigma}B^{\prime}_{\tau}-\partial_{\tau}B^{\prime}_{\sigma}$
$\displaystyle=0\ ,$
$\displaystyle\partial^{\sigma}F_{\sigma\tau}+m^{2}A^{\prime}_{\tau}\cos{(\alpha+\beta)}$
$\displaystyle=0\ ,$
$\displaystyle\frac{1}{2}\partial^{\sigma}F^{\mu\nu}\epsilon_{\mu\nu\sigma\tau}+m^{2}A^{\prime}_{\tau}\sin{(\alpha+\beta)}$
$\displaystyle=0\ ,$
$\displaystyle\partial^{\mu}A^{\prime}_{\mu}+i\rho\sin{(2\alpha-2\beta)}$
$\displaystyle=0\ ,$
$\displaystyle\partial^{\mu}B^{\prime}_{\mu}+\rho\cos{(2\alpha-2\beta)}$
$\displaystyle=0\ ,$
$\displaystyle\partial_{\sigma}\rho-m^{2}B^{\prime}_{\sigma}$
$\displaystyle=0\ .$

Taking the divergence of the first of these constraints and eliminating
explicit dependence on $F_{\mu\nu}$ and $B^{\prime}_{\mu}$, we find the basic
equations governing the fields reduce to three coulped equations of
$A^{\prime}_{\mu}$ and $\rho$:

$\displaystyle\partial^{\nu}\big{(}\partial_{\nu}A^{\prime}_{\mu}-\partial_{\mu}A^{\prime}_{\nu}\big{)}+m^{2}A^{\prime}_{\mu}$
$\displaystyle=0\ ,$ (29)
$\displaystyle\big{[}\partial^{\mu}\partial_{\mu}+m^{2}\cos(2\alpha-2\beta)\big{]}\rho$
$\displaystyle=0\ ,$
$\displaystyle\partial^{\mu}A^{\prime}_{\mu}+i\rho\sin{(2\alpha-2\beta)}$
$\displaystyle=0\ .$

It is evident that the vanishing of $\rho$ is equivalent to the reduction of
these equations to the Proca equation [5].

A more symmetric form of these equations is obtained by the definition of the
constant $\kappa\equiv\sqrt{m^{2}\cos{2(\alpha-\beta)}-\mu^{2}}$ (where $\mu$
appears as a free parameter), and the scalar field $\varphi$ defined in terms
of the divergence of the vector field
$\varphi\equiv\kappa^{-1}\partial^{\mu}A^{\prime}_{\mu}$. The constraint
equations then reduce to

$\displaystyle\left[\partial^{\nu}\partial_{\nu}+m^{2}\right]A^{\prime}_{\mu}$
$\displaystyle=+\kappa\partial_{\mu}\varphi\ ,$ (30)
$\displaystyle\left[\partial^{\nu}\partial_{\nu}+\mu^{2}\right]\varphi$
$\displaystyle=-\kappa\partial^{\mu}A^{\prime}_{\mu}\ ,$

where the first equation is the Proca-like equation and the second is the
auxiliary equation for $\varphi$. Note that $m$ and $\mu$ are generally not
equal and correspond to the masses of the vector and scalar fields
respectively. In the Lorentz gauge $\partial^{\mu}A^{\prime}_{\mu}=0$, the
scalar wavefunction $\varphi=0$ and the Proca-like equation becomes the Proca
equation [5]. The coupling between the spin-1 and spin-0 massive fields is a
new phenomena whose physical implications are now discussed.

##  4 Physical implications

The two main results of this Letter are the chiral Bargmann-Wigner (CBW)
equations for spin-1 massive fields and the Proca-like equation with its
required auxiliary equation for spin-0 massive fields. There are several
physical implications of these results.

The degrees of freedom introduced by the choice of chiral basis allowed by
Poincaré invariance admit an asymmetry to the defined representations of the
considered spin-1 massive fields described by the multispinors, thereby
allowing for generalization of the BW equations to include chiral symmetry. As
a result two CBW equations are obtained, one for $\Psi$ and the other for
$\widetilde{\Psi}$, and they are reduced to the original BW equations when
$\widetilde{\Psi}=0$, which is equaivalent to the case when chirality is
neglected. Thus, the main physical implication of the CBW equations is the
presence of the additional field described by the multispinor
$\widetilde{\Psi}$.

To explore this additional field in detail, we specified the chirial basis in
such a way that the CBW equations reduce to the Proca-like equation that is
coupled to a spin-0 massive field. We demonstrated that the asymmetry of the
defined representations manifests itself physically as the coupled scalar and
vector fields, with the total spin being consistent with our choice of
representations. By committing to a specific chiral basis one fixes the
coupling between these fields and so restricts the system to the same total
number of degrees of freedom as in the case when the chiral bases coincide.
The coupling is described by the coefficient $\kappa$ that depends on the
chiral angles $\alpha$ and $\beta$ as well as on masses $m$ and $\mu$ of the
scalar and vector fields, respectively.

The coupling between the scalar and vector fields caused by the presence of
chiral symmetry is a new phenomenon reported in this Letter. While the
fundamental spin-1 massive fields describing bosons $W^{\pm}$ and $Z^{0}$ are
well-known in the Standard Model (SM) [29], the only fundamental scalar field
in the model is the Higgs field [30,31], with a strong evidence for a
elementary massive particle of spin-0 and positive parity [32]. Therefore, let
us identify the scalar field coupled to the vector field is the Higgs field
and explore the physical implications which follow from this supposition.
Since our results show that the physical properties of the scalar field are
such that its wavefunction $\varphi$ is proportional to the divergence of the
vector field, with $\kappa$ being the proportionality coefficient representing
chirality, this implies that the Higgs field must be related to the divergence
of the vector wavefunction and that chirality of spin-1 massive elementary
particles place the dominant role in this relationship. To determine the
validity of this statement further theoretical studies and potential
experimental verifications are necessary but both out the scope of this
Letter.

Another possibility is the existence of a scalar massive field representing
the currently unexplained dark matter (DM) [33,34] and its physical properties
that are likely to be described by a spin-0 massive elementary particle
[35,36], whose existence has not yet been verified experimentally [37,38]. The
presence of such DM field and its possible coupling to spin-1 massive fields
of ordinary matter (OM) through chirality would allow both OM and DM to be
coupled. Moreover, as recently shown, in the nonrelativistic limit, DM may
have both scalar [39] and vector [40] components that could be coupled by
chirality. Further studies of these interesting phenomena are necessary and
they will be described elsewhere.

Finally, let us point out that the form of the dependence of the coupling
$\kappa$ on the chiral angles $\alpha$ and $\beta$ illustrates an important
result of our derivation that we postulate holds in all physical systems,
namely that _only differences in chiral bases are experimentally observable_.

##  5 Conclusions

The original Bargman-Wigner equations are generalized by taking into account
chiral symmetry for spin-1 massive fields. The generalization is based on the
irreps of the Poincaré group. By specified the chiral bases, the derived
chirial Bargmann-Wigner equations are reduced to the Proca-like equation,
which is shown to be coupled by chirality to an auxiliary equation for spin-0
massive field. The physical implications of this coupling are discussed in the
context of the scalar field to be either the Higgs field or a scalar massive
field describing dark matter. In both cases, new and interesting results are
likely to be obtained after more detailed investigations are performed.

##  6 References

## References

  * [1] V. Bergmann, E. Wigner, Proc. Natl. Acad. Sci. USA 34 (1948) 211
  * [2] E.P. Wigner, Ann. Math. 40, 149 (1939)
  * [3] Y.S. Kim and M.E. Noz, Theory and Applications of the Poincaré Group, Reidel, Dordrecht, 1986
  * [4] P.A.M. Dirac, Proc. Royal Soc. London 117 (1928) 610
  * [5] A, Proca, J. Physique et le Radiium 7 (1936) 347
  * [6] W. Rarita, J. Schwinger, Phys. Rev. 60 (1941) 61
  * [7] V.V. Dvoeglazov, Adv. App. Clifford Algebra 10 (2000) 7
  * [8] I. Sogami, Prog. Theor. Phys. 66 (1981) 303
  * [9] S.I. Kruglov, arXiv:hep-ph / 0507027v2 23 June 2006
  * [10] E. Marsh, Y. Narita, Front. Phys. 3 (2015) Article 82
  * [11] A.O. Barut, P. Cordero, G.C. Ghirardi, Phys. Rev. 182 (1969) 1844
  * [12] A.O. Barut, Phys. Lett. 73B (1978) 310
  * [13] W. Pfister, Nuovo Cimento A 108 (1995) 1427
  * [14] S.I. Kruglov, Ann. Found. L. de Broglie 29 (2004) 1005
  * [15] S.I. Kruglov, Phys. Let. B 718 (2012) 228
  * [16] D. Leiter, G. Szamosi, Let. Nuovo Cim. 5 (1972) 814
  * [17] K. Nozari, Chaos, Solitons & Fractals 32 (2007) 302
  * [18] Z. Tokuoka, Progr. Theor. Phys. 37 (1967) 581
  * [19] N.D.S. Gupta, Nucl. Phys. B4 (1967) 147
  * [20] A. Raspini, Fizika B5 (1996) 159
  * [21] S. Weinberg, Phys. Rev. 133 (1964) B1318
  * [22] S. Weinberg, Phys. Rev. 181 (1969) 1893
  * [23] R.H. Tucker, C.L. Hammer, Phys. Rev. D3 (1971) 2448
  * [24] V.V. Dvoeglazov, arXiv:hep-th/0208159v2 30 March 2003
  * [25] V.V. Dvoeglazov, Int. J. Mod. Phys.: Cnference Series 2 (2011) 121
  * [26] T.B. Watson, Z.E. Musielak, Int. J. Mod. Phys. A 35 (2020) 2050189
  * [27] O. Klein, Zeit. Phys. 37 (1926) 895
  * [28] W. Gordon, Zeit. Phys. 40 (1926) 117
  * [29] P. Renton, Electroweak Interactions, Cambridge Uni. Press, Cambridge, 1990
  * [30] G. Aad, et al., ATLAS Collaboration, Phys. Lett. B 716 (2012) 1
  * [31] S. Chatrchyan, et al., CMS Collaboration, Phys. Lett. B 716 (2012) 30
  * [32] G. Aad, et al., ATLAS Collaboration, arXiv: 1307.1432v1 [hep-ex] 4 July 2013
  * [33] K. Freeman, and G. McNamara, In Search of Dark Matter, Springer, Praxis, Chichester, 2006
  * [34] J.A. Frieman, M.B. Turner, and D. Huterer, Ann. Rev. Astr. Astrophys. 46 (2008) 385
  * [35] K. Sugita, Y. Okamoto, and M. Sekine, M., Int. J. Theor. Phys. 47 (2008) 2875
  * [36] R. Barbier, et al., Phys. Rep. 420 (2005) 1
  * [37] M. Ackermann, et al., Phys. Rev. Let. 107 (2011) 241302
  * [38] A. Ibarra, D. Tran, D. and C. Weniger, Int. J. Mod. Phys., 28 (2013) 1330040 (48pp)
  * [39] Z.E. Musielak, Int. J. Mod. Phys. A, 28 (2021) 2150042 (12pp)
  * [40] P. Adshead, and K.D. Lozanov, Phys. Rev. D, 103 (2021) 103501