Research Quality, Fairness, and Authorship Order
Margareta Ackerman
Simina Br\^{anzei}
The order in which authors are listed on an academic paper determines the credit that each receives on a co-authored publication, influencing hiring, tenure and promotions. Two of the prevalent author ordering schemes are alphabetical, which involves listing authors in lexicographical order of their last names, implying that all contributed equally, and by contribution, where authors are listed in decreasing order of their contribution to the paper. We perform a game theoretic analysis of the impact of author ordering schemes, uncovering two considerable advantages of alphabetical ordering: it leads to improved research quality, and it is the more fair of the two approaches in the worst case. On the other hand, contribution-based ordering results in a denser collaboration network and a greater number of publications than is achieved using alphabetical author ordering. Furthermore, authors can overcome some of the limitations of contribution-based ordering by performing rotations, alternating who is the first author on joint papers. This often allows authors to achieve optimal research quality and perfect fairness under any given contribution scheme; however, this is obtained at the expense of truthfulness.
1208.3391.tex
%\documentclass[10pt]{article} % For LaTeX2e
\documentclass[letterpaper,11pt]{article}
\setcounter{tocdepth}{3}


\usepackage{amsmath, amsthm, amssymb, amstext, comment, graphicx, fullpage}
% add fullpage
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{example}{Example}
\newtheorem{property}{Property}
\newtheorem{corollary}{Corollary}
\newtheorem{note}{Note}
\newtheorem{todo}{TODO}
\newtheorem{claim}{Claim}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{conj}{Conjecture}
\newtheorem{game}{Game}
\newtheorem{remark}{Remark}

\begin{comment}
\setlength{\textheight}{9.3in}
\setlength\topmargin{-0.81in}
\setlength{\textwidth}{6.30in}
\setlength\oddsidemargin{-0.19in}
\setlength\evensidemargin{-0.19in}

\setlength{\parskip}{0.25em}
\setlength{\parsep}{0.25em}
\setlength{\partopsep}{0pt}
\end{comment}
\addtolength{\topmargin}{-0.5in} \addtolength{\textheight}{1in}

