\documentclass[runningheads,a4paper]{llncs}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{algorithm, algorithmic}
%\usepackage{natbib}

\newcommand{\OO}{\mathcal{O}}

\def\np{${\cal NP}$}
\def\real{\hbox{\rm\vrule\kern-1pt R}}
\def\nat{\hbox{\rm\vrule\kern-1pt N}}
\def\l{\ell}
\def\eps{\varepsilon}
\def\bigm{T}

\newcommand{\non}{\nonumber}
\newlength{\algowidth}
\setlength{\algowidth}{\textwidth}
\addtolength{\algowidth}{-2cm}
\newlength{\algowidthplus}
\setlength{\algowidthplus}{\textwidth}
\sloppy
\addtolength{\algowidthplus}{-15mm}

\def\ein{\mbox{}\qquad}
\def\einn{\mbox{}\qquad\qquad}
\def\einnn{\mbox{}\qquad\qquad\qquad}
\def\einnnn{\mbox{}\qquad\qquad\qquad\qquad}
\def\einnnnn{\mbox{}\qquad\qquad\qquad\qquad\qquad}
\def\einnnnnn{\mbox{}\qquad\qquad\qquad\qquad\qquad\qquad}

\def\ow{\mbox{$\overline{w}$}}
\newlength{\figwidth}
\setlength{\figwidth}{0.25\textwidth}
%\addtolength{\figwidth}{-1cm}

\newcommand{\ec}[2]
   { $ \begin{array}{c}
     #1 \\ #2
    \end{array} $}

\newcommand{\ncoppa}[2]{\genfrac{}{}{0pt}{1}{#1}{#2}}

\def\ol#1{\overline{#1}}
\def\erre{I\!\!R}
\def\l{\ell}
\def\eps{\varepsilon}
\def\km{k_{\max}}
\def\zz{\overline{z}}
\def\z{\underline{z}}
% whatever we will call this problem use \p

\def\Re{\mathbb{R}}
\def\Za{\mathbb{Z}}

\begin{document}

\title{Subset Weight Maximization with Two Competing Agents}
%\titlerunning{Subset Weight Maximization with Two Competing Agents}

\author{Gaia~Nicosia\inst{1} \and
Andrea~Pacifici\inst{2} \and
Ulrich~Pferschy\inst{3}
}

\institute{Dipartimento di Informatica e Automazione,
Universit\`a degli studi  ``Roma Tre'',
%via della Vasca Navale 79, 00146 Rome,
Italy,
\email{nicosia@dia.uniroma3.it}
\and
Dipartimento di Ingegneria dell'Impresa,
Universit\`a degli Studi di Roma  ``Tor Vergata'', %Rome,
Italy,
\email{pacifici@disp.uniroma2.it}
\and
Department of Statistics and Operations Research,
University of Graz,
%Universitaetsstr.~15, 8010 Graz,
Austria,
\email{pferschy@uni-graz.at}
}
\maketitle

\begin{abstract}
\noindent We consider a game of two  agents competing to add items
into a solution set. Each agent owns a set of weighted items and
seeks to maximize the sum of their weights in the solution set.
In each round each agent submits one item for inclusion in the
solution. We study two natural rules to decide the winner of each
round: Rule 1 picks among the two submitted items the item with
larger weight, Rule 2 the item with smaller weight. The winning item
is put into the solution set, the losing item is discarded.

For both rules we study  the structure and the number of efficient
solutions, i.e.\ Pareto optimal solutions.
% as used in multicriteria optimization.
For Rule 1 they can be characterized easily, while the
corresponding decision problem is NP-complete under Rule 2. We also
show that there exist no Nash equlibria. Furthermore, we study the
best-worst ratio, i.e.\ the ratio between the efficient solution
with largest and smallest total weight,
% (which can be seen as an analogon to the prize of anarchy)
and show that it is bounded by two
for Rule 1 but can be arbitrarily high for Rule 2.
Finally, we consider {\em preventive} or {\em maximin} strategies, which maximize the
objective function of one agent in the worst case, and {\em best response}
strategies for one agent, if the items submitted by the other agent
are known before either in each round (on-line) or for the whole
game (off-line).

\vspace*{1ex}
\noindent
\textbf{Keywords:} multi-agent optimization, %knapsack type problem,
games.
\end{abstract}


\section{Introduction}
\label{sec:intro}

We consider a multi-agent problem where agents compete to fill a
joint solution set with their items. We focus on the following
situation: There are two agents, each of them owning one of two
disjoint sets of weighted items. The agents have to select items
from their set for putting them in a common solution set. This
process proceeds in a fixed number of rounds. In every round each of
the two agents selects exactly one of its items and submits the item
for possible inclusion in the solution set. A central decision
mechanism chooses one of the items as ``winner'' of this round. The
winning item is permanently included in the solution set while the
losing item is permanently discarded. Each agent wants to maximize
its total solution value which is given by its own items' weights in
the solution set. The sets if items are known to both agents while
the submission of items in each round occurs simultaneously. Now the
problem is how to compute solutions which take into account each
agent's solution function, and that can be used to support the
negotiation among the agents.
%
%HERE AGAIN
Although the addressed problem does not come directly from a real
world application, it is such a natural and simple game (and yet not
trivial) to make its investigation interesting and stimulating.

%HERE
This problem can also be regarded as a single-suit card game in which
each of  two players chooses a card from its  hand. The highest (or
lowest) value card wins and each card can be used only once. In
\cite{SS98} the authors study a zero-sum game in which the cards are
submitted simultaneously and the players want to maximize the total
value of the won cards. In \cite{klw87,w05} the so called
\emph{whistette} game is addressed. There is a totally ordered suit
of  $2n$ cards, distributed between the two players. The player who
has the lead plays first on each trick. The player with the higher
card wins a trick and obtains the lead. Players want to maximize the
number of won tricks.

%HERE3, not very insightful
The problem here addressed is also related to seeds assignment in
team sport tournaments, e.g.\ chess leagues, where players of each
team are ordered and each player faces the opponent on the same
ordered position of the other teams` list. However, the ordering of
players may be restricted to obey an established ranking (e.g.\ ELO
points) to some extend. There the objective is to maximize the
number of wins while our problem aims at the maximization of the
total weight of all winning rounds.
% HERE AGAIN:
%
%Further relationships regard knapsack games \cite{l00} and auctions
%\cite{a06}.

%HERE removed:
%In our case, we have a unit size for the items and a special
%mechanism to decide which items fit, i.e.\ are accepted.
%
%Another class of problems related to ours are card games.  For
%instance in~\cite{SS98}, each of two players choses a card from
%their respective hands. The highest value card wins and each card
%can be used only once. Players are maximizing the total value of the
%won cards. The authors discuss the conditions under which a subgame
%perfect equilibrium exists.


% HERE AGAIN:
% WE ARE MISSING A MOTIVATION for studying the problem



\subsection{Formal Problem Setting}\label{sec:preliminaries}

In the following, $A$ resp.\ $B$ indicate the agents' names
each of them owning a set of $n$ items, where item $i$ has weight $a_i$ resp.\ $b_i$.
Sometimes we will identify items by their weight.
All information about the input list of items is public.

The game is performed over $c$ rounds.
In each round both of the two agents simultaneously submit one of their items,
say $a_i$ and $b_j$, in secret.
%003: changed from a_k, b_k, which would mean the k-th largest in BOTH sets.
We consider the two most natural rules for deciding which of the two submitted items
wins and is added to the solution set:
\begin{description}
\item[Rule 1:] if $a_i \geq b_j$ then A wins;\\[-2ex]
\item[Rule 2:] if $a_i \leq b_j$ then A wins.
%HERE3
\footnote{In case of a tie we assume that $A$ always wins. Two
analogous rules where $B$ wins all ties can be represented by
exchanging the roles of $A$ and $B$.}
\end{description}
Recall that in both cases the losing item is discarded and can not be submitted a second time.

Throughout this paper we assume the items to be sorted in decreasing order of weights,
i.e.\ $a_1 \geq a_2 \geq \ldots \geq a_n$ resp.\ $b_1 \geq b_2 \geq \ldots \geq b_n$.


%\medskip
This problem can be represented by a graph model. Each
agent's item is associated to a node of a weighted complete
bipartite graph $G = (V^A \cup V^B, E^A \mathbin{\dot{\cup}} E^B)$.
An arc $(i, j)$ belongs to $E^A$ or to $E^B$ depending on the winner
of a comparison of $a_i$ and $b_j$, which of course depends on the
applied selection rule.
\begin{description}
\item[]\emph{Rule 1}: arc $(i, j)$ with weight $w_{ij}= \max\{a_i, b_j\}$
belongs to $E^A$ if $a_i \geq b_j$, i.e.\ if $A$ wins,
otherwise it belongs to $E^B$;
\item[]\emph{Rule 2}: arc $(i, j)$ with weight $w_{ij}= \min\{a_i, b_j\}$
belongs to $E^A$ if $a_i \leq b_j$, i.e.\ if $A$ wins,
otherwise it belongs to $E^B$;
\end{description}
Every pair of items $(a_i, b_j)$ submitted simultaneously in one round
can be represented by an arc $(i,j)$ between the two corresponding nodes.
Hence, after completing $c$ rounds any solution may be represented
as a $c$-matching $M$ on $G$.
Recall that a $c$-matching assigns $c$ nodes in $V^A$ to $c$ nodes in $V^B$.
The total weight of items in the solution for agent $A$ is given by
%$W^A=
$w^A(M) = \sum_{ij\in M\cap E^A} w_{ij}$ and that of $B$ by
%$W^B=
$w^B(M) = \sum_{ij\in M\cap E^B} w_{ij}$.
Thus, determining a global optimum maximizing the sum of the two agents' weights
can be done in polynomial time by solving
a weighted cardinality assignment problem~\cite{dm97}.
%HERE
Indeed, in the next section, we show  that the global optimum under
both rules can be found in an straightforward way, without recurring
to matching techniques.

% THIS COULD BE REMOVED IF WE HAVE ROOM PROBLEMS.
Note that matching problems on graphs with edges partitioned into
two sets are addressed in~\cite{bluered}.


\section{Structure of Efficient Solutions}
\label{sec:structure}

In this section we  investigate the solution structure in an
offline perspective, i.e.\  we consider the problem from a
centralized and static point of view and  look for Pareto efficient
solutions. Then, we show that under both rules, no Nash equilibria
exist, in general.

\subsection{Pareto Efficient Solutions}
\label{sec:pareto}

Using the same terminology as in multicriteria optimization
%HERE3 reference eliminated
%(see e.g.\ \cite{eh05})
a solution $M$ is called \textit{Pareto
efficient} or simply \textit{efficient} or \textit{nondominated} if
there exist no solution $M'$ such that $w^A(M) \leq w^A(M')$,
$w^B(M) \leq w^B(M')$ and  $w^A(M)+w^B(M) < w^A(M')+w^B(M')$.

%\subsubsection{Efficient solutions: Rule 1}
%Hereafter, we discuss the complexity of finding efficient solutions
We start our investigation %Sherlock!
with Rule~1 and notice that in this case each agent always submits
its $c$ largest items.
So, in the remainder of this section, without loss of generality,
under Rule 1 we assume $c = n$.

\begin{theorem} Under Rule 1, there are at most $c+1$ efficient solutions.
These can be computed in polynomial time.
\end{theorem}

\begin{proof}
%HERE. ULRICH CHECK!
% 002
%First, observe that no instance can have $c+1$ efficient solutions:
%in fact, if one agent, say $A$,
%wins $0$ rounds then $b_i > a_j$ for all $i, j$ %and there is only one solution.
%CHANGED AGAIN
%We restrict our attention  to the non-trivial case $k\geq 1$.
%SHOULDNT IT BE  $c+1$ SOLUTIONS? WHAT ABOUT THE CASE $k=0$ ?
%I PROPOSE THE FOLLOWING SENTENCE:
%003 plugged in again :-)
Suppose that a feasible solution exists such that agent $A$ wins $k$
rounds and therefore $B$ wins the remaining $c-k$ rounds. W.l.o.g.\
we assume $a_1>b_1$ (otherwise we can exchange the roles of $A$ and
$B$). Since $a_1$ may win in any case, if $A$ is rational there is
$k\geq 1$, otherwise, if $A$ ``voluntarily'' decides to lose all rounds by
submitting at each round an item smaller than the corresponding $B$
item, $k$ may be equal to 0.

By a simple pair interchange argument it  is easy to see that in
this case the solution where $A$ ($B$ resp.) wins with its heaviest
$k$ ($c-k$ resp.) items is also feasible. Clearly, it is also
nondominated. If $k\geq 1$, the structure of the resulting solution
is such that  item $a_i$ is matched to $b_{c-k+i}$ for $i=1,\ldots,
k$, and to $b_{i-k}$ for $i=k+1,\ldots, c$. Otherwise, we have an
additional efficient solution with $w^A=0$ and $w^B=\sum_{i=1}^c
b_i$.

Computing the solution values for all  $c+1$ efficient solutions can
be done in linear time by one scan through the list of items after
sorting the items. Giving also the corresponding pairs of items as
output would require $O(n^2)$ time.

\end{proof}

% 003
%PLEASE CHECK THIS
%Note that $A$ might lose ``voluntarily''  all rounds by submitting
%items smaller than $a_c$. This would generate an additional
%efficient solution with $w^A=0$ and $w^B=\sum_{i=1}^c b_i$, but as
%pointed out above for Rule 1 it is justified to exclude this
%strictly detrimental strategy from consideration.
%

\smallskip
A straightforward consequence of the above result is that, finding
the global optimum, i.e.\ the solution $M^*$ for which
$w^A(M^*)+w^B(M^*)$ is maximum, can be done in a simple way in
polynomial time also without solving a matching  problem, since
$M^*$ is a Pareto efficient solution.

%\medskip
Turning to Rule 2, we observe that it is not a trivial task to
select the ``best'' $c$  items to submit among the $n$ available.
Picking only large items may results in too many losses, a
restriction to the smallest items increases the chances to win many
rounds but the gain from these victories may be quite small. Hence,
we first restrict our attention to the case $c=n$. In this case we
can show the following results.
%The following example shows that there are instances with exponentially many efficient solutions.

\begin{theorem}\label{th:expefficient}
Under Rule 2, there can be an exponential number of efficient solutions for $c=n$.
\end{theorem}

Consider the following example for some small $\eps>0$:
\begin{example}\label{ex:expefficient}
$$
\setlength{\arraycolsep}{1ex}
\begin{array}{|c|c||c|c||c|}
\hline
\multicolumn{2}{|c||}{\mbox{agent } A}&\multicolumn{2}{c||}{\mbox{agent } B}&\\
\hline
a_1 & 0 & b_1 & \eps&\\
a_i & 2^{i-2} & b_i &a_i+\eps & i=2,\ldots, c\\
\hline
\end{array}
$$
%$$%\begin{array}{l}
%a_1 = 0; \ a_i = 2^{i-2} \quad   i = 2, \ldots, c;\\
%b_j = a_j + \epsilon   \quad j =  1, \ldots, c.
%\end{array}$$
For any set $S \subseteq \{2, \ldots, c-1\}$ consider the solution $M$ where
an item $a_i$ wins and, at the same time, $b_i$ loses if and only if $i\in S \cup
\{1\}$.
% 002
%HERE WE CHOOSE AN INCREASING ORDER OF ITEMS!
It is always possible to construct such an $M$: clearly, $a_1$ always wins; then, if $i\in S$, $a_i$ is matched to $b_i$, else ($i\not\in S$) $a_i$ is matched to some $b_j$, with $j < i$, $j\not\in S$. In $M$, $a_1$ is matched to $b_1$ or $b_c$ and $a_c$ is always losing.

Neglecting the $\eps$ values, the sum of the weights
$w^A(M) + w^B(M)$ is constant and equals $2^{c-1} - 1$.
Therefore, for any possible choice of $S$, it is possible to obtain an efficient solution
% added 003
since the resulting values of $w^A(M)$ are all different.
Thus, there are exponentially many efficient solutions.
\end{example}

%\medskip
We now show that, under Rule~2, the problem of deciding whether a
certain combination of weights for agents  $A$ and $B$ can be
reached is \np-complete by reduction from {\sc Partition}. This
implies that finding efficient solutions under Rule~2 is in general
an \np-hard task.

Let the decision problem be defined as follows.
\begin{quote}
%\noindent
{\sc Subset Weight Problem} (SWP):\\
{\bf Instance}: positive integers $a_i$ and $b_i$, $i = 1,\ldots,
n$; two positive values  $W^A$ and $W^B$.\\
{\bf Question}: Is there a solution (matching) $M$ such that $w^A(M) \geq W^A$
and $w^B(M) \geq W^B$?
\end{quote}

\begin{theorem}
{\sc Subset Weight Problem} is (binary) \np-complete.
\end{theorem}

\begin{proof}
Consider an instance $I$ of {\sc Partition}
with integer valued items $\{ v_1, v_2, \ldots, v_n \}$ and $\sum_{i=1}^n v_i = V$.
Assume $v_1 < v_2 < \ldots < v_n$.

For $\bigm > v_n$ and $ \eps < 1/(n+1)$, build an instance $I_{SWP}$
of {\sc Subset Weight Problem} as follows:
$$
(I_{SWP}) \quad
\begin{array}{l}
a_0 = \bigm, \quad b_0 = \eps, \\
a_i = v_i, \ \quad  b_i = v_i + \eps,  \quad  i = 1, \ldots, n,\\
W^A = W^B = \frac{V}{2}.
\end{array}
$$

\medskip
Let $I$ be a YES-instance of {\sc Partition}.
Then it is easy to build a solution $M$ of $I_{SWP}$ such that  $w^A(M)= V/2$ and
$w^B(M) \geq V/2$.
Let $S \subseteq \{ 1, 2, \ldots, n \}$ be such that $\sum_{i \in S} v_i = V/2$ and
$\bar S = \{ 0, 1, \ldots, n\}\setminus S$.
The required solution $M$ is given as follows:
Each item $i$ of $A$ with $i\in S$ is matched to the corresponding item $i$ of $B$,
while each item $j$ of $B$ with $j\in \bar S$ is matched to
$$\arg\min\{a_h \mid h \in \bar S, a_h > b_j \}.$$
Clearly, the two agents total weights are:
$w^A(M)= \sum_{i \in S} a_i= V/2$ and
$w^B(M)= \sum_{i \in \bar S} b_i \geq V/2$.

\medskip
Now, let $I_{SWP}$ be a YES-instance of {\sc Subset Weight Problem} and $M$ be a solution of $I_{SWP}$
such that $\bar S \subseteq \{0, 1, 2, \ldots, n \}$ is the set of
``winning'' items of agent $B$.
Note that $0\in \bar S$, since item 0 of $B$ always wins.
So,
$$w^B(M) = \sum_{i \in \bar S} b_i =\sum_{i \in \bar S} a_i + \eps \geq V/2$$
and $w^A(M)  \geq V/2$.
Note that, since each winning item $i$ of $A$ is matched to a losing
item of $B$ with larger weight, the total weight $L^B$ of the
``losing'' items of agent $B$ is such that
$L^B = \sum_{i \in S}b_i \geq w^A(M) \geq V/2 $.
Since, $L^B + w^B(M)= V + (n+1)\eps$, the $v_i$ are all integers and  $\eps <1/(n+1)$,
then $\sum_{i \in S} v_i=\sum_{i \in \bar S} v_i=V/2$.
\end{proof}


Observe that the above proof  shows that even if $c=n$, i.e.\ the
items to be submitted must not be selected, the problem is \np-hard.

Although finding efficient solutions under Rule 2 is \np-hard, the
global optimum $M^*$ can  be found in polynomial time using matching
techniques \cite{dm97} as already mentioned in
Section~\ref{sec:preliminaries}. However, it is easy to see that for
any value of $c \leq n$, we may compute a global optimal solution
in a straightforward way by setting $M^*=\{(a_1,b_1), (a_2,b_2),
\ldots, (a_c,b_c) \}$.

%do we need explanations?


\subsection{Nash Equilibrium}
\label{sec:nash}

It is easy to show that, under both rules, no Nash equilibria exist,
except for trivial instances where only one Pareto optimum exists. %DO WE NEED A FORMAL PROOF?
The following example presents an instance in which there are no Nash equilibria.
\begin{example}\label{ex:nonash}
$$
\setlength{\arraycolsep}{1ex}
\begin{array}{|c|c||c|c|}
\hline
\multicolumn{2}{|c||}{\mbox{agent } A}&\multicolumn{2}{c|}{\mbox{agent } B}\\
\hline
a_1 & 10 & b_1 & 12\\
a_2 & 5 & b_2 & 6\\
\hline
\end{array}
$$

There are $c=n=2$ rounds. Table \ref{nonash} gives the normal-form
representations of the game under the two rules. Assume, under
Rule~1, that $A$ submits $a_1$ and $a_2$ in the first and second
round, respectively. Then the best sequence for $B$ is $\langle
b_1,b_2 \rangle$. Clearly, when $B$ submits the latter sequence, $A$
changes its own, by swapping $a_1$ with $a_2$. So, $A$'s strategy
$\langle a_1,a_2 \rangle$  is not in a Nash equilibrium. An
analogous reasoning applies for the only other possible sequence for
$A$, $\langle a_2,a_1 \rangle$. So, under Rule~1, no Nash
equilibrium exists.
%
The same argument applies for Rule~2.
\end{example}
%
\begin{table}[htbp]
\begin{center}
{\footnotesize
\begin{tabular}{c|c|c}
 & $\langle b_1,b_2 \rangle$  &  $\langle b_2,b_1 \rangle$   \\ \hline
 $\langle a_1,a_2 \rangle$ & 0,18 & 10,12  \\ \hline
 $\langle a_2,a_1 \rangle$  & 10,12 & 0,18  \\
 \hline
  \end{tabular}
%
\quad \quad \quad
%
\begin{tabular}{c|c|c}
 & $\langle b_1,b_2 \rangle$  &  $\langle b_2,b_1 \rangle$   \\ \hline
 $\langle a_1,a_2 \rangle$ & 15,0 & 5,6  \\ \hline
 $\langle a_2,a_1 \rangle$  & 5,6 & 15,0  \\
 \hline
  \end{tabular}
  }
\end{center}
\caption{Payoffs of agents $A$ and $B$ with data of
Example~\ref{ex:nonash} under Rule 1 and 2.}\label{nonash}
\end{table}


\vspace*{-7mm}

\section{Best-Worst Ratio}
\label{sec:bestworst}

%HERE
The {\em price of anarchy}  is usually defined as the worst possible
ratio between the value of the global (social) optimum and the value
of a solution derived by a selfish optimization.
In this context, we adopt a slightly different definition, considering the ratio between
the best and worst values of two efficient solutions, and we denote
it as the  \emph{best-worst ratio} (BWR). Formally,
$$ \mbox{BWR} = \max_{M \in \mathcal{E}} \left\{
\frac{w^*}{w^A(M)+w^B(M)}\right\},$$ where $\mathcal{E}$ is the set
of efficient solutions and $w^*$ is the global optimum value.

It will be
shown that this ratio is equal to $2$ in case of Rule 1, while it
can be arbitrarily high in case of Rule 2.


\begin{theorem}\label{th:anarchy1}
The best-worst ratio under Rule 1 is $2$.
\end{theorem}

\begin{proof}
Let $X=\{ a_1, a_2, \ldots, a_c\} \cup \{ b_1, b_2, \ldots, b_c\}$
and number the items of $X$ in non-increasing order of weights,
$X=\{ x_1, x_2, \ldots, x_{2c}\} $.
Obviously, the global optimum value is bounded from above by
the sum of the $c$ largest items, i.e.\ $w^* \leq \sum_{i=1}^c x_i$.
On the other hand, even the value of the efficient solution $\bar M$
with the {\em worst} global value can be bounded from below.
% 002
In fact, in $\bar M$, the set $X$ can be partitioned into the two
sets $X^V$ and $X^L$ of winning and losing items. Clearly $|X^V| =
|X^L| = c$. Since, under Rule~1, each winning item is matched to an
item with smaller weight, then $w(X^V) \geq w(X^L)$. Therefore
$w^A(\bar M)+w^B(\bar M) = w(X^V) \geq w(X)/2$.
%Consider that at least one between every pair of items $x_{2i-1}, x_{2i}$,
%$i=1,\ldots,c$ must contribute to the global solution value.
%I THINK THIS NEEDS SOME EXPLANATION
%\sum_{i=1}^{c} x_{2i-1} $.
%Therefore, since $\sum_{i=1}^{c} x_{2i-1} \geq
Since $w(X) \geq w^*$, the statement follows.
\end{proof}

To show that the bound of $2$ can be reached consider the following
example for a large constant $\bigm$:
\begin{example}\label{ex:anarchy1}
$$
\setlength{\arraycolsep}{1ex}
\begin{array}{|c|c||c|c|}
\hline
\multicolumn{2}{|c||}{\mbox{agent } A}&\multicolumn{2}{c|}{\mbox{agent } B}\\
\hline
a_1 & \bigm & b_1 & \bigm - 1 \\
a_2 &  2 & b_2 & 1 \\
\hline
\end{array}
$$
Let $c=2$.
Agent $A$ submits items $\langle a_1, a_2 \rangle$.
There are only two efficient solutions:
If $B$ submits $b_1$ first and $b_2$ second thus losing both rounds,
the global solution value is $\bigm+2$.
If $B$ exchanges the order of its submissions
then $A$ wins the first round and $B$ the second yielding a global solution
value of $2\bigm-1$.
Therefore, for $\bigm$ tending to infinity,
the best-worst ratio tends to $2$.
\end{example}

\begin{theorem}\label{th:anarchy2}
The best-worst ratio under Rule 2 can be arbitrarily high.
\end{theorem}

Consider the following trivial example:
\begin{example}\label{ex:anarchy2}
$$
\setlength{\arraycolsep}{1ex}
\begin{array}{|c|c||c|c|}
\hline
\multicolumn{2}{|c||}{\mbox{agent } A}&\multicolumn{2}{c|}{\mbox{agent } B}\\
\hline
a_1 & \bigm & b_1 & \bigm+1\\
a_2 & 2 & b_2 & 1\\
\hline
\end{array}
$$
There is only one round.
If agent $B$ submits $b_1$ it will lose in any case.
Therefore, any selfish strategy of $B$ will submit $b_2$ gaining in any case $w^B=1$,
while agent $A$ will lose and have $w^A=0$.
A global optimum would submit $a_1$ and $b_1$ yielding a total weight of $\bigm$.
\end{example}


\section{Strategies of Agents}
\label{sec:strategies}

In this section we address the problem of devising a
\emph{strategy}, that is an algorithm, that suggests an agent which
item to submit at each round, in order to maximize the agent's
weight under different information scenarios.

In particular, in the {\em off-line} case, where an agent, say $B$,
knows all $c$ submissions of $A$ before deciding on its $c$
submissions, the problem of selecting the best $c$ items for $B$ is
easy under both rules.
%
Take the bipartite graph $G$ defined in
Section~\ref{sec:preliminaries} and restrict $V^A$ to the $c$ nodes
representing the items submitted by $A$.
%$V^B$ is restricted to the $c$ items of $B$ with largest weight.
%NO: this is only for rule 1
Now compute a maximum weight $V^A$-perfect matching, where the
weight of every arc in $E^A$ is set to $0$ while arcs in $E^B$ keep
the weight of the corresponding winning item in $B$.
%
Actually,  such $c$-matchings can be computed through simple greedy
algorithms depending on the  rule in force.


The above remark implies that, in the {\em on-line} case in which an
agent does not know in advance the sequence of items submitted by
the other, no strategy of $B$ can guarantee a limited
\emph{competitive ratio} \cite{borodin}, since $A$ can always
minimize $B$'s weight by maximizing its own weight. For instance,
consider the problem given in Example \ref{ex:nonash}, whatever the
strategy of $B$ is,  under Rule 2 in the worst case, $w^B=0$, which
makes the competitive ratio unbounded. (Under Rule 1, the same
example applies by exchanging the role of the two agents).


In what follows we consider the scenario under Rule 1  where agent
$B$, gets to know the item submitted by agent $A$ in every round
{\em before} making its own move. We will try to answer the question
how $B$ should select its items under such an advantageous asymmetry
of information. In this particular context, the  strategy adopted by
agent $B$ is referred to as \emph{best response} strategy.

Somewhat surprisingly, it will  turn out that for Rule~2 an optimal
best response strategy can be found while for Rule~1 the existence
of such a strategy can be ruled out.


\subsection{Best Response Strategies for
Rule~1}\label{sec:bestresponseR1}

We now consider the scenario where $B$ only knows the submission of
$A$ in the current round and has to react immediately before both
agents move on to the next round.
% 002
%PLEASE CHECK THIS:
If $B$ knows in advance which items $A$ would submit
(for instance when
$n = c$, or
$A$ behaves in a rational way
and only uses its largest items $a_1, \ldots, a_c$)
%
the problem is
 easy. By solving the matching problem described above, $B$
knows the optimal answer to every item submitted by $A$. The
ordering of these submissions does not matter, since  $B$ simply
uses the answer indicated by the optimal matching to every item of
$A$.

\medskip
The problem becomes more difficult if we cannot restrict the choices
of $A$ but have to assume that any item $i\in\{1,\ldots,n\}$ could
be submitted by $A$. In this case, there is no optimal strategy for
$B$. Indeed we can show that no strategy of $B$ can have a
competitive ratio  (compared to the best off-line strategy) better
than $1.618\ldots$ . On the other hand, we will show that a simple
greedy-type algorithm has a worst-case competitive ratio of $2$.

\begin{theorem}\label{th:onlinelower}
No on-line strategy of agent $B$ against an arbitrary strategy of agent $A$ can have a
competitive ratio smaller than $\frac{\sqrt{5}+1}{2}=1.618034\ldots$ under Rule 1.
\end{theorem}

Consider the following example:
\begin{example}\label{ex:bestresponselower}
$$
\setlength{\arraycolsep}{1ex}
\begin{array}{|c|c||c|c|}
\hline
\multicolumn{2}{|c||}{\mbox{agent } A}&\multicolumn{2}{c|}{\mbox{agent } B}\\
\hline
a_1 & 2 & b_1 & 1+\eps\\
a_2 & 1 & b_2 & y \\
a_3 & \eps & b_3 & \eps\\\hline
\end{array}
$$
There are $c=2$ rounds and parameter $y$ is chosen such that $2\eps <y < 1$.
We will consider two (suboptimal) strategies of agent $A$:
In both cases $A$ starts by submitting $a_3$.
In strategy $S_1$ it is followed by $a_1$, in strategy $S_2$ by $a_2$.

Given the first item $a_3$ there are only two ways for agent $B$ to react:

In Case~1, $B$ submits $b_2$ thus winning this round.
Against strategy $S_1$, $B$ loses the second round
and the worst-case total weight for Case~1 is $W^B_1=y$.

In Case~2, $B$ submits $b_1$ and wins again.
But against strategy $S_2$, $B$ loses again the second round and
in the worst-case stops with a total weight $W^B_2=1+\eps$.

\medskip
However, an optimal off-line strategy of $B$ against $S_1$ would be
$\langle b_1,b_2 \rangle$
gaining a weight of $W^*_1=1+\eps$, while against $S_2$ the submission of
$\langle b_2 ,b_1 \rangle$
would yield $W^*_2=y+1+\eps$.

%Putting these values
Altogether we get a lower bound for the worst-case competitive ratio
of
$$ \max_{2\eps <y < 1}\ \min_{i=1,2} \left\{\frac{W^*_i}{W^B_i}\right\}
= \max_{2\eps <y < 1}\ \min \left\{\frac{1+\eps}{y},\; \frac{y+1+\eps}{1+\eps}\right\}.$$
Clearly, this maximum is attained if the expressions of the minimum are equal.
An elementary calculation yields $y=(1+\eps)\frac{\sqrt{5}-1}{2}$ .
Plugging in this value of $y$ in the above equation yields
$\frac{\sqrt{5}+1}{2}$ as  a lower bound for the competitive ratio
and proves Theorem~\ref{th:onlinelower}.

%003 DO WE NEED THIS:
%(*** 002 would shorten it as follows ***):
In the above analysis $B$ submits its $c=2$ largest items;
however it is not hard to see that the same result is attained
when $B$ may decide to submit $b_3$.
%AND SKIP THE REST:
%Note that it does not change the construction if $B$ avoids the decision
%between $b_1$ and $b_2$ by deviating from its $c$ largest items and submitting $b_3$.
%Against strategy $S_2$ it would gain $W^B_2=y$ which adds a ratio of
%$\frac{y+1+\eps}{y}$ to the minimum.
%But this expression is strictly larger than $\frac{1+\eps}{y}$.
\end{example}


\smallskip
The following greedy-type algorithm tries to win against  every item
submitted by $A$ with the largest item still available. If this
fails and a loss cannot be avoided in the current round the smallest
remaining item is submitted.

\begin{algorithm}[h]
\caption{Algorithm for agent $B$ responding to the submissions of agent $A$ under Rule~1.} \label{alg:resp}
\vspace{0.2cm}
\textsc{Greedy Response Rule~1}
\begin{algorithmic}[1]
\STATE $f\leftarrow 1$ \COMMENT{index of largest available item}
\STATE $\l\leftarrow c$ \COMMENT{index of smallest available item}
\REPEAT
\STATE $A$ submits item $a'$
\IF {$b_f > a'$}
\STATE $B$ submits $b_f$ and wins
\STATE $f\leftarrow f+1$
\ELSE
\STATE $B$ submits $b_\l$ and loses
\STATE $\l\leftarrow \l-1$
\ENDIF
\UNTIL{$f<\l$} \COMMENT{all $c$ rounds finished}
\end{algorithmic}
\end{algorithm}

\begin{theorem}
Algorithm \textsc{Greedy Response Rule~1} has a tight competitive ratio of $2$.
\end{theorem}

\begin{proof}
Let $S^A$ be the complete set of items submitted by $A$.
At the end of the execution of \textsc{Greedy Response Rule~1}
agent $B$ has added its $k$ largest items into the solution and reached a total weight of
$W^B$ ($k=f-1$ at the end of the algorithm).

It is easy to see that an optimal off-line solution against the same
set $S^A$ will always consist of the largest $k^*$ items with
$k^*\geq k$. In this optimal strategy the items  in set $D^B=\{k+1,
\ldots, k^*\}$ of $B$ all win against some items in $S^A$. This
means that at least the smallest items in $S^A$ must be potential
losers against $D^B$. Let $j$ be the index of the $c-(k^*-k-1)$
largest item in $S^A$. Then we have $b_{k+1} > a_j$.

Considering the item $b_f=b_\l$ submitted by $B$ in the last round of the game
there are two cases to distinguish.

{\bf Case 1}: $b_f$ loses. Since $b_f=b_{k+1}$ would win against any
of the $k^*-k$ smallest items in $S^A$, these must have been
submitted by $A$ before. Moreover, at the rounds where these items
were submitted, item $b_{k+1}$ was still available and would yield a
win for $B$. By definition of \textsc{Greedy Response Rule~1} some
other item of $B$ must have won these rounds. Therefore, the total
number of wins for $B$ must be at least $k^*-k$, i.e.\ $k\geq
k^*-k$, which proves the statement of the theorem.

{\bf Case 2}: $b_f$ wins. In all rounds, in which $A$ submitted one
of the $k^*-k$ smallest items in $S^A$, item $b_f$ was still
available and would have won against these items. As above, by the
definition of \textsc{Greedy Response Rule~1} some other item of $B$
must have won these rounds and again $k\geq k^*-k$.

\medskip
To show that the bound of $2$ is tight consider the simple Example~\ref{ex:wcgreedy}.
\end{proof}

\begin{example}\label{ex:wcgreedy}
$$
\setlength{\arraycolsep}{1ex}
\begin{array}{|c|c||c|c|}
\hline
\multicolumn{2}{|c||}{\mbox{agent } A}&\multicolumn{2}{c|}{\mbox{agent } B}\\
\hline
a_1 & 1+\eps & b_1 & 1+2\eps\\
a_2 & 1-\eps & b_2 & 1 \\
\hline
\end{array}
$$

There are $c=2$ rounds.
Agent $A$ submits $a_2$ in the first round.
\textsc{Greedy Response Rule~1} reacts with $b_1$
and loses the second round ($a_1$ against $b_2$) gaining a total weight of $1+2\eps$.

An optimal off-line strategy of $B$ would react with $b_2$ in the first round
thus winning both rounds and gaining $2+2\eps$.
\end{example}

\subsection{Best Response Strategies for Rule~2}\label{sec:bestresponseR2}

Even under Rule~2, if $B$ knows in advance which items $A$ would submit (e.g., when $n = c$), it is easy to devise an optimal response algorithm using the same matching argument holding for Rule~1.

%HERE3, comment to the referee:
%It is not enough to chose the largest winner, when possible.
%You also have to chose the "correct" loosing item, which is not so trivial.
%Therefore, I would not change anything here.
As in Rule 1, the following greedy-type  algorithm for Rule 2 tries
to win against every item submitted by $A$ with the largest possible
winning item. If no such item exists, a losing item is determined
which can not worsen the remainder of the solution for $B$.
% 003 IS THAT OK WITH YOU? (***002: OK!***)
To avoid a tedious special treatment of ties we  will assume in this
subsection that all $2n$ items have different weights.

\begin{algorithm}[h]
\caption{Algorithm for agent $B$ responding to the submissions of agent $A$ under Rule 2.} \label{alg:resp2}
\vspace{0.2cm}
\textsc{Greedy Response Rule~2}
\begin{algorithmic}[1]
\STATE $R^A\leftarrow \{a_1, \ldots, a_n\}$ \COMMENT{set of remaining items for $A$}
\STATE $R^B\leftarrow \{b_1, \ldots, b_n\}$ \COMMENT{set of remaining items for $B$}
\REPEAT
\STATE $A$ submits item $a'$, remove $a'$ from $R^A$
\STATE $b_{\min}\leftarrow \min\{b_i\mid b_i\in R^B\}$
\IF {$a'> b_{\min}$}
\STATE $b_{win} \leftarrow \max\{b_i\mid b_i<a', b_i \in R^B\}$
\STATE $B$ submits $b_{win}$ and wins, remove $b_{win}$ from $R^B$
\ELSE
\STATE $A_j \leftarrow \{a_i\mid a_i \geq b_j, a_i\in R^A\}, \ j=1,\ldots,|R^B|$
\STATE $B_j \leftarrow \{b_i\mid b_i \geq b_j, b_i\in R^B\}, \ j=1,\ldots,|R^B|$
\STATE determine the minimum index $\l\geq 1$ such that $|A_\l| < |B_\l|$\label{alg:bell}\\
%$|\{a_i\mid a_i \geq b_\l, a_i\in R^A\}| < |\{b_i\mid b_i \geq b_\l, b_i\in R^B\}|$
\STATE$B$ submits $b_\l$ and loses, remove $b_\l$ from $R^B$
\ENDIF
\UNTIL{all $c$ rounds finished}
\end{algorithmic}
\end{algorithm}

\begin{theorem}
Algorithm \textsc{Greedy Response Rule~2} yields the optimal off-line solution under Rule 2.
\end{theorem}

%THE PROOF IS NOT "WEAK" ANY LONGER :)

\begin{proof}
We will consider round 1, where agent $A$ submits $a'$,
and show that also an optimal algorithm \textsc{Opt} can not do better than
\textsc{Greedy Response Rule~2} and that the later does not diminish the range of options for
an optimal strategy in the subsequent rounds.
Repeating this argument over all rounds yields the statement of the theorem.


{\bf Case 1}: $B$ wins. What are the alternatives for \textsc{Opt}?
If \textsc{Opt} submits an item $b_j < b_{win}$ it earns a smaller
weight in round 1. In contrary to \textsc{Greedy Response Rule~2} it
can use $b_{win}$ to win in one of the subsequent rounds. However,
in this case \textsc{Greedy Response Rule~2} could submit $b_j$ in
this future round and win as well since $b_j < b_{win}$. Obviously,
the total weight of these two rounds would be the same for both
algorithms.

If \textsc{Opt} chooses to submit an item $b_k \geq a'$ and loose ``voluntarily'',
it can again use $b_{win}$ to win in a later round.
\textsc{Greedy Response Rule~2} might be forced to loose in that round, but again the
two algorithms end up with the same total weight for these two rounds.

{\bf Case 2}: $B$ looses. First, let us note that in the special
case $b_1 > a_1$ (considering only items in $R^A$ and $R^B$)
\textsc{Greedy Response Rule~2} will submit $b_\l=b_1$. Since $b_1$
cannot win in any round, it clearly cannot violate optimality to
submit $b_1$ in a round which $B$ will lose in any case.

% 003 some changes here
%I TRIED TO IMPROVE, NOT SURE IF SUCCESSFUL
%(*** 002: I think it's much clearer now ***)
Also for $b_1 < a_1$ index $\l$ is well defined.
Note that $b_j \in B_j,\;\forall\; j$.
For $j=1$ the defining inequality in line~\ref{alg:bell} is clearly violated
since $A_1 \supseteq \{a_1\}$ and $B_1=\{b_1\}$.
Since $a' < b_{\min}$ and $|R^A|=|R^B|$, an index $\l$ satisfying $|A_\l| < |B_\l|$
will be determined for $b_{\min}$ at the latest.

%Now for the general case
%and $b_{\l-1}$ has exactly the same set of possible items to beat as $b_\l$.
Note that in the ordering of the items in $R^A\cup R^B$ there must occur an item $b_{\l-1}\in R^B$ directly before $b_\l$.
Otherwise, since there was $|A_{\l-1}| \geq |B_{\l-1}|$, one (or more) items of $R^A$ plugged in between $b_{\l-1}$ and $b_\l$
would not lead to the required change in the balance of cardinalities.
This means that $A_{\l-1}=A_\l$.

Now consider that $B_{\l-1}$ can be matched to win against $A_{\l-1}$.
This can be seen by a simple scan through the items in $R^A\cup R^B$ in decreasing order,
starting with $a_1$ being matched to $b_1$.
A failure of such a scan would immediately yield a new smaller value of $\l$.
In fact, the existence of such a matching follows from Hall's marriage theorem.
Clearly, also every subset of items of $A_{\l-1}$ ($=A_\l$) can be matched to be beaten
by the corresponding number of items of $B_{\l-1}$
(e.g.\ by taking the smallest items in $B_{\l-1}$).

On the other hand, it follows from the definition of $|A_\l|$ and $|B_\l|$
that there are more items in $R^B$ with weight larger or equal $b_\l$ than in $R^A$.
Therefore, it is impossible for any strategy that {\em all} items in $B_\l$
will win against some items in $R^A$, the items in $A_\l$ being the only candidates for losers.

Since it is impossible for agent $B$ to beat all items in $A_\l$, but every strict subset of $A_\l$
can be beaten also by items in $B_{\l-1}$, the removal of $b_\l$ does not change the options of \textsc{Opt}
in any subsequent round.
\end{proof}


\section{Conclusions}\label{sect:concl}
%
% 002
This work puts several directions forward for future research. One
is the design of  algorithms to efficiently enumerate all
Pareto-optimal solutions under Rule~2.
Another is to extend our results to further relevant %worthwhile
rules controlling how an agent's item is added to the solution set.
For instance, the case when losing items are not discarded but are
\emph{reusable} (meaning that an agent can submit them in successive
rounds), seems particularly significant.
%HERE
Furthermore, it would be interesting to investigate the problem
where both agents ignore the weights of the items of the other
agent.


%\setlength{\bibsep}{0.3mm}
\begin{thebibliography}{99}

% HERE AGAIN
%\bibitem{a06}{
%G. Aggarwal, J. D. Hartline. Knapsack auctions, Proceedings of the
%17th annual ACM-SIAM Symposium on Discrete Algorithm, pp.
%1083--1092, 2006. }

\bibitem{borodin}{A. Borodin, R. El-Yaniv.
  Online Computation and Competitive Analysis,
   Cambridge University Press, 1998.}

\bibitem{dm97}{M. Dell'Amico, S. Martello. The $k$-cardinality assignment problem,
Discrete Applied Mathematics,  76, pp. 103--121, 1997.}

%\bibitem{eh05}{M. Ehrgott.
%Multicriteria Optimization, Springer, 2005.}

%THIS CITATION IS WRONG
%\bibitem{fy04}{M. Fujimoto, T. Yamada.
%An exact algorithm for the knapsack sharing problem with common
%items, European Journal of Operational Research,  171(2), pp.
% 693--707, 2006.}
%
%\bibitem{hifi2005}{M. Hifi, H. M'Hallab, S. Sadfi. An exact algorithm for
%the knapsack sharing problem, Computers \& Operations Research,
% 32(5),  pp. 1311--1324, 2005.}

\bibitem{klw87}{J. Kahn, J. C. Lagarias, H. S. Witsenhausen. Single-Suit
Two-Person Card Play. International Journal of Game Theory, 16(4),
pp. 291--320, 1987.}

%HERE AGAIN
%\bibitem{l00}{V. Liberatore.
%Scheduling Jobs Before Shut Down, Lecture Notes in Computer Science,
%1851, Algorithm Theory - SWAT 2000, pp. 461--466, Springer, 2000.}

\bibitem{bluered}{C. Nomikos, A. Pagourtzis,  S. Zachos.
Randomized and Approximation Algorithms for Blue-Red Matching.
Lecture Notes in Computer Science 4708,
% proceedings of   Mathematical Foundations of Computer Science,
pp. 715--725, Springer, 2007.}

\bibitem{SS98}{K.H. Schlag, A. Sela. You play (an action) only once, Economic Letters,
 59,  pp. 299--303, 1998.}

\bibitem{w05}{J. W\"{a}stlund. A solution of two-person single-suit whist. The
electronic journal of combinatorics 12, 2005.}

\end{thebibliography}

\end{document}