\newcommand{\footnoteremember}[2]{
\footnote{#2}
\newcounter{#1}
\setcounter{#1}{\value{footnote}}
}
\newcommand{\footnoterecall}[1]{
\footnotemark[\value{#1}]
}


%\setlength{\textheight}{9.31in}
%\setlength{\textheight}{9.3in}
%\setlength\topmargin{-0.5in}
%\setlength{\textwidth}{6.30in}
%\setlength\oddsidemargin{-0.19in}
%\setlength\evensidemargin{-0.19in}

\DeclareMathOperator*{\argmax}{arg\,max}


\title{Research Quality, Fairness, and Authorship Order}
%\title{Name Ordering Schemes in Academic Collaboration}

\author{
\textbf{Margareta Ackerman}\\
\small{University of Waterloo}\\
\small{mackerma@cs.uwaterloo.ca}
\footnote{%School of Computer Science, University of Waterloo, Canada. E-mail: mackerma@cs.uwaterloo.ca.
The author acknowledges support from the Natural Sciences and Engineering Research Council of Canada.}
\and
\textbf{Simina Br\^{a}nzei}\\
\small{Aarhus University}\\
\small{simina@cs.au.dk}
\footnote{%Department of Computer Science, Aarhus University, Denmark. E-mail: simina@cs.au.dk.
The author acknowledges support from the Sino-Danish Center for the Theory of Interactive Computation, funded by the Danish National Research Foundation and the National Science Foundation of China (under the grant 61061130540), and from the Center for research in the Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. }
}
%\date{\emph{Columbus did not become famous because he was the first to discover America, but because he was the last. (The %Last Inventor of the Telephone, Science)}}
\date{}

\begin{document}
\maketitle


\begin{abstract}

The order in which authors are listed on an academic paper determines the credit that each receives on a co-authored publication, influencing hiring, tenure and promotions. Two of the prevalent author ordering schemes are \emph{alphabetical}, which involves listing authors in lexicographical order of their last names, implying that all contributed equally, and by \emph{contribution}, where authors are listed in decreasing order of their contribution to the paper.

We perform a game theoretic analysis of the impact of author ordering schemes, uncovering two considerable advantages of alphabetical ordering:  it leads to improved research quality,  and it is the more fair of the two approaches in the worst case.
On the other hand, contribution-based ordering results in a denser collaboration network and a greater number of publications than is achieved using alphabetical author ordering.

Furthermore, authors can overcome some of the limitations of contribution-based ordering by performing \emph{rotations}, alternating who is the first author on joint papers. This often allows authors to achieve optimal research quality and perfect fairness under any given contribution scheme; however, this is obtained at the expense of truthfulness.
\end{abstract}

\newpage

\section{Introduction}


Author ordering is an important issue in all academic communities. Research performance is judged in large part by publication records,
and how much one benefits from each publication depends on their position within the paper's author list as well as the conventions of the field.
In short, how authors are listed affects the \emph{credit} they receive for their contributions.


Given the critical role that author ordering plays in academia, it is surprising how little is known of the effects of name-ordering conventions. What influence do ordering schemes have on individual authors? Do these scheme have any global effect on research communities where they are applied? What can authors do to overcome the limitations of contribution schemes? Our goal in this paper is to provide a framework for studying the effects of author order schemes and address these questions.

\vspace{3mm}
\textbf{Author ordering schemes.} Several name-ordering conventions are commonly applied in academic communities, each corresponding to a different credit allocation scheme.  One such common convention, frequently used in mathematics, economics, and theoretical computer science, is to list authors in lexicographical order of their last names. We refer to this method as \emph{alphabetical} author ordering. The intention is to occlude any differences in contribution, effectively implying that all authors should receive equal credit for the paper.

The American Mathematical Society~\cite{AMS} explains that ``in most areas of mathematics, joint research is a sharing of ideas and skills that cannot be attributed to the individuals separately... Determining which person contributed which ideas is often meaningless because the ideas grow from complex discussions among all partners... mathematicians traditionally list authors on joint papers in alphabetical order.''

Another dominant convention is ordering by \emph{contribution}, listing authors in decreasing order of their contribution to the project. This scheme appears, for example, in psychology and applied branches of computer science. Non-alphabetical listing sends a clear signal that earlier authors should receive greater credit than the authors listed later.

For instance, the American Psychological Association~\cite{APA} recommends ordering authors by their relative contribution: ``Authors are responsible for determining authorship and for specifying the order in which two or more author's names appear in the byline. The general rule is that the name of the principal contributor should appear first, with subsequent names in order of decreasing contribution.''


Among disciplines where authors are listed by contribution, the perceived contribution of authors can still vary substantially.   For example, in psychology, the first author typically receives substantially greater utility than other authors. On the other hand, practical branches of computer science usually assume that contribution diminishes more gracefully with author order. There are several other conventions in addition to alphabetical and contribution, but these two appear to be the most prevalent.


\vspace{3mm}
\textbf{A game-theoretic perspective.} Most previous work on author-order schemes focused on empirical studies and two player simulations. In this paper, we analyse the effects of author-order schemes from a game-theoretic perspective. To this end, we introduce a game theoretic model for analysing the impact of author ordering schemes on academic collaboration. Specifically, we propose a model of overlapping coalitions using a variant of threshold task games~\cite{Elkind}.


%Our model is the first to provide a compelling explanation for the observed correlation between research quality and alphabetical author ordering.



%Our model predicts some of the phenomenon that has been observed in empirical studies and %confirms some of the observations found through simulations. But it does more than that. Our %model offers a compelling explanation for the phenomenon it predicts. In addition, our model
%identifies several phenomenon that, to the best of our knowledge, have not been previously %observed.

%Let us first establish that no single contribution scheme can be perfectly suited to all projects.  This %may explain why some fields, such as economics and several branches of computer science, refrain from %making a commitment to a single author-ordering scheme, and instead rely on both alphabetical and %contribution based ordering schemes.
\vspace{3mm}

\textbf{Benefits of ordering alphabetically.} Alphabetical author ordering offers several surprising benefits to both individuals and the community as a whole. Namely, this contribution scheme leads to higher research quality and is the more fair of the two prominent contribution schemes considered here in the worst case.
\newpage
\begin{enumerate}
\item \emph{\textbf{Higher research quality:}} Perhaps the most appealing feature of the alphabetical author ordering scheme is that it leads to improved research quality. Specifically, under this scheme, authors solve the most difficult projects possible, and the largest number of such projects.

Several studies provide empirical evidence for this phenomenon. Brown \emph{et al.}~\cite{Brown} found that alphabetical ordering is positively correlated with research quality in the marketing literature. Laband and Tollison~\cite{Laband} found a similar trend in the economics research literature, where two-author papers that are alphabetized are more frequently cited. In addition, Joseph \emph{et al.}~\cite{Joseph} set up a two player simulation, and found that the tendency towards alphabetical author ordering increases as acceptance rates decrease, and that for a fixed acceptance rate, papers whose authors are listed in alphabetical order tend to be of higher quality.

Why does alphabetical ordering result in higher quality research? Our model offers a compelling explanation, showing that ordering authors alphabetically encourages collaboration between similar players. In particular, it gives incentive for the strongest players to combined their efforts. As all authors involved would receive equal credit, they all have vested interest in creating a high quality joint project.

On the other hand, when a contribution scheme where the first author receives most of the credit is applied, the strongest players get penalized for collaborating, as only one of them can take the first author slot.  As a result, alphabetical ordering leads to the completion of more difficult tasks than when authors are listed by contribution.


\item \emph{\textbf{Better worst-case fairness:}} Another important issue with regard to author ordering is that of fairness.
Several authors previously suggested that contribution-based ordering is the more fair of the two common name-ordering schemes. Lake~\cite{Lake} argues that alphabetical author ordering is uninformative and unfair. This scheme gives raise to a version of the \emph{Matthew Effect}, whereby readers are likely to assume that the more established authors have made a greater contribution, giving them disproportional credit at the expense of the remaining authors. Alphabetical ordering also benefits those whose last names start with letters that occur earlier in the alphabet (\cite{Efthyvoulou}, \cite{Einav}, \cite{Praag}). For these reasons, Lake~\cite{Lake} argues for regulations to enforce ordering authors by contribution.
 %as is already mandated by the Psychological Association.

However, upon formal examination, it becomes clear that all contribution schemes suffer from unfairness in some cases. Surprisingly, our worst case analysis reveals that alphabetical ordering is the safer choice: Greater loss due to unfairness is possible when ordering by contribution than alphabetically. That is, the worst case loss due to unfairness that a player can incur when relying on the alphabetical ordering scheme is not as severe as the loss a player can incur when ordering by contribution.

% Alphabetical ordering leads to higher quality research and less loss due to unfairness in the worst %case. However, conventions underlying contribution schemes are typically resistance to change and %authors often have little choice in the matter. So what are authors to do if they are unsatisfied with %the implications of the author ordering scheme that they are required to use? Sometimes, there is a %solution.
\end{enumerate}

\vspace{3mm}

\textbf{Benefits of ordering by contribution.} We also demonstrate several advantages of ordering by contribution. Specifically, we consider the scheme that allows those who make a very small contribution to be listed as authors. Under such contribution schemes, authors later in the list receive a correspondingly small proportion of the credit.

Using such a contribution scheme results in a denser social network. The finding that contribution ordering results in a greater number of collaborators has been previously observed through empirical data analysis by Newman~\cite{Newman}, who reports that the average number of collaborators an individuals has is more than four times higher in biology (where contribution-based ordering is used) than in mathematics (where authors are listed in alphabetical order). Further, it is shown that the number of collaborates in physics, another field that relies on alphabetical author ordering, is similar to that found in mathematics. Lastly, we also show that this contribution scheme results in a higher research productively as measured by the average number of publications per author.


\newpage

\textbf{Overcoming limitations of contribution ordering via rotations.}
What are authors to do if they are unsatisfied with the implications of the author ordering scheme that they are required to use? Sometimes, there is a solution. When the same players collaborate on multiple projects, they can perform \emph{rotations} by alternating who is the first author on joint papers. Performing rotations allows players to achieve perfect fairness as well as solve the highest quality projects that their combined efforts can attain. Although rotations offer benefits to individual players, they come at the price of truthfulness. Authors no longer try to use author ordering to demonstrate how much they contribute to individual papers, undermining the intended purpose of the contribution scheme.

%We also note that rotations cannot always be applied, and even when they can, some authors may still experience loss due to unfairness.


\section{Model}

The \emph{academic game} is a network formation game.
Let $N = \{1, \ldots, n\}$ be a set of players. Each player $i$ has a budget of weight $w_i$, consisting of a set of coins
$C_i = \{c_{i,1}, \ldots, c_{i, n_i}\}$. Every coin $c_{i,j}$ has a positive weight
$w_{i,j}$, and $\sum_{j=1}^{n} w_{i,j} = w_{i}$, $\forall i \in N$. The players can form overlapping coalitions to solve different
projects.
A project of weight $w$ can be solved either by one player who invests a coin of weight $w$ to the project,
or by two players, each of which contributes with one coin, and the sum of the two coins is $w$.
A player can participate in multiple projects simultaneously, by investing a different coin to each project they participate in.
The same pair of players can solve multiple projects together, and each coin can only be used once.

Let $T \subseteq \mathbb{R}^{+}$ denote a set of project weights and let $f:\mathbb{R}^{+} \rightarrow \mathbb{R}^{+}$ be a reward
function. For every $w \in T$, there exists an infinite
number of available projects of weight $w$. Solving a project of weight $w \in T$ gives a reward $f(w)$, 
which is divided among the players that solved the project.
In this paper we study games with polynomial reward, that is, $f(w) = w^r$, where $r>1$.
%Note that in reality the reward
%function may be curbed, such that for tasks of higher weight, the exponent $r$ decreases to model diminished returns due to
%coordination costs, for example.
%We consider two main types of available tasks:
Unless otherwise noted, there exist projects for every positive weight (i.e. $T = \mathbb{R}^{+}$).
We are also interested in a restriction relevant to academic games:
%\begin{itemize}
$T = [t, \infty)$, where $t$ is referred to as a \emph{conference tier}. Solving a project of weight $w$ gives reward
$f(w)$ if $w \geq t$, and zero otherwise.
%\item $T = [a, b]$, where $a$ and $b$ are lower and upper bounds, respectively, on the hardness of the available projects. That is,
%a project of weight $w$ gives a reward of $\min(f(w), f(b))$ when $w \geq a$, and zero if $w < a$.
%\end{itemize}

Finally, in each academic community there exists a general perception of the significance of being first or second author on a paper.
%Without prior knowledge about the specific paper and authors involved, one may evaluate the relative contribution of each author using a \emph{contribution vector},
%such that the $k^{th}$ entry in a vector of size $n$ shows the percentage of credit received by the $k^{th}$ author on \emph{any} paper with $n$ authors.
Without prior knowledge about the specific paper and authors involved, the relative contribution of each author on a two-authored paper
can be evaluated using a fixed \emph{contribution vector} $[\phi, 1-\phi]$, where $1/2 \leq \phi < 1$. That is, the community assumes that
the contribution of the first and second author are $\phi$\% and $(1-\phi)$\%, respectively.

%In this model, we study contribution vectors of size two. That is, for every research community and two-author paper,
%there exists $\phi$ such that $1/2 \leq \phi < 1$ and the first author receives $\phi$\% of the credit, while the second author
%receives $(1-\phi)$\% of the credit.

Next we define coalition structures and utility in academic games.

\begin{definition}[Coalition Structure]
Given an academic game, a \emph{coalition structure} $CS$ is a partition of all the coins, such that every coin $c_{i,j}$ of player $i$
is either a singleton project, or is paired with a coin $c_{k,l}$ belonging to another player $k \in N \setminus \{i\}$.
\end{definition}

\begin{definition}[Utility]
Given an academic game and a coalition structure $CS$,
let $CS_i$ be the set of projects that player $i$ contributes to, $\forall i \in N$.
%let $\{P_1, \ldots, P_m\}$ denote the set of projects solved under $CS$, and
%$CS_i$ the set of projects that player $i$ contributes to.
The utility of $i$ is:
\[
u_i(CS) = \sum_{P_{j} \in CS_i} v_i(P_{j}),
\]
where $\{P_1, \ldots, P_m\}$ is the set of projects solved under $CS$,
$w(P_j)$ is the weight of project $P_j$, and
\[
v_i(P_{j}) =
\left\{
	\begin{array}{ll}
	w(P_j)^r & \mbox{if $i$ completes $P_j$ alone} \\
	\phi \cdot w(P_j)^r & \mbox{if $i$ is the first author on $P_j$} \\
	(1 - \phi) \cdot w(P_j)^r & \mbox{if $i$ is the second author on $P_j$}
	\end{array}
\right.
\]
\end{definition}

\begin{example}
Consider a two player academic game, where player $1$ has the set of coins $C_1 = \{c_{1,1}, c_{1,2}\}$, 
player $2$ has set of coins $C_2 = \{c_{2,1}\}$, the weights of the coins are:
$w_{1,1} = 3, w_{1,2} = 1$, $w_{2,1} = 2$, and $r = 2$.
The possible coalition structures are: $CS_1 = (\{c_{1,1} \}, \{c_{1,2}\}, \{c_{2,1}\})$,
$CS_2 = (\{c_{1,1}, c_{2,1}\}, \{c_{1,2}\})$, and $CS_3 = (\{c_{2,1}, c_{1,2}\}, \{c_{1,1}\})$, where for each
project, the coins are listed by decreasing size.
The utilities of the players are as follows:
\begin{itemize}
\item $CS_1$: $u_1(CS_1) = w_{1,1}^r + w_{1,2}^r = 3^2 + 1^2 = 10$ and $u_2(CS) = w_{2,1}^r = 2^2 = 4$.
\item $CS_2$: $u_1(CS_2) = \phi \cdot (w_{1,1} + w_{2,1})^r + w_{1,2}^r = \phi \cdot 5^2 + 1^2 = 25 \phi + 1$ and $u_2(CS_2) = (1-\phi) \cdot (w_{1,1} + w_{2,1})^r =
25 (1-\phi)$
\item $CS_3$: $u_1(CS_3) = (1-\phi)\cdot (w_{2,1} + w_{1,2})^r + w_{1,1}^r = 9(1-\phi) + 9$ and $u_2(CS_3) = \phi \cdot (w_{2,1} + w_{1,2})^r = 9 \phi$.
\end{itemize}
\end{example}


The rest of the paper is organized as follows. In section 3 we study academic games with indivisible budgets, where each player has exactly one coin, and analyze research quality and fairness in that setting. In section 4, we study academic games with discrete budgets,
where each player can have multiple coins of different sizes, and investigate
research quality, fairness, rotations, and implications for the resulting social network. In Section 5, we discuss related models, and in section 6 we conclude with avenues for future investigation.


\section{Indivisible Budgets}

We begin by considering the indivisible budgets setting, where each player has a single coin, corresponding to the scenario where every player is involved in a single project.
We will show that this setting is sufficient to demonstrate the main benefits of the alphabetical ordering scheme, namely, that it leads to optimal research quality and
is more fair than contribution-based ordering in the worst case.

First, we introduce our main solution concept, namely pairwise stability. Pairwise stability is the standard solution concept in network formation games
\cite{Jackson}. We say that a coalition structure $CS$ is \emph{pairwise stable} if:
\begin{itemize}
\item For all $i\in N$, $u_i(CS) \geq w_i^r$. That is, $i$ cannot improve by allocating his coin to a singleton project.
\item For all $i, j \in N$, with $w_i \geq w_j$, either $u_i(CS) \geq \phi \cdot (w_i + w_j)^r$ or $u_j(CS) \geq (1 - \phi) \cdot (w_i + w_j)^r$.
That is, $i$ and $j$ cannot both strictly improve by deviating to a joint project.
\end{itemize}

Further, we note that the alphabetical ordering scheme guarantees the existence of a pairwise stable coalition.
In contrast, there are games where no pairwise stable coalitions exist under contribution-based ordering. See Appendix B for details.

\subsection{Research Quality}~\label{researchQualitySection}

We show that alphabetical ordering results in higher research quality than is possible using some contribution-based scheme; Namely, it leads to the solution of the highest number of projects of optimal quality. Since players can work either by themselves or in pairs, the most difficult project that a set of players can solve results from the combined efforts of its two strongest players. We call a project of this difficulty a \emph{hard project}. Observe that a coalition can solve multiple hard projects.

 We begin by considering identical players, showing that they solve the maximum number of hard projects under alphabetical ordering.


\begin{proposition}
Consider an academic game with identical players and indivisible budgets. Then every pairwise stable coalition structure
solves the maximum number of \emph{hard projects}, i.e. projects requiring two players, whenever $\frac{1}{2^r} < \phi < 1 - \frac{1}{2^r}$.
%In particular, the maximum number of hard projects are always solved under alphabetical ordering ($\phi = 1/2$).
\end{proposition}
\begin{proof}
In order for the maximum number of hard projects to be solved in every pairwise stable equilibrium, it should be the case that
two singleton players can strictly improve their utility by working on a joint project.
The conditions for the first and second author, respectively, are: $\phi \cdot 2^r > 1$ and $(1 - \phi)\cdot 2^r > 1$, or
equivalently, $\frac{1}{2^r} < \phi < 1 - \frac{1}{2^r}$.
\end{proof}

Note that the maximum number of hard projects is always solved under alphabetical ordering ($\phi = \frac{1}{2}$).

%Discussion for mechanism design
%Thus when the players are identical, alphabetical ordering is the only name ordering scheme which %encourages truthfulness. Otherwise,
%the players can lie about who contributed more on a project, when in fact their contribution was equal.
%To ensure stability, a mechanism designer needs to impose a tie-breaking rule, such that if two players, %$i$ and $j$,
%contributed equally, it is always the same player (say $i$) who gets credit as a first author.

We now consider a game with two player types, \emph{heavy players} of weight $1$ and \emph{light players} of weight $0 < \lambda < 1$. A contribution scheme can encourage same-layer collaborations, resulting in the solution of the maximum number of hard projects. Alternatively, a contribution scheme can encourage cross-layer collaborations or discourage all collaboration.

\begin{theorem} \label{thm:two_layer}
Consider an academic game with indivisible budgets and two types of players, of weights $1$ and $\lambda$, respectively, where $0 < \lambda < 1$.
Then every pairwise stable coalition structure has
\begin{enumerate}
\item Only same-layer collaborations when $\frac{(1+\lambda)^r}{2^r + (1+\lambda)^r} < \phi < \min\left(1 - \frac{1}{2^r}, \frac{1}{(1+ \lambda)^r}, \frac{2^r}{2^r + (1+\lambda)^r}\right)$.
\item Only cross-layer collaborations when $\max\left( 1 - \frac{1}{2^r}, \frac{1}{(1+\lambda)^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$.
\item No collaboration when $1 - \frac{1}{2^r} < \phi < \frac{1}{(1+ \lambda)^r}$ or
$\phi > \max\left( 1 - \frac{1}{2^r}, 1 - \left( \frac{\lambda}{1 + \lambda}\right)^r\right)$.
\end{enumerate}
\end{theorem}
%\begin{proof}
%The proof follows from Lemma \ref{lem:two_player_same_layer}, Lemma \ref{lem:two_layer_cross}, and Lemma %\ref{lem:two_layer_none} in the Appendix.
%\end{proof}

%Note that the conditions in Theorem \ref{thm:two_layer} ensure that \emph{every} academic game with %indivisible budgets and player types $1$ and $\lambda$
%has the given properties

Observe that setting $\phi=\frac{1}{2}$, we obtain that alphabetical ordering solves the highest number of hard projects, while ordering by contribution in the range given by (2) solves the highest number
of intermediate projects (i.e. projects requiring one heavy and one light player).

\begin{comment}
\begin{corollary}
Consider an academic game with two types of players, of weights $1$ and $\lambda$, respectively, and conference tier $1 + \lambda$,
where $0 < \lambda < 1$.
Then the highest number of hard projects is solved when $\frac{(1+\lambda)^r}{2^r + (1+\lambda)^r} < \phi < \min\left(1 - \frac{1}{2^r}, \frac{1}{(1+ \lambda)^r}, \frac{2^r}{2^r + (1+\lambda)^r}\right)$,
and the highest number of intermediate projects is solved when $\max\left( 1 - \frac{1}{2^r}, \frac{1}{(1+\lambda)^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$.
\end{corollary}
\end{comment}







\subsection{Fairness}\label{fairnessSection}

It has been argued that alphabetical ordering is unfair~\cite{Lake}, as it gives the same credit to all authors even when they do not contribute equally. Our results show that both alphabetical and contribution-based ordering can result in substantial degrees of unfairness. There is no single contribution scheme that is best for all coalitions. Yet unfairness can actually be \emph{greater} when using contribution-based ordering than when the alphabetical ordering scheme is applied. That is, the worst case loss due to unfairness is higher when using contribution-based ordering than when ordering authors alphabetically.


The fundamental difficulty is that in research communities, the contribution scheme is fixed.
 Even listing authors by contribution is not informative enough, since the members of the community have a predetermined notion
of the proportion of work contributed by each author. While in some communities the second author is assumed to have done moderately less than the first, in others, the contribution of the second author is considered to be negligible compared with that of the first. Whatever the case may be, authors do not typically get to choose the contribution vector, since that would require changing the perception of the entire community. Consequently, in most cases, some degree of unfairness is inevitable.

Formally, if two players allocate weights $x$ and $y$, respectively, to a joint project, then the rewards should be proportional to the effort invested,
i.e.
$\left( \frac{x}{x + y} \right) (x+ y)^r$ and $\left( \frac{y}{x + y} \right) (x + y)^r$, respectively.
Thus the \emph{fair contribution vector} for this project is uniquely defined as: $\mathcal{C} = \left[\frac{x}{x + y}, \frac{y}{x + y} \right]$.

We study the losses of the players due to the fixed contribution vector. For each player, the loss is given by the (normalized) difference between the actual contribution and the perceived contribution. Recall that $w(P)$ denotes the weight of project $P$.
Given a contribution scheme $\phi$, the \emph{loss due to unfairness} of player $i$ in a coalition structure $CS$ where he solves project $P$ is:
\[ \mathcal{L}_i =
\left\{
	\begin{array}{ll}
	0 & \mbox{if $i$ completes $P$ alone} \\
	\frac{w_i - \phi \cdot w(P)}{w_i}   & \mbox{if $i$ is the first author on $P$} \\
	\frac{w_i - (1-\phi) w(P)}{w_i} & \mbox{if $i$ is the second author on $P$}
	\end{array}
\right.
\]

Note that the loss due to unfairness parallels the price of anarchy (Nisan \emph{et al}, \cite{AGT_book}).

%Similarly, the \emph{gain due to unfairness} is:
%$\mathcal{G}_i = \frac{\mbox{\textit{actual}} - \mbox{\textit{fair}}}{\mbox{\textit{fair}}}$.

\begin{comment}
We define the \emph{unfairness imparted on author $i$}, denoted $unfairness(i)$, as 1 minus the ratio of the proportion that they actually receive over the proportion of credit that they would have received had the ideal contribution vector been used. Formally,
given coalition $(1,2)$ where player $1$ of contributes $W$ and player $2$ contributes $cW$ for some $0 < c < 1$, and a fixed contribution vector, $(\alpha, 1-\alpha)$, the \emph{unfairness imparted on author} on author $1$ is  $unfairness(1) = 1-\alpha(1+c)$, while the unfairness imparted on author on author $2$ is $unfairness(2) = 1- \frac{\alpha(1+c)}{c}$.
\end{comment}



We explore the degree of unfairness permitted by both the alphabetical and contribution-based orderings. 
We begin by considering identical players. Since they contribute equally to a project, alphabetical author ordering corresponds to the unique fair contribution vector for their project, while all contribution-based ordering schemes result in some degree of unfairness.

\begin{theorem}\label{alpha fairness}
Consider an academic game with identical players and indivisible budgets.
Then alphabetical ordering is the (unique) fair contribution vector. When $\phi > 1 - \frac{1}{2^r}$,
the loss due to unfairness is $2\phi-1$ for at least $\frac{n}{2}-1$ of the players, under every
pairwise stable coalition structure.
\end{theorem}

The highest loss due to unfairness occurs when $\phi = 1 - \frac{1}{2^r}$.

\begin{corollary}\label{corr:fainessContribution}
%Consider an academic game with identical players, indivisible budgets, and a fixed tie-breaking rule.
There exists an academic game and a contribution-based ordering such that the loss due to unfairness is
$1-\frac{1}{2^{r-1}}$ for half of the players under every pairwise stable coalition structure.
\end{corollary}

For example, when $r=2$, half of the authors lose 50\% of their rightful credit. %When $r=1.5$, the value of the loss $1-0.5^{r-1}$ is just under $0.3$.



\begin{comment}
A similar result to Theorem~\ref{alpha fairness} holds for the academic game with two types of players when $\phi$ encourages the maximum number of same-layer collaborations. % The following corollary follows by Theorem~\ref{thm:two_layer}.

\begin{corollary}
Consider an academic game with two types of players, of weights 1 and $\lambda$, respectively, where $0 < \lambda < 1$.
Then if $\phi$ is in the range $\frac{(1+\lambda)^r}{2^r + (1+\lambda)^r} < \phi < \min\left(1 - \frac{1}{2^r}, \frac{2^r}{2^r + (1+\lambda)^r}\right),$
at least $n/2-1$ of the players incur a loss of $2\phi-1$ due to unfairness.
\end{corollary}
\end{comment}


\begin{comment}
When the contribution vector encourages cross-level collaboration, we obtain the following loss due to unfairness.

\begin{theorem}\label{different players fairness}
Consider an academic game with two types of players, of weights 1 and $\lambda$, respectively. If
 $\phi$ is in the range $\max\left( 1 - \frac{1}{2^r}, \frac{1}{(1+\lambda)^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$, then in every pairwise stable coalition structure:
\begin{itemize}
\item If $\phi < \frac{1}{\lambda}$, all the heavy players involved in a collaboration incur a loss of $1-\phi(1+\lambda)$ due to unfairness.
\item If $\phi > \frac{1}{\lambda}$, all the light players involved in a collaboration incur a loss of $1-\frac{(1-\phi)(1+\lambda)}{\lambda}$ due to unfairness.
\end{itemize}
\end{theorem}
\end{comment}

%We can now evaluate the degree of unfairness allowed under alphabetical ordering.
%We study games with two types of players, of weights $1$ and $\lambda$, respectively, where $0 < \lambda < 1$.
%When ordering alphabetically, the worst case loss due to unfairness is incurred on heavy players who are paired up with light players.

Next, we prove the worst case loss due to unfairness allowed by alphabetical author ordering. That is, we will illustrate a coalition structure where a player obtains the worst possible loss due to unfairness that can occur when alphabetical author ordering is applied. To this end, we begin with a more general result concerning loss due unfairness for different player types.

\begin{theorem}\label{different players fairness}
Consider an academic game with two types of players, of weights 1 and $\lambda$, respectively. If
 $\phi$ is in the range $\max\left( 1 - \frac{1}{2^r}, \frac{1}{(1+\lambda)^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$, then in every pairwise stable coalition structure:
\begin{itemize}
\item If $\phi < \frac{1}{\lambda}$, all the heavy players involved in a collaboration incur a loss of $1-\phi(1+\lambda)$ due to unfairness.
\item If $\phi > \frac{1}{\lambda}$, all the light players involved in a collaboration incur a loss of $1-\frac{(1-\phi)(1+\lambda)}{\lambda}$ due to unfairness.
\end{itemize}
\end{theorem}

We now demonstrate the worst case loss for alphabetical author ordering.

\begin{proposition} \label{proposition:unfairness_loss_alphabetical_indivisible}
Consider an academic game with two types of players, of weights 1 and  $\lambda$ respectively, where $2^{\frac{1}{r}}-1 < \lambda < 1$.
Then under alphabetical ordering, all the heavy players that collaborate incur a loss of $\frac{1}{2}(1-\lambda)$ due
to unfairness, under pairwise stability. It follows that the worst case loss due to unfairness for alphabetical ordering is no greater than $1-2^{\frac{1}{r}-1}$.
\end{proposition}
\begin{proof}
In the two player setting, alphabetical ordering disadvantages the heavier player.
We require a bound of $2^{\frac{1}{r}}-1$ to ensure that heavy players collaborate with light players.
The result follows by Theorem~\ref{different players fairness}.
The worst case is obtained when $\lambda$ approaches $2^{\frac{1}{r}}-1$.
For example, when $r=2$, the unfairness score is $\approx 30$\%.
\end{proof}



%\begin{observation} \label{obs:unfairness}
%Observe that the loss due to unfairness of $1-2^{1-r} = 1-\frac{1}{2^{r-1}}$
%allowed by contribution based ordering, is strictly greater than that possible using alphabetical author %ordering, $1-\left(\frac{1}{2}\right)^{\frac{r-1}{r}}$, for all $1 < r \leq 2$.
%\end{observation}

While in the previous theorems we showed that the contribution vector can affect as many as half of the players involved, we show that for arbitrary
games, the same worst case bounds hold for individual players.

%Instead of Observation \ref{obs:unfairness}, can we state something like this:


\begin{theorem}
Consider an academic game with indivisible budgets and arbitrary weights. Then for every player, the worst case loss due to unfairness is no greater than $1-\left(\frac{1}{2}\right)^{\frac{r-1}{r}}$
under alphabetical ordering, while it can be as high as $1-\frac{1}{2^{r-1}}$ under contribution-based ordering.
\end{theorem}
\begin{proof}
Note that the bound in Proposition~\ref{proposition:unfairness_loss_alphabetical_indivisible} represents the worst case loss due to unfairness that any player can incur under alphabetical ordering. The result follow from Proposition~\ref{proposition:unfairness_loss_alphabetical_indivisible} and Corollary~\ref{corr:fainessContribution}.
\end{proof}

Note that $1-\left(\frac{1}{2}\right)^{\frac{r-1}{r}} < 1-\frac{1}{2^{r-1}}$ for all $r >1$.
Although the fairness of any contribution scheme depends on the specific coalition where it is applies, we find that contribution-based ordering can result in a greater degree of unfairness than is allowed by alphabetical author ordering.



\section{Discrete Budgets}

We now turn our attention to the general model, where each player has multiple coins, allowing players to work on multiple projects simultaneously. While the results above also apply in the multiple coins setting, we uncover several phenomena that cannot be observed when each player has a single coin.

\begin{comment}
\begin{todo}
Check again this paragraph
\end{todo}
Similarly to the indivisible budgets setting, when the players have any number of identical coins and the reactions to a deviation are neutral, alphabetical ordering ensures that the maximum number of hard tasks is solved. Moreover, when the players have neutral reactions to a deviation, there exist games in which alphabetical ordering is the only ordering scheme which ensures that the academic game has a stable coalition structure.
\end{comment}

First, we generalize some of our findings to this general model, in particular, showing that
alphabetical ordering leads to improves research quality. We then demonstrate the following interesting phenomenon: There exist many games in which the \emph{contribution vector does not matter}, since the players can perform rotations, by alternating between being first and second author on joint projects. Rotations can allow players to reach optimal research quality as well as obtain perfect fairness.

Our solution concept is pairwise stability for games with overlapping coalition structures.
Given that a player can be involved in multiple projects
simultaneously,
it is important that one estimates correctly the reactions from the rest of the players before agreeing to be involved in a deviation.
We follow the recent literature on overlapping coalition formation games
(Elkind \emph{et al} \cite{Elkind}, Zick \emph{et al} \cite{Zick}), and study \emph{refined reactions} to a deviation.
In short, when player $i$ is involved in a deviation from a coalition structure $CS$, he or she can expect the following:
\begin{itemize}
\item Every non-deviating player which is hurt by the deviation retaliates
and drops all the projects with $i$. Note that unless $i$ and $j$ agreed to deviate together,
a player $j$ is hurt by the deviation when at least one of $j$'s projects has been discontinued by the deviators.
\item The unaffected players are neutral, and they maintain all of their existing projects with $i$.
\end{itemize}

\begin{comment}
I.e., when a player $i$ deviates from a coalition structure $CS$, he can expect retaliation from the players which are hurt by
$i$'s deviation, and no reaction from the players which are not affected by a deviation. That is, if player $i$ deviates by
reallocating a coin from a project with another player $j$, then $i$ can expect that $j$ will drop all the existing projects
with $i$. On the other hand, if $i$ maintains all the projects with $j$ during the deviation, he can expect that $j$ will
not react to the deviation.
\end{comment}

\begin{definition}[Pairwise Stability]
A coalition structure $CS$ is pairwise stable if:
\begin{itemize}
\item No player $i$ can drop some of his existing projects and strictly improve utility in the resulting coalition structure $CS^{'}$
\item No two players $i$ and $j$, can rearrange the projects among themselves and possibly drop some of the
projects with the remaining players, such that both $i$ and $j$ strictly improve their utility in the resulting coalition structure $CS^{'}$
\end{itemize}
where $CS^{'}$ is such that the remaining players have refined reactions to a deviation.
\end{definition}

See Appendix C for an example of pairwise stability for discrete budgets. 
%\textbf{TODO:} Give example of pairwise stable and unstable coalition structures.


%However, maintaining stability when ordering is done by contribution can require additional constraints, %such as the players punishing the deviators~\cite{Elkind}.
\subsection{Research Quality}

We now generalize the results of Section~\ref{researchQualitySection}, showing that alphabetical ordering encourages high research quality in the discrete budget model. First, we consider discrete budgets with identical coins, where alphabetical ordering leads to the solution of the greatest number of hard projects.

\begin{proposition}~\label{discreteResearchQualityIndentical}
Consider an academic game with discrete budgets and identical coins. Then alphabetical ordering ensures the existence of a pairwise stable coalition structure. Moreover, every pairwise stable coalition structure under alphabetical ordering solves the greatest number of hard projects.
\end{proposition}


Next, we consider the game where players have two coins types, and demonstrate the type of collaborations that result from different contribution schemes. The following result provides another illustration that alphabetical ordering leads to the solution of the greatest number of hard projects. In addition, this result shows what contribution schemes result in the greatest number of intermediate projects, whose weight consists of one large and one small coin.

\begin{theorem} \label{thm:two_layer_discrete}
Consider an academic game with discrete budgets, where each player has two types of coins, of size $1$ and $\lambda$, respectively. Then every pairwise stable coalition structure:
\begin{enumerate}
\item has only equal effort collaborations, consequently solving the maximum number of hardest projects, when $\frac{(1+\lambda)^r}{2^r + (1+\lambda)^r} < \phi < \min\left(1 - \frac{1}{2^r}, \frac{1}{(1+ \lambda)^r}, \frac{2^r}{2^r + (1+\lambda)^r}\right)$.
\item has only unequal effort collaborations when  $\max\left( 1 - \frac{1}{2^r}, \frac{1}{(1+\lambda)^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$.
\item has no collaborations when $1 - \frac{1}{2^r} < \phi < \frac{1}{(1+ \lambda)^r}$ or
$\phi > \max\left( 1 - \frac{1}{2^r}, 1 - \left( \frac{\lambda}{1 + \lambda}\right)^r\right)$.
\end{enumerate}
\end{theorem}

\subsection{Fairness}

We generalize our result for identical players from Section~\ref{fairnessSection} to the setting of identical coins, showing that alphabetical ordering is the unique fair contribution vector, while all other contribution vectors can cause substantial loss due to unfairness.

First, we generalize loss due unfairness to the discrete budgets setting. For each player, the loss is given by the (normalized) difference between the actual contribution and the perceived contribution,
aggregated over all the projects that the player is involved with.
Given a contribution scheme $\phi$, the \emph{loss due to unfairness} of player $i$ in a coalition structure $CS$, where he solves project $P_1, \ldots, P_m$, is:
\[
\mathcal{L}_i = \frac{w_i - \sum_{j=1}^m \mathcal{L}_i(P_j)}{w_i},
\]
where
\[ \mathcal{L}_i(P_j) =
\left\{
	\begin{array}{ll}
	0 & \mbox{if $i$ completes $P_j$ alone} \\
	\phi \cdot w(P_j)   & \mbox{if $i$ is the first author on $P_j$} \\
	(1-\phi) w(P_j) & \mbox{if $i$ is the second author on $P_j$}
	\end{array}
\right.
\]

Observe that this definition is equivalent to the one given in Section~\ref{fairnessSection} when a player has only one coin.

\begin{theorem}\label{alpha fairness discrete}
Consider an academic game with discrete budgets and identical coins. Then alphabetical ordering is the unique fair contribution vector. When $\phi > 1 - \frac{1}{2^r}$,
 up to $n-1$ players can incur a loss due to unfairness of $2\phi-1$.
\end{theorem}

In the following section, we demonstrate an approach for eradicating loss due to unfairness in the discrete budget model regardless of what contribution scheme is applied.


\subsection{Rotations}

Players can sometimes overcome the limitations of a fixed contribution scheme. That is, they can simultaneously solve the highest number of hardest projects and achieve fairness, regardless of the contribution vector.
We refer to this phenomenon as \emph{rotations}.
Players who collaborate on multiple projects agree that one of them will be the primary author on half of their publications, while the other will be first author on the remaining ones - regardless of whether this represents their actual contributions.

%On the other hand, we demonstrate an interesting phenomenon under ordering by contribution. If a tie-breaking rule is not used, then the players can perform rotations to ensure that they receive a fair amount of credit.

\begin{comment}
We rely on conservative reaction to a deviation, where hurt players retaliate (they drop all projects with the deviator), while the rest don't care and maintain all existing projects (Cite the refined core--this is the version for pairwise stability).
\end{comment}

We first demonstrate this result for budgets with multiple identical coins.

\begin{proposition}\label{rotations1}
There exist academic games with discrete budgets and multiple identical coins
such that for every $\phi$, the maximum number of hard projects is solved in a refined pairwise stable equilibrium and no player suffers any loss due to unfairness.
\end{proposition}


%NOTE: Above can be generalized any number of coins in the two player setting, or any equal number of coins for $n$ players.

Rotations can also be used to overcome loss due to unfairness when coins are not required to be identical, and projects require the combination of different coin types.

%\textbf{RITA} Some of your theorems / propositions have the same label (e.g. "rotations"). This created errors in the proposition %numbers you are referring to. I fixed one of them, but please check over all and give them different labels (or just  remove the %label if you don't reference the theorem).


\begin{proposition}\label{rotations2}
Let $1-\lambda$ be the conference tier. There there exist academic games with discrete budgets, where each player has two types of coins, one of size $1$ and one of size $\lambda$, so that there is no loss due to unfairness in the refined pairwise stable equilibrium.
\end{proposition}

However, rotations do not completely solve the problem of loss due to unfairness. Even when players who work together on multiple projects perform rotations, there are several ways in which some unfairness can be retained. This occurs, for instance, when when a pair of players collaborate on an odd number of projects. However, an even worse loss due due to unfairness in incurred by those unable to find a collaborator who will work with them on several different projects.
We demonstrate the latter phenomenon in the case of identical coins.


\begin{proposition}
Consider an academic game with discrete budgets and identical coins. Even when rotations are performed, there can be a player who incurs a loss of $2\phi-1$ due to unfairness whenever $\phi > 1 - \frac{1}{2^r}$.
\end{proposition}
\begin{proof}
Consider a coalition with an odd number of players where every player has $2m+1$ coins where $n\geq 2m+2$, all but one of the players collaborate with one other player on $2m$ projects, and the remaining player collaborates with a different player on every project as the second author. Then that last player incurs a loss of $2\phi-1$ due to unfairness. Note also that all but the last player receive optimal utility and the last player does not deviate due to the lower bound on $\phi$.
\end{proof}





\begin{comment}
TODO: Make a note that if the players have neutral reactions to a deviation (i.e. they don't do anything), then
they can't do the rotations, since a player will drop their second author project and use that coin to work alone.

Setting a tie-breaking rule ensures the existence of a pairwise stable coalition structure
for every contribution-based ordering.
\end{comment}

\subsection{Implications for the Social Network}
For the next result we illustrate the following phenomenon observed in~\cite{Newman}: when the players use ordering by
contribution, they have more co-authors than when using alphabetical ordering.
In the next result, we consider the setting in which every player has a budget consisting of big coins and small coins.
The big coins represent a large amount of effort, while small coins represent very little effort, such as `` cheap talk'',
but can nevertheless contribute to improving the quality of a paper. Allowing for cheap talk results in a much higher number of collaborations.

\begin{proposition}~\label{social network result}
Consider an academic game with discrete budgets, where each player has several big and small coins,
of sizes $1$ and $\varepsilon$, respectively, where $0 < \varepsilon \ll 1$, and the conference tier is $1$.
The small coins represent ``cheap talk'', and we assume that each player has more big coins than small coins.
Then when $\phi > \max \left(\frac{2^r}{2^r + (1+\varepsilon)^r}, \frac{1}{(1+\varepsilon)^r}\right)$,
every pairwise stable equilibrium solves the maximum number of projects and the average number of
collaborators per player is the highest possible.
\end{proposition}

We note that there exist games in which ordering by contribution allows to simultaneously maximize the number of hard projects
and the total number of projects. We illustrate this phenomenon when there exist both an upper and lower bound on the
hardness of the rewarded projects.

\begin{corollary}
Consider an academic game with discrete budgets, where each player has several big coins and small coins, of sizes $1$ and $\lambda$,
respectively, where $0 < \lambda < 1$, the conference tier is $1$, and the maximum project hardness is $1 + \lambda$.
We assume that each player has more big coins than small coins.
Then when $\phi > \max \left(\frac{2^r}{2^r + (1+\lambda)^r}, \frac{1}{(1+\lambda)^r}\right)$,
every pairwise stable equilibrium solves the maximum number of projects, each of the projects solved is the hardest possible,
and the average number of collaborators per player is the highest possible.
\end{corollary}


\begin{comment}
\subsection{Combining credit allocation schemes}

\begin{proposition}
Consider an academic game with discrete budgets and two types of players, where players of type 1 have coins of size 1 and $\varepsilon$, respectively,
while players of type 2 have coins of size $\lambda$, where $\varepsilon < \lambda < 1$. Then the highest number of hard projects is solved when
both alphabetical and contribution ordering are used.
\end{proposition}
\begin{proof}
TODO: Formalize this. The idea is that profs use their big coins toward collaborating with colleagues under alphabetical ordering, and their small
coins towards collaborating with students (who have intermediate coins) under contribution ordering.
\end{proof}
\end{comment}

\section{Related Models}

The academic game is a non-transferable utility game with overlapping coalitions and is related to several existing classes of coalitional games, such as threshold task games \cite{Elkind}, coalitional skill games \cite{Bachrach}, and weighted voting
games \cite{Elkind_wvg}.
There exist several co-authorship models in the economics and computer science literature, among which we mention the following.
Clippel \emph{et al} (\cite{Moulin}, \cite{Ariel_blog}) study the division of a homogeneous divisible good
when every player reports an evaluation of the other players' contribution.
The main properties required from a mechanism are impartiality -- a player's share of credit should
only depend on the other players' reports, and consensuality -- if there exists a division that agrees with all the individual reports,
then that division should be the outcome. Clippel \emph{et al.} show that for three players, there exists a unique impartial and
consensual mechanism.

Kleinberg and Oren \cite{Kleinberg_STOC} study a noncooperative model for the allocation of scientific credit. Their main finding is
that research communities may have to over-reward their key scientific challenges, to ensure that such problems are solved in a Nash
equilibrium.

Jackson and Wolinsky \cite{Jackson_Wolinsky} introduce a co-author model with network externalities, where each player has a unit
of time and can divide it among different collaborations. The output of each project depends on the total time invested in it by the
two collaborators, and the structure of the networks that arise in equilibrium depends on the synergies between the players.

Anshelevich and Hoefer \cite{Hoefer} study contribution games on networks, where the players have concave or convex reward
functions, and give bounds on the price of anarchy.
Anshelevich \emph{et al} \cite{Anshelevich} study contribution games where the players are embedded in a social context and may incorporate friendship relations
or altruism into their decisions, and analyze the social welfare in the equilibrium.

\section{Discussion and Future Work}
We introduced the first game theoretic model for studying author ordering schemes. Our model proposes possible causes for phenomenon previously observed empirically. Namely, we show that alphabetical ordering encourages collaboration between players of the same type, in particular, leading to collaboration between the strongest players in the community. This may explain the previously observed correlation between the use of alphabetical author ordering and higher research quality.

Furthermore, our model leads to several predictions on the effects of author ordering schemes commonly applied in academia. Most notably, we show that rotations can be used to overcome some of the limitations of contribution-based ordering schemes. This phenomenon suggests an avenue for future empirical investigation. In particular, it would be interesting to explore how frequently rotations appear in practice, as well as their influence on individuals and the community at large.

There are also several natural extensions of our model left for future investigation. For instance, we could consider continuously divisible budgets,
which would allow players to arbitrarily partition their resources among multiple projects.
Another natural generalization is to formulate a nontransferable utility game with overlapping coalitions, and study the stable outcomes using the
core solution concept. Furthermore, the game can be studied under more general families of reward functions, such as concave and convex functions.
Preliminary analysis confirms some of our main findings in these generalized settings,
in particular the finding that alphabetical ordering leads to high research quality.

\section{Acknowledgements}


We thank Peter Bro Miltersen and Yair Zick for valuable discussion.



\newpage
\section{Appendix A}

%\setcounter{lemma}{0}

\subsection{Omitted Proofs: Indivisible Budgets}
\textbf{Theorem~\ref{thm:two_layer}} (restated):
\emph{
Consider an academic game with indivisible budgets and two types of players, of weights $1$ and $\lambda$, respectively, where $0 < \lambda < 1$.
Then every pairwise stable coalition structure has
\begin{enumerate}
\item Only same-layer collaborations when $\frac{(1+\lambda)^r}{2^r + (1+\lambda)^r} < \phi < \min\left(1 - \frac{1}{2^r}, \frac{1}{(1+ \lambda)^r}, \frac{2^r}{2^r + (1+\lambda)^r}\right)$.
\item Only cross-layer collaborations when $\max\left( 1 - \frac{1}{2^r}, \frac{1}{(1+\lambda)^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$.
\item No collaboration when $1 - \frac{1}{2^r} < \phi < \frac{1}{(1+ \lambda)^r}$ or
$\phi > \max\left( 1 - \frac{1}{2^r}, 1 - \left( \frac{\lambda}{1 + \lambda}\right)^r\right)$.
\end{enumerate}
}
\begin{proof}
The proof follows from Lemma \ref{lem:two_player_same_layer}, Lemma \ref{lem:two_layer_cross}, and Lemma \ref{lem:two_layer_none} below.
\end{proof}


\begin{lemma} \label{lem:two_player_same_layer}
Consider an academic game with indivisible budgets and two types of players, of weights $1$ and $\lambda$, respectively, where $0 < \lambda < 1$.
Then every pairwise stable coalition structure has only same-layer collaborations when
 $\frac{(1+\lambda)^r}{2^r + (1+\lambda)^r} < \phi < \min\left(1 - \frac{1}{2^r}, \frac{1}{(1+ \lambda)^r}, \frac{2^r}{2^r + (1+\lambda)^r}\right)$.
\end{lemma}
\begin{proof}
For every pairwise stable coalition structure to solve the maximum number of same-layer collaborations, it should be the case
that whenever a coalition structure contains:
\begin{itemize}
\item 2 identical singleton projects: the two players can improve their utility by deviating to a pair. That is, $(1-\phi)\cdot 2^r > 1$
and $(1 - \phi) \cdot (2\lambda)^r > \lambda^r$, i.e. $\phi < 1 - \frac{1}{2^r}$.
\item 2 cross-layer projects: then there exists an improving deviation by two players from the same layer.
It is sufficient to require that the two heavy players involved in the cross layer projects deviate together: $\phi \cdot 2^r > \phi \cdot (1 + \lambda)^r$ and
$(1-\phi) \cdot 2^r > (1 - \phi) \cdot (1 + \lambda)^r$. Thus $\phi < \frac{2^r}{2^r + (1 + \lambda)^r}$.
\item 1 cross-layer project and 1 heavy singleton project: then the two heavy players deviate to a pair. The two heavy players can deviate
to a pair when $\phi \cdot 2^r > \phi \cdot (1 + \lambda)^r$ and $(1-\phi)2^r > 1$, i.e. $\phi < 1 - \frac{1}{2^r}$.
\item 1 cross-layer project and 1 light singleton project: then the two light players deviate to a pair. The two light players
can deviate to a pair when $\phi \cdot (2\lambda)^r > (1-\phi)(1+\lambda)^r$ and $(1-\phi)(2\lambda)^r > \lambda^r$.
That is, $\frac{(1+\lambda)^r}{(2\lambda)^r + (1+\lambda)^r} < \phi < 1 - \frac{1}{2^r}$.
\end{itemize}
In addition, we require that no intermediate project is solved, even when the maximum number of hard projects is completed.
That is, a coalition of weight $1+ \lambda$ is blocked by a deviation to a singleton by one of the players, i.e. $\phi < \frac{1}{(1+\lambda)^r}$ or $\phi > 1 - \left( \frac{\lambda}{1 + \lambda} \right)^r$.
It follows that
 $\frac{(1+\lambda)^r}{2^r + (1+\lambda)^r} < \phi < \min\left(1 - \frac{1}{2^r}, \frac{1}{(1+ \lambda)^r}, \frac{2^r}{2^r + (1+\lambda)^r}\right)$.
\end{proof}



\begin{lemma}  \label{lem:two_layer_cross}
Consider an academic game with indivisible budgets and two types of players, of weights $1$ and $\lambda$, respectively, where $0 < \lambda < 1$.
Then every pairwise stable coalition structure has the maximum number of cross-layer collaborations when
$\max\left(\frac{1}{(1+\lambda)^r}, 1 - \frac{1}{2^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$.
\end{lemma}
\begin{proof}
For every pairwise stable coalition structure to solve the maximum number of cross-layer collaborations, it should be the case that
whenever a coalition structure contains:
\begin{itemize}
\item 2 singleton projects of different weights: then the two players can deviate to a pair. That is, $\phi \cdot (1 + \lambda)^r > 1$
and $(1-\phi)(1 + \lambda)^r > \lambda^r$, i.e. $\frac{1}{(1+\lambda)^r} < \phi < 1 - \left(\frac{\lambda}{1+\lambda}\right)^r$.
\item 1 same-layer project by two heavy players and 1 light singleton project: then the light player deviates with one of the two heavy players.
That is,
$\phi \cdot (1 + \lambda)^r > (1 - \phi) \cdot 2^r$
and
$(1-\phi)(1+\lambda)^r > \lambda^r$, and so $\frac{1}{1 + \left( \frac{1+\lambda}{2} \right)^r} < \phi < 1 - \left( \frac{\lambda}{1 + \lambda} \right)^r$.
\item 1 same-layer project by two light players and 1 heavy singleton project: then the heavy player deviates with one of the light players.
That is, $(1-\phi)\cdot (1 + \lambda)^r > (1-\phi)(2\lambda)^r$ and $\phi \cdot (1 + \lambda)^r > 1$, i.e. $\phi > \frac{1}{(1 + \lambda)^r}$.
\item 2 same-layer projects of different weights: Then one of the heavy players deviates with one of the light players.
That is, $\phi \cdot (1 + \lambda)^r > (1 - \phi) \cdot 2^r$ and
$(1-\phi)\cdot (2\lambda)^r < (1-\phi) \cdot (1 + \lambda)^r$, i.e. $\phi > \frac{1}{1 + \left( \frac{1+\lambda}{2}\right)^r}$.
\end{itemize}
In addition, we require that even when the maximum number of cross layer collaborations occurs, if there exists a same-layer project, it is blocked by a deviation of the second player, who prefers to work alone. That is, $\phi > 1 - \frac{1}{2^r}$, and so
$\max\left(\frac{1}{(1+\lambda)^r}, 1 - \frac{1}{2^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$.
\end{proof}

\begin{lemma}  \label{lem:two_layer_none}
Consider an academic game with indivisible budgets and two types of players, of weights $1$ and $\lambda$, respectively, where $0 < \lambda < 1$.
Then no pairwise stable coalition structure has collaborations when $1 - \frac{1}{2^r} < \phi < \frac{1}{(1+ \lambda)^r}$ or
$\phi > \max\left( 1 - \frac{1}{2^r}, 1 - \left( \frac{\lambda}{1 + \lambda}\right)^r\right)$.
\end{lemma}
\begin{proof}
There are two cases. If the coalition structure contains a same-layer project, then it is blocked by one of the players, who deviates to a singleton.
That is, $(1-\phi)\cdot 2^r < 1$. If the coalition structure contains a cross-layer project, then again one of the players deviates to a singleton.
That is,
either $\phi \cdot (1 + \lambda)^r < 1$ or $(1-\phi) \cdot (1 + \lambda)^r < \lambda^r$.
Thus every pairwise stable coalition structure contains only singleton projects when either $1 - \frac{1}{2^r} < \phi < \frac{1}{(1+ \lambda)^r}$ or
$\phi > \max\left( 1 - \frac{1}{2^r}, 1 - \left( \frac{\lambda}{1 + \lambda}\right)^r\right)$.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textbf{Theorem~\ref{different players fairness}} (restated):
\emph{Consider an academic game with two types of players, of weights 1 and $\lambda$, respectively. If
 $\phi$ is in the range $\max\left( 1 - \frac{1}{2^r}, \frac{1}{(1+\lambda)^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$, then in every pairwise stable coalition structure:
\begin{itemize}
\item If $\phi < \frac{1}{\lambda}$, all the heavy players involved in a collaboration incur a loss of $1-\phi(1+\lambda)$ due to unfairness.
\item If $\phi > \frac{1}{\lambda}$, all the light players involved in a collaboration incur a loss of $1-\frac{(1-\phi)(1+\lambda)}{\lambda}$ due to unfairness.
\end{itemize}
}
\begin{proof}
By Theorem~\ref{thm:two_layer}, the condition: $\max\left( 1 - \frac{1}{2^r}, \frac{1}{(1+\lambda)^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$ ensures there are only cross-layer collaborations. Then all the players of weight $1$ paired with a player of weight $\lambda$  incur a loss of  $2\phi-1$ due to unfairness.

The fair contribution vector for every cross-layer coalition is $(\frac{1}{1+\lambda}, \frac{\lambda}{1+\lambda}).$ If follows that if $\phi < \frac{1}{\lambda}$, then the contribution vector favours the second player, and all the heavy players paired with a light player incur a loss of $1-\phi(1+\lambda)$ due to unfairness. Otherwise, all the light players paired with a heavy player incur a loss of $1-\frac{(1-\phi)(1+\lambda)}{\lambda}$ due to unfairness.
\end{proof}


\subsection{Omitted Proofs: Discrete Budgets}

%\setcounter{theorem}{1}

\begin{comment}

\begin{theorem}
Consider an academic game with two types of players, of weights $1$ and $\lambda$, respectively, and conference tier $1 + \lambda$,
where $0 < \lambda < 1$.
Then the highest number of hard projects is solved when $\frac{(1+\lambda)^r}{2^r + (1+\lambda)^r} < \phi < \min\left(1 - \frac{1}{2^r}, \frac{1}{(1+ \lambda)^r}, \frac{2^r}{2^r + (1+\lambda)^r}\right)$,
and the highest number of intermediate projects is solved when $\max\left( 1 - \frac{1}{2^r}, \frac{1}{(1+\lambda)^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$.
\end{theorem}
\begin{proof}
The proof follows from the conditions in Theorem \ref{thm:two_layer}. Observe that in particular, alphabetical ordering guarantees the highest number of hard projects
solved in a pairwise stable equilibrium for every $\lambda \in (0,1)$.
\end{proof}
\end{comment}
%\setcounter{proposition}{2}


\begin{comment}
\begin{proposition}
Consider an academic game with different players and indivisible budgets. Then a pairwise stable coalition structure can be found in polynomial time when it exists.
\end{proposition}
\begin{proof}
The game is an instance of the
stable roommates problem with ties and incomplete lists, where a player $i$ finds another player $j$ unacceptable if $i$ prefers working alone instead
of forming a pair with $j$.
\end{proof}
\end{comment}

\begin{comment}
\begin{todo}
Unless we include a full section on the existence of stable coalition structures for discrete budgets, remove this proposition altogether.
\end{todo}
\setcounter{proposition}{3}

\begin{proposition}
Consider an academic game with discrete budgets and multiple identical coins. Then a pairwise stable coalition structure exists
for every $\phi$ under deterministic tie-breaking rules.
\end{proposition}
\begin{proof}
%TODO: Similar to the proof for indivisible identical budgets.
Without loss of generality, assume that the tie-breaking rule is $[1, \ldots, n]$.
If $\phi \geq 1 - \frac{1}{2^r}$, then the coalition structure in which every coin is a singleton is pairwise stable.
If $\phi < 1 - \frac{1}{2^r}$, consider the following coalition structure.
Pair every coin of player $n$ with the next available coin of another player in $N \setminus \{n\}$, where the players
in $N \setminus \{n\}$ are taken in reverse order, and a player $k$ is only considered when there are no available coins
from the players in $\{n-1, \ldots, k+1\}$.
After all the coins of player $n$ have been matched (or there are no available pairs), repeat with the remaining players
in the order $\{n-1, \ldots, 1\}$ and their unmatched coins.
We show that the resulting coalition structure is pairwise stable. Consider player $n$. If all of $n$'s coins have been matched, then
$n$ obtains his maximum possible utility. The condition on $\phi$ ensures that moving a coin to a singleton project
decreases $n$'s utility, and due to the tie-breaking rule, $n$ can never be listed as first author. Similarly, if $n$ has any unmatched
coins, then during the iteration of the algorithm there were no available coins, and $n$ still obtains his highest possible utility.
Thus $n$ cannot improve by deviating. Iteratively, it can be shown that no player $k$ can deviate
given that players $\{n, \ldots, k+1\}$ do not participate in deviations, and so the coalition structure is pairwise stable.
\end{proof}
\end{comment}


\textbf{Theorem~\ref{thm:two_layer_discrete}} (restated):
\emph{Consider an academic game with discrete budgets, where each player has two types of coins, of size $1$ and $\lambda$, respectively.
Then every pairwise stable coalition structure:
\begin{enumerate}
\item has only equal effort collaborations when $\frac{(1+\lambda)^r}{2^r + (1+\lambda)^r} < \phi < \min\left(1 - \frac{1}{2^r}, \frac{1}{(1+ \lambda)^r}, \frac{2^r}{2^r + (1+\lambda)^r}\right)$.
\item has only unequal effort collaborations when  $\max\left( 1 - \frac{1}{2^r}, \frac{1}{(1+\lambda)^r}, \frac{2^r}{2^r+ (1+\lambda)^r}\right) < \phi < 1 - \left( \frac{\lambda}{1+ \lambda} \right)^r$.
\item has no collaborations when $1 - \frac{1}{2^r} < \phi < \frac{1}{(1+ \lambda)^r}$ or
$\phi > \max\left( 1 - \frac{1}{2^r}, 1 - \left( \frac{\lambda}{1 + \lambda}\right)^r\right)$.
\end{enumerate}
}
\begin{proof}
The proof follows from Theorem \ref{thm:two_layer}. Note that whenever two players have a singleton coin each, they will form
a joint project if the coins are identical and $\phi$ is in the range in case 1, or if the coins are different and $\phi$ is in the range of case 2.
\end{proof}

%\setcounter{theorem}{8}

\textbf{Theorem~\ref{alpha fairness discrete}} (restated):
\emph{Consider an academic game with discrete budgets and identical coins. Then alphabetical ordering is the unique fair contribution vector. When $\phi > 1 - \frac{1}{2^r}$,
 up $n-1$ players can incur a loss due to unfairness of $2\phi-1$.}
\begin{proof}
Since all coins are identical, alphabetical ordering is the fair contribution vector. We now consider the loss incurred for arbitrary $\phi$.
Consider the case where one of the players has $n-1$ coins and the rest of the players have one coin each. The coalition structure where the player with many coins collaborate with every player that has a single coin, and the player with many coins is the first author on all of his projects. Given the lower bound on $\phi$, the player will not deviate to work along. Furthermore, no pair of player with a single coin will deviate to work together because at least one of them would not improve his or her utility by deviating.
\end{proof}

%\setcounter{proposition}{4}
\textbf{Proposition~\ref{rotations1}} (restated):
\emph{There exist academic games with discrete budgets and multiple identical coins
such that for every $\phi$, the maximum number of hard projects is solved in a refined pairwise stable equilibrium and no player suffers any loss due to unfairness.}
\begin{proof}
Let $\phi < 1$ and consider a two player game, such that player $1$ has coins $\{c_{1,1}, c_{1,2}\}$, player $2$
has coins $\{c_{2,1}, c_{2,2}\}$, and all the coins have weight $1$. Consider the coalition structure $CS = (C_1, C_2)$, where
$C_1 = \{c_{1,1}, c_{2,1}\}$ and $C_2 = \{c_{2,2}, c_{1,2}\}$, such that player $1$ is the first author on project $C_1$ and player
$2$ is the first author on project $C_2$. It can be verified that both players receive the best possible utility, which coincides
with the fair allocation given by alphabetical ordering.
Moreover, the coalition structure is pairwise stable.
None of the players can gain by investing the coin from their second-author project to a singleton project, since the other player
will retaliate and drop the other project as well.
\end{proof}

%\setcounter{proposition}{5}
\textbf{Proposition~\ref{rotations2}} (restated):
\emph{
Let $1-\lambda$ be the conference tier. There there exist academic games with discrete budgets, where each player has two types of coins, one of size $1$ and one of size $\lambda$, so that there is no loss due to unfairness in the refined pairwise stable equilibrium.}
\begin{proof}
Consider the two player game where every player has $2m$ coins of size $1$ and $2m$ coins of size $\lambda$. The players can then create $2m$ projects, each of size $1+ \lambda$, and have each player be the first author on exactly $m$ projects. Then the total contribution corresponds to the total credit received, resulting in loss due to unfairness over all projects. Moreover, the coalition structure is pairwise stable. None of the players can receive any utility from working alone using any of their coins.
\end{proof}

%\setcounter{proposition}{5}

\begin{comment}
\textbf{Proposition~\ref{rotations_identical} (restated)}:
\emph{There exist academic games with discrete budgets and multiple identical coins
such that for every $\phi$, the maximum number of hard projects is solved in a refined pairwise stable equilibrium and no player suffers any loss due to unfairness.}
\begin{proof}
Let $\phi < 1$ and consider a two player game, such that player $1$ has coins $\{c_{1,1}, c_{1,2}\}$, player $2$
has coins $\{c_{2,1}, c_{2,2}\}$, and all the coins have weight $1$. Consider the coalition structure $CS = (C_1, C_2)$, where
$C_1 = \{c_{1,1}, c_{2,1}\}$ and $C_2 = \{c_{2,2}, c_{1,2}\}$, such that player $1$ is the first author on project $C_1$ and player
$2$ is the first author on project $C_2$. It can be verified that both players receive the best possible utility, which coincides
with the fair allocation given by alphabetical ordering.
Moreover, the coalition structure is pairwise stable.
None of the players can gain by investing the coin from their second-author project to a singleton project, since the other player
will retaliate and drop the other project as well.
\end{proof}
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\setcounter{proposition}{7}
\textbf{Proposition~\ref{social network result}} (restated):
\emph{
Consider an academic game with discrete budgets, where each player has several big and small coins,
of sizes $1$ and $\varepsilon$, respectively, where $0 < \varepsilon \ll 1$, and the conference tier is $1$.
The small coins represent ``cheap talk'', and we assume that each player has more big coins than small coins.
Then when $\phi > \max \left(\frac{2^r}{2^r + (1+\varepsilon)^r}, \frac{1}{(1+\varepsilon)^r}\right)$,
every pairwise stable equilibrium solves the maximum number of projects and the average number of
collaborators per player is the highest possible.}
\begin{proof}
To ensure that every pairwise stable coalition structure solves the maximum number of collaborations, it should be the case that
the best way in which a player can invest a big coin is by pairing it with a small coin.
 That is, a player prefers being the first author on a project of weight $1+\varepsilon$ instead of either
second author on a hard project or the only author
on a singleton project. The conditions are: $(1-\phi) \cdot 2^r < \phi \cdot (1+\varepsilon)^r$ and $\phi \cdot (1+\varepsilon)^r > 1$, or equivalently, $\phi > \max \left(\frac{1}{(1+\varepsilon)^r}, \frac{2^r}{2^r + (1+\varepsilon)^r}\right)$.
Then in every pairwise stable coalition structure, all the big coins are paired with small coins, and the average number
of collaborators is maximal.
We note that while alphabetical ordering solves the highest number of hard projects, both the number of projects
completed and the number of collaborators is twice as low.
Finally, the singleton coalition structure solves the same number of projects above the conference tier. 
However, in this case, the players have no collaborators, and the quality of the projects completed is lower compared to the case when cheap talk is allowed.
\end{proof}



\subsection{Appendix B}

We show that alphabetical author ordering guarantees the existence of a pairwise stable coalition structure; Furthermore, it can always be found in polynomial time. In contrast, the use of contribution based ordering can result in there being no pairwise stable solutions. 

\begin{comment}
\begin{theorem}
Every academic game with identical players and indivisible budgets has a pairwise stable coalition structure under deterministic tie-breaking rules.
\end{theorem}
\begin{proof}
Without loss of generality, assume that the deterministic tie-breaking rule lists the
players in the order $[1, \ldots, n]$.
If $\phi \geq 1 - \frac{1}{2}$, then the singleton coalition structure, $CS = (\{1\}, \ldots, \{n\})$ is pairwise stable,
since no player can improve their utility by being second author on a project.
If $\phi < 1 - \frac{1}{2^r}$, there are two cases. If
$n$ is even, then $CS^{'} = (\{1,2\}, \ldots, \{n-1, n\})$ is pairwise stable.
If $n$ is odd, then $CS^{''} = (\{2,3\}, \ldots, \{n-1, n\}, \{1\})$, is pairwise stable, since no player has an incentive to
switch to a singleton, the coalition structure given by $CS^{''} \setminus \{1\}$ is pairwise stable (by case 1), and
player $1$ cannot be part of a deviating pair, since no other player has an incentive to join $1$ as a second author.
\end{proof}
\end{comment}


\begin{theorem}
Consider an academic game with different players and indivisible budgets.
Under alphabetical ordering, a pairwise stable coalition structure is guaranteed to exist and can be
computed in polynomial time.
\end{theorem}
\begin{proof}
Let $N = \{1, \ldots, n\}$ be the set of players and without loss of generality, let $w_1 \geq w_2 \geq \ldots \geq w_n$.
Start with an empty coalition structure: $CS = \emptyset$. Iteratively, pair whenever possible the two players with the heaviest weights
among the remaining players. Let $\{k, k+1, \ldots, n\}$ be the remaining set of players during some iteration.
If $\frac{1}{2}(w_{k} + w_{k+1})^{r} \geq w_{k}^{r}$ and $\frac{1}{2}(w_{k}+ w_{k+1})^{r} \geq w_{k+1}^{r}$, then
let $CS \leftarrow CS \cup \{k, k + 1\}$, otherwise, $CS \leftarrow CS \cup \{k\}$.
We claim that the resulting coalition structure, $CS$, is pairwise stable. If $CS$ contains coalition $\{1, 2\}$,
then player $1$ does not have an incentive to form another
pair or move to a singleton, since $u(1, CS) \geq w_{1}^{r}$ and $u(1, CS) \geq \frac{1}{2}(w_1 + w_j)^{r}$, $\forall j \in N \setminus \{1\}$.
Similarly, player $1$ does not deviate if a singleton in $CS$. Iteratively, whenever the first $k$ players do
not have an incentive to deviate, player $k + 1$ does not have an incentive to deviate either. Thus $CS$ is pairwise stable.
\end{proof}


On the other hand, contribution-based ordering
does not guarantee the existence of stable coalition structures even under fixed tie-breaking rules.

\begin{proposition}
There exist academic games with different players and indivisible budgets,
such that when contribution-based ordering is used, no pairwise stable coalition structure exists.
\end{proposition}
\begin{proof}
Consider a three player game, with weights $1$, $1+ \varepsilon$, and $1 + 2 \varepsilon$, respectively, where $r= 2$, $\varepsilon = 0.8$,
and $\phi = 0.8$. It can be easily verified that no coalition structure is stable. The singleton coalition structure is blocked by the players
with weights $\{1,1+\varepsilon\}$, the coalition structure $CS = (\{1+\varepsilon, 1\}, \{1 + 2 \varepsilon\})$ is blocked by $\{1+2\varepsilon,1\}$,
$CS^{'} = (\{1+2\varepsilon,1+\varepsilon\},\{1\})$ is blocked by $\{1+\varepsilon,1\}$, and
$CS^{''} = (\{1+2\varepsilon,1\}, \{1+\varepsilon\})$ is blocked by $\{1+2\varepsilon,1+\varepsilon\}$.
\end{proof}

\begin{comment}
\begin{proposition}
Consider an academic game with different players and indivisible budgets. Then a pairwise stable coalition structure can be found in polynomial time when it exists.
\end{proposition}
\begin{proof}
The game is an instance of the
stable roommates problem with ties and incomplete lists, where a player $i$ finds another player $j$ unacceptable if $i$ prefers working alone instead
of forming a pair with $j$.
\end{proof}
\end{comment}

\section{Appendix C}
We illustrate pairwise stability for discrete budgets using the following example.
\begin{example}
Consider an academic game with three players, sets of coins: $C_1 = \{c_{1,1}, c_{1,2}\}$, $C_2 = \{c_{2,1}, c_{2,2}\}$, and
$C_3 = \{c_{3,1}, c_{3,2}\}$, and the coalition structure $CS = (\{c_{1,1}, c_{2,1}\}, \{c_{2,2}, c_{3,1}\}, \{c_{1,2}, c_{3,2}\})$.

If player $1$ deviates by allocating the coin $c_{1,2}$ to a singleton project, then $1$ expects that the resulting coalition
structure is $CS^{'} = (\{c_{1,1}, c_{2,1}\}, \{c_{1,2}\}, \{c_{3,2}\}, \{c_{2,2}, c_{3,1}\})$, since player $2$ is not hurt by the
deviation.

On the other hand, if the deviating coalition is $\{1,2\}$ and the deviation consists of forming the joint project $\{c_{1,1}, c_{2,2}\}$,
then players $1$ and $2$ can expect that the resulting coalition structure is $CS^{''} = (\{c_{1,1}, c_{2,2} \}, \{c_{2,1} \}, \{c_{1,2}\},
\{c_{3,1}\}, \{c_{3,2}\})$, since player $3$ is hurt by the deviation and drops \emph{all} the projects with the deviators.
\end{example}


\bibliographystyle{plain}
%\bibliography{academic_refs}
%\nocite{*}
\begin{thebibliography}{}

\bibitem{Anshelevich}
E.~Anshelevich, O.~Bhardwaj, and M.~Hoefer.
\newblock {Friendship, Altruism, and Reward Sharing in Stable Matching and
  Contribution Games}.
\newblock {\em http://arxiv.org/abs/1204.5780}, 2012.

\bibitem{Hoefer}
E.~Anshelevich and M.~Hoefer.
\newblock {Contribution Games in Social Networks}.
\newblock {\em Algorithmica}, 63(1-2):51--90, 2012.

\bibitem{APA}
American~Psychological Association.
\newblock {\em {APA Style Manual}}.
\newblock 1994.

\bibitem{Bachrach}
Y.~Bachrach and J.~Rosenschein.
\newblock {Coalitional Skill Games}.
\newblock In {\em Proceedings of AAMAS}, 2003.

\bibitem{Brown}
C.~L. Brown, K.~C. Chan, and P.~Lai.
\newblock {Marketing Journal Coauthorships: An Empirical Analysis of Coauthor
  Behavior}.
\newblock {\em Journal of Marketing Education}, 28(1):17--25, 2006.

\bibitem{Elkind}
G.~Chalkiadakis, E.~Elkind, E.~Markakis, M.~Polukarov, and N.~R. Jennings.
\newblock {Cooperative Games with Overlapping Coalitions}.
\newblock {\em Journal of Artificial Intelligence Research (JAIR)},
  39:179--216, 2010.

\bibitem{Moulin}
G.~de~Clippel, H.~Moulin, and N.~Tideman.
\newblock Impartial division of a dollar.
\newblock {\em Journal of Economic Theory}, 139(1):176--191, 2008.

\bibitem{Efthyvoulou}
G.~Efthyvoulou.
\newblock {Alphabet Economics: The Link Between Names and Reputation}.
\newblock {\em Journal of Socio-Economics}, 37(3):1266--1285, 2008.

\bibitem{Einav}
L.~Einav and L.~Yariv.
\newblock {What's in a Surname? The Effects of Surname Initials on Academic
  Success}.
\newblock {\em Journal of Economic Perspectives}, 20(1):175--88, 2006.

\bibitem{Elkind_wvg}
E.~Elkind, G.~Chalkiadakis, and N.~R. Jennings.
\newblock {Coalition Structures in Weighted Voting Games}.
\newblock In {\em Proceedings of ECAI}, pages 393--397, 2008.

\bibitem{Engers}
M.~Engers, J.S. Gans, S.~Grant, and S.P. King.
\newblock {First-Author Conditions}.
\newblock {\em The Journal of Political Economy}, 107(4):859--883, 1999.

\bibitem{Jackson}
M.~O. Jackson.
\newblock {\em {Social and Economic Networks}}.
\newblock Princeton University Press, 2008.

\bibitem{Jackson_Wolinsky}
M.~O. Jackson and A.~Wolinsky.
\newblock {A Strategic Model of Social and Economic Networks}.
\newblock {\em Journal of Economic Theory}, 71:44--74, 1996.

\bibitem{Joseph}
K.~Joseph, D.~N. Laband, and V.~Patil.
\newblock {Author Order and Research Quality}.
\newblock {\em Southern Economic Journal}, 71(3), 2005.

\bibitem{Kleinberg_STOC}
J.~Kleinberg and S.~Oren.
\newblock {Mechanisms for (Mis)Allocating Scientific Credit}.
\newblock In {\em Proceedings of STOC}, 2011.

\bibitem{Laband}
D.~Laband and R.~Tollison.
\newblock {Alphabetized Coauthorship}.
\newblock {\em Applied Economics}, 38(14):1649--1653, 2006.

\bibitem{Lake}
D.~A. Lake.
\newblock {Who's on First? Listing Authors by Relative Contribution Trumps the
  Alphabet}.
\newblock {\em Political Science and Politics}, 43:43--47, 2010.

\bibitem{Newman}
M.~E.~J. Newman.
\newblock {Coauthorship Networks and Patterns of Scientific Collaboration}.
\newblock In {\em Proceedings of the National Academy of Sciences}, volume 101,
  pages 5200--5205, 2004.

\bibitem{AGT_book}
N.~Nisan, T.~Roughgarden, E.~Tardos, and V.~Vazirani (editors).
\newblock {\em {Algorithmic Game Theory}}.
\newblock Cambridge University Press, 2007.

\bibitem{Ariel_blog}
A.~D. Procaccia.
\newblock {Impartial Division of Scientific Credit}.
\newblock {\em Turing's Invisible Hand}.
\newblock
  http://agtb.wordpress.com/2012/07/11/impartial-division-of-scientific-credit.

\bibitem{AMS}
American~Mathematics Society.
\newblock {\em {The Culture of Research and Scholarship in Mathematics: Joint
  Research and Its Publication}}.
\newblock 2004.

\bibitem{Praag}
M.~van Praag and B.~van Praag.
\newblock {The Benefits of Being Economics Professor A (and not Z)}.
\newblock {\em Jena Economic Research Papers}, (07-048/3), 2007.

\bibitem{Zick}
Y.~Zick, G.~Chalkiadakis, and E.~Elkind.
\newblock {Overlapping Coalition Formation Games: Charting the Tractability
  Frontier}.
\newblock In {\em Proceedings of AAMAS}, pages 787--794, 2012.

\end{thebibliography}

\end{document}






1208.3391.extracted_bib
\begin{thebibliography}{}

\bibitem{Anshelevich}
E.~Anshelevich, O.~Bhardwaj, and M.~Hoefer.
\newblock {Friendship, Altruism, and Reward Sharing in Stable Matching and
  Contribution Games}.
\newblock {\em http://arxiv.org/abs/1204.5780}, 2012.

\bibitem{Hoefer}
E.~Anshelevich and M.~Hoefer.
\newblock {Contribution Games in Social Networks}.
\newblock {\em Algorithmica}, 63(1-2):51--90, 2012.

\bibitem{APA}
American~Psychological Association.
\newblock {\em {APA Style Manual}}.
\newblock 1994.

\bibitem{Bachrach}
Y.~Bachrach and J.~Rosenschein.
\newblock {Coalitional Skill Games}.
\newblock In {\em Proceedings of AAMAS}, 2003.

\bibitem{Brown}
C.~L. Brown, K.~C. Chan, and P.~Lai.
\newblock {Marketing Journal Coauthorships: An Empirical Analysis of Coauthor
  Behavior}.
\newblock {\em Journal of Marketing Education}, 28(1):17--25, 2006.

\bibitem{Elkind}
G.~Chalkiadakis, E.~Elkind, E.~Markakis, M.~Polukarov, and N.~R. Jennings.
\newblock {Cooperative Games with Overlapping Coalitions}.
\newblock {\em Journal of Artificial Intelligence Research (JAIR)},
  39:179--216, 2010.

\bibitem{Moulin}
G.~de~Clippel, H.~Moulin, and N.~Tideman.
\newblock Impartial division of a dollar.
\newblock {\em Journal of Economic Theory}, 139(1):176--191, 2008.

\bibitem{Efthyvoulou}
G.~Efthyvoulou.
\newblock {Alphabet Economics: The Link Between Names and Reputation}.
\newblock {\em Journal of Socio-Economics}, 37(3):1266--1285, 2008.

\bibitem{Einav}
L.~Einav and L.~Yariv.
\newblock {What's in a Surname? The Effects of Surname Initials on Academic
  Success}.
\newblock {\em Journal of Economic Perspectives}, 20(1):175--88, 2006.

\bibitem{Elkind_wvg}
E.~Elkind, G.~Chalkiadakis, and N.~R. Jennings.
\newblock {Coalition Structures in Weighted Voting Games}.
\newblock In {\em Proceedings of ECAI}, pages 393--397, 2008.

\bibitem{Engers}
M.~Engers, J.S. Gans, S.~Grant, and S.P. King.
\newblock {First-Author Conditions}.
\newblock {\em The Journal of Political Economy}, 107(4):859--883, 1999.

\bibitem{Jackson}
M.~O. Jackson.
\newblock {\em {Social and Economic Networks}}.
\newblock Princeton University Press, 2008.

\bibitem{Jackson_Wolinsky}
M.~O. Jackson and A.~Wolinsky.
\newblock {A Strategic Model of Social and Economic Networks}.
\newblock {\em Journal of Economic Theory}, 71:44--74, 1996.

\bibitem{Joseph}
K.~Joseph, D.~N. Laband, and V.~Patil.
\newblock {Author Order and Research Quality}.
\newblock {\em Southern Economic Journal}, 71(3), 2005.

\bibitem{Kleinberg_STOC}
J.~Kleinberg and S.~Oren.
\newblock {Mechanisms for (Mis)Allocating Scientific Credit}.
\newblock In {\em Proceedings of STOC}, 2011.

\bibitem{Laband}
D.~Laband and R.~Tollison.
\newblock {Alphabetized Coauthorship}.
\newblock {\em Applied Economics}, 38(14):1649--1653, 2006.

\bibitem{Lake}
D.~A. Lake.
\newblock {Who's on First? Listing Authors by Relative Contribution Trumps the
  Alphabet}.
\newblock {\em Political Science and Politics}, 43:43--47, 2010.

\bibitem{Newman}
M.~E.~J. Newman.
\newblock {Coauthorship Networks and Patterns of Scientific Collaboration}.
\newblock In {\em Proceedings of the National Academy of Sciences}, volume 101,
  pages 5200--5205, 2004.

\bibitem{AGT_book}
N.~Nisan, T.~Roughgarden, E.~Tardos, and V.~Vazirani (editors).
\newblock {\em {Algorithmic Game Theory}}.
\newblock Cambridge University Press, 2007.

\bibitem{Ariel_blog}
A.~D. Procaccia.
\newblock {Impartial Division of Scientific Credit}.
\newblock {\em Turing's Invisible Hand}.
\newblock
  http://agtb.wordpress.com/2012/07/11/impartial-division-of-scientific-credit.

\bibitem{AMS}
American~Mathematics Society.
\newblock {\em {The Culture of Research and Scholarship in Mathematics: Joint
  Research and Its Publication}}.
\newblock 2004.

\bibitem{Praag}
M.~van Praag and B.~van Praag.
\newblock {The Benefits of Being Economics Professor A (and not Z)}.
\newblock {\em Jena Economic Research Papers}, (07-048/3), 2007.

\bibitem{Zick}
Y.~Zick, G.~Chalkiadakis, and E.~Elkind.
\newblock {Overlapping Coalition Formation Games: Charting the Tractability
  Frontier}.
\newblock In {\em Proceedings of AAMAS}, pages 787--794, 2012.

\end{thebibliography}