# Optimizing over Serial Dictatorships

Ioannis Caragiannis  Nidhi Rathi

(Department of Computer Science, Aarhus University
Åbogade 34, 8200 Aarhus N, Denmark
Email<EMAIL_ADDRESS>
###### Abstract

Motivated by the success of the serial dictatorship mechanism in social choice
settings, we explore its usefulness in tackling various combinatorial
optimization problems. We do so by considering an abstract model, in which a
set of agents are asked to act in a particular ordering, called the action
sequence. Each agent acts in a way that gives her the maximum possible value,
given the actions of the agents who preceded her in the action sequence. Our
goal is to compute action sequences that yield approximately optimal total
value to the agents (a.k.a., social welfare). We assume query access to the
value $v_{i}(S)$ that the agent $i$ gets when she acts after the agents in the
ordered set $S$.

We establish tight bounds on the social welfare that can be achieved using
polynomially many queries. Even though these bounds show a marginally
sublinear approximation of optimal social welfare in general, excellent
approximations can be obtained when the valuations stem from an underlying
combinatorial domain. Indicatively, when the valuations are defined using
bipartite matchings, arborescences in directed graphs, and satisfiability of
Boolean expressions, simple query-efficient algorithms yield
$2$-approximations. We discuss issues related to truthfulness and show how
some of our algorithms can be implemented truthfully using VCG-like payments.
Finally, we introduce and study the price of serial dictatorship, a notion
that provides an optimistic measure of the quality of combinatorial
optimization solutions generated by action sequences.

##  1 Introduction

Serial dictatorship (SD) is arguably the most straightforward algorithm with
numerous applications in many different settings [AS98, BM01, CFRF+16, KMRZ19,
RS90, FRFZ14, Sve99]. In the economics literature (e.g., see [AS98]), it was
first considered as a solution to the house allocation problem, where a set of
houses have to be matched to agents who have strict preferences for them. The
algorithm considers the agents in a fixed order and assigns the most-preferred
available house to each agent considered.

Crucially, SD can be used in a much more general context. Consider a scenario
with a set of agents, each having a menu of available actions and preferences
for them. The objective is to compute a set of collective actions, with one
action per agent. SD can perform the task by asking the agents to act in a
predefined order. Whenever it is an agent’s turn to act, she does so by
selecting the action that is best possible, given the actions of agents who
acted before. Previous actions may render some action of an agent unavailable
and they can furthermore change her initial preferences.

This is a paradigm with several advantages. From the computational point of
view, SD is as simple as possible. Furthermore, it is easily explainable to
the agents, who are expected to have a minimal interaction with it. As SD
never uses any input from the agents besides their actions, they have no other
option but to act truthfully, selecting their best available action. On the
negative side, the predefined order in which the agents are considered may
lead to inefficiencies [CFRF+16]. An agent who acts early may block actions
which might be highly beneficial to agents acting later. Random serial
dictatorship [AS98, BM01, FRFZ14, KMRZ19] is an attempt to address this
inefficiency without deviating from the main principles of SD. The main idea
is to consider the agents in a uniformly random order in the hope that
problematic orderings will be used only rarely. However, inefficiencies may
still happen [FRFZ14].

We attempt a radical improvement of SD and instead ask: what is the ordering
of the agents which SD must use in order to obtain the best possible results?
In other words, we are interested in optimizing over serial dictatorships for
a given problem. Of course, this task cannot be performed without using the
agent preferences and, as such, creates apparent incentives to the agents to
misreport their preferences in order to manipulate the outcome of the
optimization to their benefit.

To mitigate this, we seek algorithmic solutions that use agent input
sparingly. Starting with no information about the problem at hand, our
algorithms learn (part of) the preferences by posing queries to the agents. A
typical query to an agent asks for the value of her best possible action in an
agent ordering. Our objective is to study the query complexity [DV12] of
optimizing over serial dictatorships. Hence, we seek for algorithms that use
as few queries as possible.

###  1.1 Our contribution

At the highest level of abstraction, we define the problem OptimalSequence
that captures the essence of optimizing over serial dictatorships. Instances
of OptimalSequence consist of a set of $n$ agents. Each agent $i$ has a
valuation function which returns the value $v_{i}(S)$ she gets by her best
available action after the agents in the sequence $S$ have acted before $i$.
Our aim is to design algorithms that compute an agent ordering that gives high
value to the agents. Our benchmark is the social welfare, i.e., the total
value of all agents. An important restriction is low query complexity; we seek
for algorithms that use only polynomially many value queries. Our main result
(under a mild monotonicity assumption) is an asymptotically tight bound of
$\Theta\left(\frac{n\ln\ln{n}}{\ln{n}}\right)$ on the best approximation ratio
that can be achieved by such algorithms that use randomization.

Next, we consider refined OptimalSequence instances that may be relevant for
practical applications. We do so by assuming an underlying combinatorial
structure which defines the valuations. Indicatively, we present three
specific valuation structures, motivated by matching markets, network design,
and constraint satisfaction. These define three special cases of
OptimalSequence, which we call OSM, OSA, and OSS. In OSM, the agents have a
set of items as their available actions. Whenever it is an agent’s turn to
act, she picks the available item that is of highest value to her. In OSA, the
agents correspond to the nodes of a network and they can establish links to
other nodes as actions. Whenever it is an agent’s turn to act, she draws a
link of maximum value under the constraint that the network stays acyclic. In
OSS, each agent controls a Boolean variable and has two actions: setting her
variable to either True or False. These variables appear in a collection of
weighted clauses. Whenever it is an agent’s turn, she acts so that the weight
of new satisfied clauses is maximized.

It turns out that OSM, OSA, and OSS admit much better algorithms. We present
simple $2$-approximation algorithms for the three of them and leave open the
question of better approximation results or lower bounds on the query
complexity. We furthermore study computational questions related to the
existence of serial dictatorships that produce a given solution to the
underlying combinatorial problem. We prove that whether a given perfect
matching for OSM and a given arborescence for OSA can be produced by serial
dictatorships can be decided in polynomial time. In contrast, for OSS, we show
that deciding whether a given Boolean assignment can be produced by a serial
dictatorship is an NP-hard problem.

We also consider serial dictatorship as a solution concept and quantify the
restrictions it poses on the solutions of optimization problems by introducing
the notion of the price of serial dictatorship (PoSD). The PoSD of a
combinatorial optimization problem is the worst-case ratio over all instances
of the benefit of the optimal solution over the best social welfare obtained
by a serial dictatorship. We prove optimal bounds of $1$ for both maximum-
weight bipartite matching and maximum-weight arborescence in directed graphs.
In contrast, for maximum satisfiability, the PoSD is between $3/2$ and $2$.

Finally, we scratch the surface of truthful implementations of our algorithms.
We prove that our best algorithm for general instances of OptimalSequence has
a truthful implementation through VCG-like payments (see [Cla71]) which
require only polylogarithmically many queries to compute. Our algorithms for
OSM and OSA are shown to be non-truthful. For OSA, we present a very simple
randomized truthful mechanism that uses no payments.

Our work reveals many open problems; we give a list with the most important
ones later. We remark that the approach can be naturally extended to many
other combinatorial problems than the ones considered here.

###  1.2 Further related work

Serial dictatorship and its variations have been well-studied in the matching
literature [Man13]. It seems however that the approach we consider here has
not received attention therein. As an attempt to optimize serial
dictatorships, one can view the notion of greedy weighted matchings in
[DMS17]. A greedy weighted matching is one that can be produced by an
algorithm which starts from an empty matching and iteratively puts an edge of
maximum weight that is consistent with it. This is a restricted way to
optimize over serial dictatorships. Furthermore, the authors in [DMS17] study
the computational complexity of the problem assuming that the graph
information (i.e., the edge weights) is given to the algorithm upfront. The
notion of picking sequence in fair division [GLW21] is close to the action
sequences that we consider here; the crucial difference is that each agent can
appear several times in a picking sequence.

Optimizing over serial dictatorships can be thought of as a particular way of
exploiting greediness in computation. There have been several attempts to
formally define greedy algorithms, including their relations to matroids,
which are covered in classical textbooks on algorithm design [CLRS09]. In
relation to combinatorial optimization, the work on incremental priority
algorithms [BNR03, BBLM10, DI04] has conceptual similarities. Furthermore, for
maximum satisfiability, there is a ongoing research line (e.g., see [PSWZ17])
that aims to design simple greedy-like algorithms that achieve good
approximation ratios. However, all these studies neglect query complexity
questions.

Finally, we remark that value queries, similar in spirit to those we consider
here, have been used to solve the maximum welfare problem in combinatorial
auctions [LLN06]. The PoSD notion is inspired by the price of stability in
strategic games [ADK+08] and the price of fairness in allocation problems
[BFT11, CKKK12].

###  1.3 Roadmap

The rest of the paper is structured as follows. We give preliminary
definitions and our notation in Section 2. We then study the query complexity
of OptimalSequence in Section 3. The refinement of OptimalSequence with
specific valuation structures is presented in Section 4. The three case
studies on bipartite matchings, arborescences, and satisfiability follow in
Sections 5, 6, and 7. Issues related to truthful implementation are considered
in Section 8.

##  2 Preliminaries

We consider scenarios where a set of agents are asked to _act_ in a particular
order. Whenever it is the turn of an agent to act, she selects an action that
gives her the maximum possible value, given the actions of agents who acted
before her. In this section, we present basic definitions and notation for an
abstract model that captures such scenarios. Later, in Section 4, we refine
this model further to bring it closer to well-known combinatorial optimization
problems.

We denote by $n$ the number of agents, which we assume to be identified by the
integers in set $[n]=\\{1,2,...,n\\}$. An action sequence (respectively,
action subsequence) $S$ is an ordering $S=(S(1),S(2),...)$ of the agents in
$[n]$ (respectively, some of the agents in $[n]$). For a subset of agents
$C\subseteq[n]$, we denote by $\mathcal{S}_{C}$ the set of all action
(sub)sequences of the agents in $C$. For an agent $i\in[n]$, we write
$\mathcal{S}_{-i}$ to denote all possible action subsequences consisting of
agents from the set $[n]\setminus\\{i\\}$. We reserve the letters $S$ and
$\pi$ for use as action (sub)sequences.

For two action subsequences $S$ and $S^{\prime}$, we write $S^{\prime}\leq S$
if $S^{\prime}$ is an ordered subset of $S$, i.e., if all agents in
$S^{\prime}$ are also in $S$ and have the same relative ordering. We use
$S||i$ to denote the action (sub)sequence which is obtained by appending agent
$i$ to the action subsequence $S$. We use $S\setminus j$ to denote the action
subsequence obtained by removing agent $j$ from $S$, and preserving the order
of the remaining agents. For an action (sub)sequence $S$, we write $S^{i}$ to
denote the action subsequence consisting of the ordered set of agents that are
ranked ahead of agent $i$ in $S$. We sometimes use the term prefix to refer to
agents at the beginning of an action (sub)sequence. Clearly, for any agent $i$
who appears in action subsequence $S$, it is $S^{i}\leq S$. For an integer
$c\in[n]$, we denote by $S|_{c}$ the action subsequence consisting of the
first $c$ agents of $S$.

Every agent $i\in[n]$ has a valuation function
$v_{i}:\mathcal{S}_{-i}\mapsto\mathbb{R}_{\geq 0}$ which, for every action
subsequence $S\in\mathcal{S}_{-i}$, returns the value $v_{i}(S)$ that agent
$i$ gets when acting immediately after the agents in the action subsequence
$S$. We say that the valuations of an agent $i$ are monotone if for any two
action subsequences $S,S^{\prime}\in\mathcal{S}_{-i}$, $S^{\prime}\leq S$
implies $v_{i}(S^{\prime})\geq v_{i}(S)$. The social welfare $\mathrm{SW}(S)$
of an action sequence $S$ is the total value of the agents in the sequence,
i.e., $\mathrm{SW}(S)=\sum_{i\in[n]}{v_{i}(S^{i})}$.

We study the problem of computing an action sequence having maximum social
welfare, which we call OptimalSequence. In particular, an instance of
OptimalSequence consists of the valuation functions of $n$ agents and the
objective is to compute an action sequence of maximum social welfare. An
important limitation of our model is that the valuation functions are not
given to the algorithm as part of the input. Instead, the algorithms for
solving OptimalSequence can access the entry $v_{i}(S)$ of the valuation
function through a query. We are interested in algorithms that solve
OptimalSequence using a polynomial number of queries. In other words, we are
interested in understanding the query complexity of OptimalSequence. Notice
that exponentially many queries (for each agent $i$ and each action
subsequence in $\mathcal{S}_{-i}$) can always be used to learn the valuation
functions. Then, OptimalSequence can be solved exactly. We remark that
computational limitations are not our concern in this work and we assume to
have unlimited computational resources to process the valuations once these
are available.

As we will see, solving OptimalSequence exactly using polynomially many
queries is a challenge. So, we are interested in algorithms that compute
approximately optimal solutions. On input an OptimalSequence instance, a
$\rho$-approximate action sequence (for $\rho\geq 1$) is one which has a
social welfare that is at most $\rho$ times smaller than the maximum possible
(or optimal) social welfare over all action sequences. We refer to $\rho$ as
the approximation ratio of an algorithm which always returns
$\rho$-approximate action sequences. We are interested in OptimalSequence
algorithms that make only polynomially many queries and achieve an
approximation ratio that is as low as possible.

##  3 The Query Complexity of Approximate Serial Dictatorships

We devote this section to studying the query complexity of approximation
algorithms for OptimalSequence, presenting both positive and negative results.
It is not hard to see that non-monotone valuations are notoriously hard to
cope with and any finite approximation may require to examine almost all the
$n!$ action sequences.111Indeed, consider instances in which a special agent
$i$ has valuation $v_{i}(S)=1$ if $S$ contains all $n-1$ other agents in a
specific hidden order and all other agent valuations are zero. To compute the
only action sequence with non-zero social welfare, an algorithm needs to
“guess” the hidden order. However, as we will see later in Section 7,
excellent approximations for special cases of non-monotone valuations are
possible.

So, in the rest of this section, we focus on instances with monotone
valuations. On the positive side, we present two algorithms for
OptimalSequence, one deterministic and one randomized, called Det and Rand,
respectively. Both algorithms use an integer parameter $c\geq 1$ and apply to
$n$-agent OptimalSequence instances. We denote by $N_{c}$ the collection
consisting of all sets of $c$ distinct agents from $[n]$. Algorithm Det
considers all $c$-sets in $N_{c}$. For each set $C\in N_{c}$, it considers
every action subsequence $S\in\mathcal{S}_{C}$ and selects the one, call it
$S^{\prime}$, that maximizes the quantity $\sum_{i\in C}{v_{i}(S^{i})}$.
Finally, it returns an action sequence that contains $S^{\prime}$ as a prefix
(by filling the last $n-c$ positions in the action sequence with agents in
$[n]\setminus C$ in arbitrary order).

######  Theorem 1.

On input $n$-agent monotone OptimalSequence instances, algorithm Det makes
${n\choose c}\cdot c\cdot c!$ queries and has an approximation ratio of at
most $\frac{n}{c}$.

###### Proof.

Consider an $n$-agent OptimalSequence instance and notice that the algorithm
enumerates all the ${n\choose c}$ elements of $N_{c}$ and for each such
element $C\in N_{c}$ and each of the $c!$ action subsequences
$S\in\mathcal{S}_{C}$, it makes $c$ queries to compute the value of the sum
$\sum_{i\in C}{v_{i}(S^{i})}$. The bound on the number of queries follows.

Given an $n$-agent OptimalSequence instance, let $\widetilde{\pi}$ be the
optimal action sequence, $\pi$ be the action sequence returned by algorithm
Det, and $S=\pi|_{c}$. Denote by $\widetilde{S}\leq\widetilde{\pi}$ the action
subsequence consisting of those $c$ agents that have the $c$ highest values
$v_{i}(\widetilde{\pi}^{i})$ (breaking ties arbitrarily). Then, by the
definition of Det,

$\displaystyle\sum_{i\in S}{v_{i}(S^{i})}$
$\displaystyle\geq\sum_{i\in\widetilde{S}}{v_{i}(\widetilde{S}^{i})}.$ (1)

Furthermore, by monotonicity, the fact that
$\widetilde{S}^{i}\leq\widetilde{\pi}^{i}$ implies that
$v_{i}(\widetilde{S}^{i})\geq v_{i}(\widetilde{\pi}^{i})$ for every agent $i$
and, thus,

$\displaystyle\sum_{i\in\widetilde{S}}{v_{i}(\widetilde{S}^{i})}$
$\displaystyle\geq\sum_{i\in\widetilde{S}}{v_{i}(\widetilde{\pi}^{i})}.$ (2)

Finally, by the definition of $\widetilde{S}$, we have

$\displaystyle\sum_{i\in\widetilde{S}}{v_{i}(\widetilde{\pi}^{i}})$
$\displaystyle\geq\frac{c}{n}\cdot\sum_{i\in[n]}{v_{i}(\widetilde{\pi}^{i})}.$
(3)

By inequalities (1), (2), (3), and the definition of the social welfare, we
get

$\displaystyle\mathrm{SW}(\pi)$
$\displaystyle=\sum_{i\in[n]}{v_{i}(\pi^{i})}\geq\sum_{i\in
S}{v_{i}(S^{i})}\geq\frac{c}{n}\cdot\sum_{i\in[n]}{v_{i}(\widetilde{\pi}^{i})}=\frac{c}{n}\cdot\mathrm{SW}(\widetilde{\pi}).$

The bound on the approximation ratio follows. ∎

Theorem 1 implies the following using $c=1/\epsilon$ for constant
$\epsilon>0$.

######  Corollary 2.

For every constant $\epsilon>0$, on input $n$-agent monotone OptimalSequence
instances, algorithm Det has an approximation ratio at most $\epsilon\cdot n$
by making $O\left(n^{2/\epsilon}\right)$ queries.

Algorithm Rand is similar to Det; it uses randomization to avoid the
enumeration over all elements of $N_{c}$. First, it selects a $c$-set $C$ from
$N_{c}$ uniformly at random. Then, it considers every action subsequence
$S\in\mathcal{S}_{C}$ and selects the one, call it $S^{\prime}$, that
maximizes the quantity $\sum_{i\in C}{v_{i}(S^{i})}$. Finally, it returns an
action sequence that contains $S^{\prime}$ as a prefix.

######  Theorem 3.

On input $n$-agent monotone OptimalSequence instances, algorithm Rand makes
$c\cdot c!$ queries and has an approximation ratio of at most $\frac{n}{c}$.

###### Proof.

The bound on the number of queries is due to the fact that Rand considers all
the $c!$ action subsequences with the agents in $C$ and computes the sum
$\sum_{i\in C}{v_{i}(S^{i})}$ by making $c$ queries for each of them.

To bound the approximation ratio, consider an $n$-agent OptimalSequence
instance and let $\widetilde{\pi}$ and $\pi$ be the optimal action sequence
and the (random) action sequence returned by Rand, respectively. Also, let
$S_{C}$ be the action subsequence consisting of agents in $C$ so that
$S_{C}\leq\widetilde{\pi}$. Since Rand prefers the prefix $\pi|_{c}$ to
$S_{C}$, we have

$\displaystyle\sum_{i\in C}{v_{i}(\pi^{i})}$ $\displaystyle\geq\sum_{i\in
C}{v_{i}(S_{C}^{i})}\geq\sum_{i\in C}{v_{i}(\widetilde{\pi}^{i})}.$ (4)

The last inequality follows by monotonicity of valuations, which implies that
$v_{i}(S_{C}^{i})\geq v_{i}(\widetilde{\pi}^{i})$ since
$S_{C}^{i}\leq\widetilde{\pi}^{i}$ for every agent $i\in C$. Now, since $C$ is
selected uniformly at random from $N_{c}$, an agent from $[n]$ belongs to $C$
with probability $\frac{c}{n}$. Using linearity of expectation, inequality
(4), and this last observation, we have

$\displaystyle\mathbb{E}\left[\mathrm{SW}(\pi)\right]$
$\displaystyle\geq\mathbb{E}\left[\sum_{i\in
C}{v_{i}(\pi^{i})}\right]\geq\mathbb{E}\left[\sum_{i\in
C}{v_{i}(\widetilde{\pi}^{i})}\right]=\frac{c}{n}\cdot\mathbb{E}\left[\sum_{i\in[n]}{v_{i}(\widetilde{\pi}^{i})}\right]=\frac{c}{n}\cdot\mathbb{E}\left[\mathrm{SW}(\widetilde{\pi})\right].$

This completes the proof. ∎

For $c=\Theta\left(\frac{\ln{n}}{\ln\ln{n}}\right)$, Theorem 3 yields the
following.

######  Corollary 4.

On input $n$-agent monotone OptimalSequence instances, algorithm Rand makes at
most $\textup{poly}(n)$ queries and has an approximation ratio of at most
$O\left(\frac{n\ln\ln{n}}{\ln{n}}\right)$.

In the following, we show that Rand is (asymptotically) optimal.

######  Theorem 5.

For every integer $c\geq 1$, any (possibly randomized) algorithm for monotone
OptimalSequence that makes at most $\frac{c!}{n}-1$ queries when applied on
instances with $n$ agents has an approximation ratio at least $\frac{n}{c+1}$.

###### Proof.

For an integer $c\geq 1$, we will define a probability distribution $Q_{c}$
over $n$-agent instances of OptimalSequence with an optimal social welfare of
$n$, and will prove that the expected social welfare of any deterministic
algorithm that makes at most $\frac{c!}{n}-1$ queries on these instances is at
most $c+1$. Then, by Yao’s principle [Yao77], the quantity $\frac{n}{c+1}$
will be a lower bound on the approximation ratio of randomized algorithms for
OptimalSequence.

We define the family $\mathcal{F}_{c}$ consisting of instances $I_{\pi}$ for
every $\pi\in\mathcal{S}_{[n]}$. Instance $I_{\pi}$ is defined by the
following valuation functions. For any agent $i\in[n]$ and any action
subsequence $S$ from $\mathcal{S}_{-i}$:

$v_{i}(S)=\left\\{\begin{array}[]{ll}1&\mbox{if }|S|<c\ \ \text{or}\ \
S\leq\pi\\\ 0&\mbox{otherwise }\end{array}\right.$

Hence, the valuation functions are binary. An agent gets a value of $1$ only
in the following two cases: (a) when she has fewer than $c$ agents ahead of
her, or (b) when the agents ranked ahead of her have the same relative
ordering as in the action sequence $\pi$. In all other cases, her value is
$0$. Notice that the action sequence $\pi$ has optimal social welfare of $n$
for instance $I_{\pi}$.

Let us prove that the instances in $\mathcal{F}_{c}$ are indeed valid ones,
i.e., the valuations defined are monotone. Fix any agent $i\in[n]$ and any
action subsequence $S\in\mathcal{S}_{-i}$. To prove monotonicity, we need to
show that $v_{i}(S^{\prime})\geq v_{i}(S)$ for any action subsequence
$S^{\prime}\leq S$. This follows trivially when $|S|<c$ or when $v_{i}(S)=0$.
Therefore, let us assume that $|S|\geq c$ and $v_{i}(S)=1$. This implies that
$S$ is an action subsequence of $\pi$, i.e., $S\leq\pi$. By transitivity, we
have $S^{\prime}\leq\pi$ as well, and the definition of $v_{i}$ yields
$v_{i}(S^{\prime})=1$, thereby proving that $v_{i}$ is monotone.

For integer $c\geq 1$, the probability distribution $Q_{c}$ simply selects a
magic action sequence $\widehat{\pi}$ and produces the instance
$I_{\widehat{\pi}}$. Consider a deterministic algorithm $\mathcal{A}$ that
makes at most $k=\frac{c!}{n}-1$ queries; we will show that the expected
social welfare of its output on the (random) instances produced by
distribution $Q_{c}$ is at most $c+1$. Assume that, on input the instance
$I_{\widehat{\pi}}$, algorithm $\mathcal{A}$ makes $k$ queries of the form
$(i,S)$ and eventually returns the action sequence
$\overline{\pi}\in\mathcal{S}_{[n]}$. We say that an action (sub)sequence $S$
hits the magic action sequence $\widehat{\pi}$ when $|S|\geq c$ and
$S|_{c}\leq\widehat{\pi}$. We define the enhanced version of $\mathcal{A}$,
denoted by $\mathcal{A}_{\widehat{\pi}}$, that works as follows when applied
on instance $I_{\widehat{\pi}}$. Algorithm $\mathcal{A}_{\widehat{\pi}}$
simulates algorithm $\mathcal{A}$, performing the following additional steps.
Whenever $\mathcal{A}$ makes a query $(i,S)$ so that $S$ hits the magic action
sequence $\widehat{\pi}$, $\mathcal{A}_{\widehat{\pi}}$ returns
$\widehat{\pi}$ and terminates. Also, if the action sequence $\overline{\pi}$
returned by $\mathcal{A}$ hits $\widehat{\pi}$, algorithm
$\mathcal{A}_{\widehat{\pi}}$ returns $\widehat{\pi}$ instead. Otherwise, it
returns $\overline{\pi}$.

Observe that, the social welfare of algorithm $\mathcal{A}$ when applied on
the instance $I_{\widehat{\pi}}$ is never higher than the social welfare of
the enhanced algorithm $\mathcal{A}_{\widehat{\pi}}$. This is due to the fact
that $\mathcal{A}_{\widehat{\pi}}$ returns a suboptimal action sequence (i.e.,
one that is different than $\widehat{\pi}$) only when this sequence is
returned by $\mathcal{A}$. Hence, it suffices to bound the social welfare of
algorithm $\mathcal{A}_{\widehat{\pi}}$ when applied on instance
$I_{\widehat{\pi}}$.

For an action (sub)sequence $S$, observe that $\mathcal{S}_{[n]}$ contains
$\frac{n!}{c!}$ action sequences $\pi^{\prime}$ such that
$S|_{c}\leq\pi^{\prime}$. Since $\widehat{\pi}$ is selected uniformly at
random among the $n!$ action sequences of $\mathcal{S}_{[n]}$, the probability
that $S$ hits $\widehat{\pi}$ is $\frac{1}{c!}$. By applying the union bound,
we obtain that the probability that either some of the $k$ action subsequences
that algorithm $\mathcal{A}$ uses in its $k$ queries or the action sequence
$\overline{\pi}$ it outputs hit the magic action sequence $\widehat{\pi}$ is
at most $\frac{k+1}{c!}$. We conclude that the enhanced algorithm
$\mathcal{A}_{\widehat{\pi}}$ returns $\widehat{\pi}$ with probability at most
$\frac{k+1}{c!}$ and gets social welfare $n$. Notice that if this is not the
case, the social welfare of the action sequence returned is exactly $c$. Then,
the expected welfare of algorithm $\mathcal{A}$ is

$\displaystyle\mathbb{E}_{I\sim Q_{c}}[\mathrm{SW}(\mathcal{A(I)})]$
$\displaystyle\leq\mathbb{E}_{\widehat{\pi}\sim
Q_{c}}[\mathrm{SW}(\mathcal{A}_{\widehat{\pi}}(I_{\widehat{\pi}}))]\leq
c+(n-c)\cdot\frac{k+1}{c!}\leq c+1,$

as desired. The last inequality follows by the definition of $k$. ∎

By applying Theorem 5 with $c=\Theta\left(\frac{\ln{n}}{\ln\ln{n}}\right)$, we
obtain that Rand is essentially best possible.

######  Corollary 6.

Any (possibly randomized) algorithm for monotone OptimalSequence that makes
$\textup{poly}(n)$ queries has approximation ratio
$\Omega\left(\frac{n\ln\ln{n}}{\ln{n}}\right)$.

##  4 Specific Valuation Structures

We now explore specific instances of OptimalSequence, in which valuations have
a combinatorial structure. In particular, the definition of valuations assumes
that each agent $i$ has a set $X_{i}$ from which she can select her actions. A
collection of actions is just a set of agent-action pairs $(i,a)$, each
consisting of an agent $i$ and an action $a\in X_{i}$. An agent $i$ may appear
in at most one agent-action pair of a collection. A collection of actions that
includes all agents is called full. A constraint $F$ defines which collections
of actions are feasible. $F$ is called downward closed if every subset of a
feasible collection of actions is feasible as well.

An action (sub)sequence $S$ produces a collection of actions $A$ as follows.
Initially, $A$ is empty. When it is the turn of agent $i$ to act, she selects
an action $\widehat{a}$ from $X_{i}$ which is best possible among all actions
$a$ in $X_{i}$ such that $A\cup\\{(i,a)\\}$ is feasible. The agent-action pair
$(i,\widehat{a})$ is then included in the collection of actions $A$. To decide
which action is best possible, agent $i$ uses a strict ranking of the actions
in $X_{i}$ (possibly dependent on other agent-action pairs in $A$ when this
decision is made) and corresponding valuations for them that are consistent to
it. We call the ranking of an agent and the corresponding valuations for their
action endogenous when it is independent of actions by other agents. For an
agent $i$ who acts after a collection of actions by other agents, we denote
her best possible action as $\textsc{BR}(i,A)$.

We consider three different feasibility constraints, which define three
different classes of valuations and corresponding restricted classes of
OptimalSequence instances; others can be defined analogously. Essentially,
with each class, we restrict our attention to OptimalSequence instances that
may appear in practical applications and which are hopefully easier to solve
than the very general ones. The three valuation structures we consider are
described in the next three subsections.

###  4.1 Matchings in bipartite graphs

The valuations are defined using a complete bipartite graph $G=K_{n,n}$,
equipped with a function $w:[n]^{2}\rightarrow\mathbb{R}_{\geq 0}$, that
assigns non-negative weights to its edges. The nodes in the left part of the
bipartition correspond to the $n$ agents. The nodes in the right part
correspond to items, which are to be given to the agents, under the
restriction that each agent can get (at most) one item and each item will be
given to (at most) one agent. Such an assignment of items to agents is
represented by a matching in $G$. The weight $w(i,j)$ denotes the value agent
$i$ has for item $j$. Agents pick their items according to an action sequence.
When it is the turn of an agent to act, she picks the item of highest value
among those that have not been picked by agents who acted before her.

Formally, each agent $i$ has a strict ranking $r_{i}$ that ranks the items in
monotone non-increasing order with respect to the value of agent $i$ for them,
breaking ties in a predefined (agent-specific) manner. We denote by $r_{i}(j)$
the rank of item $j$ for agent $i$. The items of rank $1$ and $n$ for agent
$i$ are ones for which she has highest and lowest values, respectively. Also,
$r_{i}(j)<r_{i}(j^{\prime})$ implies that $w(i,j)\geq w(i,j^{\prime})$. For an
action subsequence $S\in\mathcal{S}_{-i}$, denote by $\mu_{i}(S)$ the item
agent $i$ gets when she acts immediately after the agents in $S$. By
overloading notation, we use $\mu(S)$ to denote the set of items picked by the
agents who acted before agent $i$, i.e., $\mu(S)=\cup_{k\in
S}{\mu_{k}(S^{k})}$. Clearly, $\mu(\emptyset)=\emptyset$. Then, the action of
agent $i$ when acting after the action subsequence $S\in\mathcal{S}_{-i}$ is
to pick item
$\mu_{i}(S)=\operatorname*{arg\,min}_{j\in[n]\setminus\mu(S)}{r_{i}(j)}$,
which gives her value $v_{i}(S)=w(i,\mu_{i}(S))$. Notice that, when all agents
have acted, the items picked form a perfect matching in $G$.

We denote by OSM the special cases of OptimalSequence when applied on
instances with the specific valuation structure as defined above. To make a
connection with the general combinatorial structure described above, each
agent $i$ has the set of all items as its set of available actions $X_{i}$.
The feasibility constraint $F$ requires that the collection of actions form a
matching in $G$. Clearly, $F$ is downward closed. All agents have endogenous
rankings/valuations.

######  Lemma 7.

OSM valuations are monotone.

###### Proof.

We will prove the claim by showing the following property: for every agent
$i\in[n]$ and action subsequences $S,\widehat{S}\in\mathcal{S}_{-i}$ with
$\widehat{S}\leq S$, it holds $\mu(\widehat{S})\subseteq\mu(S)$. This implies
that $r_{i}(\mu_{i}(\widehat{S}))\leq r_{i}(\mu_{i}(S))$ and, consequently,
$v_{i}(\widehat{S})\geq v_{i}(S)$.

To complete the proof, assume that the property is not true. Then, there
exists an agent $k$ who gets in $\widehat{S}$ an item that does not belong to
set $\mu(S^{k})$ and is different than item $\mu_{k}(S^{k})$. Assume,
furthermore, that among the agents satisfying these conditions, $k$ is the
agent that acts earliest in $\widehat{S}$. This would mean that the two items
$\mu_{k}(\widehat{S}^{k})$ and $\mu_{k}(S^{k})$ are both available to agent
$k$ when his turn in $\widehat{S}$ and $S$ comes. Picking a different item in
$\widehat{S}$ and $S$ violates our definition of agent actions. ∎

###  4.2 Arborescences in directed graphs

The valuations are defined using an $n$-node complete directed graph
$G=([n],E)$ with a weight function $w:E\rightarrow\mathbb{R}_{\geq 0}$ on its
edges. The nodes correspond to the agents. The weight $w(i,j)$ denotes the
value of agent $i$ for the edge $(i,j)$ (i.e., the directed edge from node $i$
to node $j$). Each agent has as objective to connect to another node through a
directed edge of maximum value so that this edge forms a directed forest with
edges drawn before.

Formally, each agent $i$ has a strict ranking $r_{i}$ that ranks the outgoing
edges from node $i$ in monotone non-increasing order with respect to the value
of agent $i$ for them, breaking ties in a predefined manner. We denote by
$r_{i}(j)$ the rank of edge $(i,j)$ for agent $i$. The edges of rank $1$ and
$n-1$ for agent $i$ are ones for which agent $i$ has highest and lowest
values, respectively. Also, $r_{i}(j)<r_{i}(j^{\prime})$ implies that
$w(i,j)\geq w(i,j^{\prime})$. For an action subsequence
$S\in\mathcal{S}_{-i}$, denote by $G_{S}$ the subgraph of $G$ consisting of
the edges drawn during the actions of the agents in $S$. Clearly,
$G_{\emptyset}$ consists of the $n$ nodes of $G$ and no edges. For an agent
$i$ and action subsequence $S\in\mathcal{S}_{-i}$, we say an edge $(i,j)$ is
forbidden if it forms a cycle when put together with the graph $G_{S}$. The
action of agent $i$ when acting after the action sequence
$S\in\mathcal{S}_{-i}$ is to draw an edge to node $\tau_{i}(S)$ defined as the
node $j$ minimizing $r_{i}(j)$ under the constraint that edge $(i,j)$ is not
forbidden. The agent draws no edge if all edges are forbidden and gets a value
of $v_{i}(S)=0$. Notice that this will happen only for an agent who acts after
all other agents. Otherwise, the value of agent $i$ is
$v_{i}(S)=w(i,\tau_{i}(S))$. Notice that, when all agents have acted, the
edges drawn form an arborescence in $G$, i.e., a tree whose edges are directed
towards the root, which has out-degree $0$.

According to the terminology of the general combinatorial structure, each
agent $i$ has the set of all edges outgoing from node $i$ as its set of
available actions $X_{i}$. The feasibility constraint $F$ requires that the
collection of actions form a directed forest in $G$; this is clearly downward
closed. Again, all agents have endogenous rankings/valuations. We use the term
OSA to refer to these instances of OptimalSequence.

######  Lemma 8.

OSA valuations are monotone.

###### Proof.

Consider agent $i\in[n]$ and two action subsequences
$S,\widehat{S}\in\mathcal{S}_{-i}$ such that $\widehat{S}\leq S$. We will show
the following property: the edge agent $i$ draws when she acts after the
action subsequence $S$ is not forbidden when she acts after the action
subsequence $\widehat{S}$. Hence, we get $v_{i}(\widehat{S})\leq v_{i}(S)$, as
desired.

For the sake of contradiction, assume that the property is not true. Then,
there should exist action subsequences $S$ and $\widehat{S}$ with
$\widehat{S}\leq S$ and an agent $k$ in $\widehat{S}$, for which the edge
$(k,j)$ she picks in $S$ is forbidden when her turn to act comes in
$\widehat{S}$. Among all agents who may satisfy this condition, we
specifically select $k$ to be the one who acts earliest in $\widehat{S}$. As
edge $(k,j)$ is forbidden for agent $k$ in $\widehat{S}$, let $C$ be the cycle
it forms together with $G_{\widehat{S}}$. Let $j_{1}$ be the node/agent that
is furthest from $k$ in $C$ among those drawing different edges in $S$ and
$\widehat{S}$. Let $(j_{1},j_{2})$ and $(j_{1},j_{3})$ be the edges agent
$j_{1}$ draws in $\widehat{S}$ and $S$, respectively.

We now claim that when it is the turn of agent $j_{1}$ to act in $S$, the edge
$(j_{1},j_{2})$ is not forbidden. The reason is that the only nodes to which
node $j_{1}$ can be connected via edges that were drawn in $S$ before agent
$j_{1}$ acts, are those in the path from $j_{2}$ to $k$ in $C$. As agent $k$
has not acted before agent $j_{1}$, no cycle can be formed if agent $j_{1}$
draws edge $(j_{1},j_{2})$. Hence, $r_{j_{1}}(j_{2})>r_{j_{1}}(j_{3})$. But
then, agent $j_{1}$ who acts before agent $k$ in $\widehat{S}$ and draws edge
$(j_{1},j_{2})$ must have the edge $(j_{1},j_{3})$ she drew in $S$ as
forbidden. This contradicts our assumption on the timing of agent $k$. ∎

###  4.3 Satisfiability of clauses

The valuations are defined using $n$ Boolean variables $x_{1}$, $x_{2}$, …,
$x_{n}$, a set $\mathcal{C}$ of $m$ clauses $C_{1}$, $C_{2}$, …, $C_{m}$, and
a function $w:\mathcal{C}\rightarrow\mathbb{R}_{\geq 0}$ that assigns a non-
negative weight to each clause. Agent $i\in[n]$ controls the variable $x_{i}$.
Informally, when acting according to an action sequence, an agent sets the
value of her variable to either True or False, so that the additional weight
in the newly satisfied clauses is maximized. The value of an agent is then
simply this additional weight of clauses that became satisfied due to her
action.

Formally, for agent $i\in[n]$ and a set of clauses $M$, we denote by $P(i,M)$
(respectively, $N(i,M)$) the total weight of the clauses in $M$ which contain
the positive literal $x_{i}$ (respectively, the negative literal
$\overline{x_{i}}$). For an action subsequence $S$, we denote by $C_{S}$ the
set of clauses that are not satisfied by the actions of the agents in $S$.
Clearly, $C_{\emptyset}=\mathcal{C}$. The action of agent $i$ when acting
after the agents in the action subsequence $S\in\mathcal{S}_{-i}$ is to set
her variable $x_{i}$ to True if $P(i,C_{S})>N(i,C_{S})$ and to False if
$P(i,C_{S})<N(i,C_{S})$. Ties, i.e., when $P(i,C_{S})=N(i,C_{S})$, are
resolved by setting $x_{i}$ to a predefined value (True or False). Then, the
valuation $v_{i}(S)$ is simply $P(i,C_{S})$ or $N(i,C_{S})$, whichever is
higher, i.e., $v_{i}(S)=\max\\{P(i,C_{S}),N(i,C_{S})\\}$.

According to the terminology above, each agent $i$ has True and False as her
two available actions in $X_{i}$ and there is no feasibility constraint. In
contrast to the two classes above, the agent rankings/values of the two
actions are non-endogenous. We denote by OSS the special cases of
OptimalSequence when applied on satisfiability instances.

######  Lemma 9.

OSS valuations are not monotone.

###### Proof.

Consider the instance with three agents and the following clauses: $x_{1}\vee
x_{2}$ of weight $6$, $\overline{x_{1}}\vee x_{2}\vee x_{3}$ of weight $2$,
$\overline{x_{1}}\vee\overline{x_{2}}\vee x_{3}$ of weight $1$, and
$\overline{x_{1}}\vee\overline{x_{2}}$ of weight $2$. Consider the action
subsequence $12$. Agent $1$ sets $x_{1}=1$ and then agent $2$ sets $x_{2}=0$,
leaving $\overline{x_{1}}\vee x_{2}\vee x_{3}$ as the only unsatisfied clause.
Hence, agent $3$ sets $x_{3}=1$ and gets a value of $v_{3}(12)=2$. Now,
consider the action subsequence that consists only of agent $2$. Agent $2$ set
$x_{2}=1$ and, then, the only clause that is unsatisfied and contains variable
$x_{3}$ is $\overline{x_{1}}\vee\overline{x_{2}}\vee x_{3}$. We get
$v_{3}(2)=1$, which violates monotonicity of $v_{3}$. ∎

###  4.4 Three key questions

We devote the last part of this section for introducing the three key
questions that we consider, using the term OSF as a proxy for a valuation
structure defined by a feasibility constraint $F$.

With specific valuation structures, we hope to be able to achieve considerably
better approximations with polynomially many queries, compared to the upper
bounds for general OptimalSequence instances in Theorem 3. We remark that,
like in our algorithms in Section 3, the only tool that is available to
algorithms for these problems is query access to the valuations. However,
knowledge of the fact that the valuations have a specific underlying structure
may prove useful.

> Question 1: How well can algorithms that use polynomially many queries
> approximate OSF?

We remark here that the computational complexity of the underlying
optimization problem does not have any implications for the query complexity
of (approximating) the corresponding OptimalSequence instance. We demonstrate
this with a tailored class of instances (defining the special case OSI of
OptimalSequence) that use independent sets to define the valuations. Does the
fact that the maximum independent set problem is NP-hard (even to approximate)
imply any lower bound on the query complexity of OSI? We will see that the
answer is negative.

An OSI instance is defined with an $n$-node undirected graph $G$. Each node
corresponds to an agent. For an agent $i\in[n]$, the value $v_{i}(S)$ for an
action subsequence $S\in\mathcal{S}_{-i}$ is $1$ if the nodes in
$S\cup\\{i\\}$ form an independent set and $0$ otherwise. It is not difficult
to see that these valuations are monotone. Furthermore, the social welfare
$\mathrm{SW}(\pi)$ of an action sequence $\pi$ is equal to the length of the
maximal prefix of $\pi$ consisting of agents whose corresponding nodes form an
independent set in $G$. Hence, the optimal social welfare among all action
sequences is equal to the size of the maximum independent set. Now, notice
that a simple algorithm that uses only $O(n^{2})$ queries can learn the
underlying graph $G$, compute a maximum independent set in it, and,
consequently, an action sequence with maximum social welfare. It just suffices
to query the value $v_{i}(j)$ for every pair of agents $i$ and $j$. Then, the
edge $(i,j)$ exists in $G$ if $v_{i}(j)=0$ and does not exist if $v_{i}(j)=1$.

Next, we would like to understand how rich the space of action sequences is
with respect to all feasible solutions to the underlying combinatorial
problem.

> Question 2: What is the computational complexity of the following problem?
> Given a collection of actions that satisfies the feasibility constraint $F$,
> decide whether it can be produced by an action sequence.

An action sequence can be viewed as a greedy algorithm for computing a
solution to the combinatorial optimization problem MaxF, whose objective is to
compute a feasible collection of actions of maximum total value for the
agents. An important question about the quality of action sequences is then:

> Question 3: How well can the best action sequence approximate the optimal
> solution to the underlying MaxF combinatorial optimization problem?

We introduce the concept of the price of serial dictatorship (PoSD) of MaxF to
quantify the answer to Question 3. The price of serial dictatorship of an
instance of MaxF is the ratio of the maximum total value for the agents among
all the feasible collections of actions over the social welfare of the best
action sequence. Then, the price of serial dictatorship of MaxF is the worst-
case PoSD over all MaxF instances. Note that PoSD is a number higher or equal
to $1$.

##  5 Matchings in Bipartite Graphs

We now present answers to these three key questions for OSM. An answer to
Question 1 can be obtained using Algorithm 1, which is presented in the
following.

Input: Query access to an $n$-agent OSM instance

Output: An action sequence $\pi$

1: Initialize $\pi\leftarrow\emptyset$; $R\leftarrow[n]$;

2: for $k\leftarrow 1$ to $n$ do

3: Let $i^{*}\leftarrow\operatorname*{arg\,max}_{i\in R}{v_{i}(\pi)}$;

4: Update $\pi(k)\leftarrow i^{*}$; $R\leftarrow R\setminus\\{i^{*}\\}$;

5: end for

6: return $\pi$;

ALGORITHM 1 A $2$-approximation algorithm for OSM

Algorithm 1 builds the action sequence $\pi$ gradually in steps. In the $k$-th
step, it selects the agent $i^{*}$ (among those in the set variable $R$, which
contains the agents not included in $\pi$ yet) who attains maximum value if
she acts immediately after the action subsequence built so far. Notice that
$\pi$ is an empty action subsequence initially and is augmented in each
execution of the for loop of Algorithm 1.

######  Theorem 10.

On input $n$-agent OSM instances, Algorithm 1 uses $O(n^{2})$ queries and
computes a $2$-approximate solution.

###### Proof.

The bound on the number of queries is obvious: the algorithm makes $n$
executions of the for loop and, in each of them, it makes a query $(i,\pi)$
for each of the at most $n$ agents in set $R$.

Let $\widehat{\pi}$ be an optimal action sequence for a given OSM instance
consisting of a complete bipartite graph $G=K_{n,n}$, edge-weight function
$w:[n]^{2}\rightarrow\mathbb{R}_{\geq 0}$, and rank information
$\\{r_{i}\\}_{i\in[n]}$ and $\pi$ the action sequence returned by Algorithm 1.
Let $M$ and $\widehat{M}$ be the sets of edges defined by the items picked in
action sequences $\pi$ and $\widehat{\pi}$. Let $e_{i}$ be the edge that is
incident to node $i$ in $\widehat{M}$. Let $C$ be the set of agents who pick a
different item in $\pi$ and $\widehat{\pi}$. For each agent $i\in C$, denote
by $e_{i}^{+}$ and $e_{i}^{-}$ the two edges of $M$ which are incident to edge
$e_{i}$. Notice that the definition of Algorithm 1 implies that, for any $i\in
C$, the agent who picks the first among edges $e_{i}^{+}$ and $e_{i}^{-}$ gets
a value that is at least as high as the weight of edge $e_{i}$ (since $e_{i}$
was available at that point and agent $i$ had not picked any item yet). Hence,
$w(e_{i})\leq w(e_{i}^{+})+w(e_{i}^{-})$ and

$\displaystyle\mathrm{SW}(\widehat{\pi})$
$\displaystyle=\sum_{i\in[n]}{w(e_{i})}=\sum_{i\in
C}{w(e_{i})}+\sum_{i\in[n]\setminus C}{w(e_{i})}\leq\sum_{i\in
C}{(w(e_{i}^{+})+w(e_{i}^{-}))}+\sum_{i\in[n]\setminus C}{w(e_{i})}$
$\displaystyle=2\cdot\sum_{i\in C}{w(i,\mu_{i}(\pi^{i}))}+\sum_{[n]\setminus
C}{w(i,\mu_{i}(\pi^{i}))}\leq 2\cdot\mathrm{SW}(\pi),$

as desired. ∎

Despite the simplicity of Algorithm 1, improvements seem to be technically
challenging:

> Open Question 1: Are there algorithms that solve OSM optimally using
> polynomially many queries?

We suspect that the answer to Open Question 1 is positive, at least for the
special case of OSM where each agent has different valuations for the items.
Unfortunately, our attempts to design an algorithm that learns the underlying
valuations in polynomial time have not been successful so far. In our answer
to Question 2, we will first use our more general terminology as we intend to
provide an answer for a large class of valuation structures; our answer to
Question 2 for OSM will follow as a corollary.

######  Theorem 11.

Consider an OSF instance defined by a downward closed feasibility constraint
$F$ and endogenous valuations, and let $A=\\{(i,a_{i})\\}_{i\in[n]}$ be a full
feasible collection of actions. Deciding whether there exists an action
sequence $\pi$ that produces $A$ can be done in polynomial time.

We prove Theorem 11 using Algorithm 2, which constructs the action sequence
$\pi$ in a greedy way. It uses the set variable $P$ to keep the agents whose
actions have not been checked yet; the set variable $M$ keeps the agent-action
pairs with agents in $P$. The action sequence is stored in variable $\pi$,
which is returned at the end. In case no action sequence can be computed, the
algorithms returns a Fail report.

Input: A feasibility constraint $F$, a feasible full collection of actions
$\\{i,a_{i}\\}_{i\in[n]}$, rank information $\\{r_{i}\\}_{i\in[n]}$

Output: An action sequence that produces $\\{i,a_{i}\\}_{i\in[n]}$ or Fail
report

1: Initialize $\pi\leftarrow\emptyset$; $P\leftarrow[n]$;
$M\leftarrow\emptyset$; $k\leftarrow 1$;

2: while $P\not=\emptyset$ do

3: $\text{Top}\leftarrow\\{i\in P:a_{i}=\textsc{BR}(i,M)\\}$;

4: if $\text{Top}\not=\emptyset$ then

5: Let $i^{*}\in\text{Top}$;

6: $\pi(k)\leftarrow i^{*}$; $P\leftarrow P\setminus\\{i^{*}\\}$; $M\leftarrow
M\cup\\{(i^{*},a_{i^{*}})\\}$; $k\leftarrow k+1$;

7: else

8: return Fail;

9: end if

10: end while

11: return $\pi$;

ALGORITHM 2 Deciding whether a full collection of actions can be produced by
an action sequence

###### Proof.

Clearly, the algorithm runs in polynomial time assuming we have polynomial-
time access to $\textsc{BR}(i,M)$. To prove its correctness, first notice that
it indeed outputs an action sequence that produces the collection of actions
$A$ if it never fails. Now, assume that $A$ can be produced by an action
sequence $\widehat{\pi}$; we will show that the algorithm never fails. Indeed,
at the beginning of any execution of the while loop, let $i$ be the agent in
set $P$ that acts earliest in $\widehat{\pi}$. Denote by $\widehat{M}$ the
collection of actions decided by the action subsequence $\widehat{\pi}^{i}$
(while $M$ is the collection of actions that have been checked prior to the
current while loop execution. Since $M\cup\\{(i,a_{i})\\}\subseteq A$,
downward closedness of $F$ implies that $M\cup\\{(i,a_{i})\\}$ is feasible.
Furthermore, since $\widehat{M}\cup\\{(i,x)\\}\subseteq M\cup\\{(i,x)\\}$ for
any $x\in X_{i}$, we conclude that any action that is available to agent $i$
in $\pi^{i}$ was also available in $\widehat{\pi}^{i}$. Endogeneity of
valuations then implies that $a_{i}=\textsc{BR}(i,M)$. ∎

For OSM, Theorem 11 implies the following corollary.

######  Corollary 12.

Given an instance of OSM and a perfect matching $\mu$ in the underlying
bipartite graph $G$, deciding whether there exists an action sequence $\pi$
that produces $\mu$ can be done in polynomial time.

We now use Algorithm 2 together with Corollary 12 to rediscover a
characterization of Abdulkadiroğlu and Sönmez [AS98] (see also [ACMM05]) about
matchings that can be computed by serial dictatorships. To do so, we need to
adapt Pareto-optimality to our case.

######  Definition 13.

Given a complete bipartite graph $G=K_{n,n}$ and rank information
$\\{r_{i}\\}_{i\in[n]}$ representing strict preferences of agent $i\in[n]$ for
$n$ items, a perfect matching $\mu$ is Pareto-optimal if there is no other
perfect matching $\mu^{\prime}$ such that $r_{i}(\mu^{\prime}_{i})\leq
r_{i}(\mu_{i})$ for all $i\in[n]$ and
$r_{i}(\mu^{\prime}_{i^{*}})<r_{i}(\mu_{i^{*}})$ for some agent $i^{*}\in[n]$.

######  Theorem 14 (Abdulkadiroğlu and Sönmez [AS98]).

Given an instance of OSM consisting of a complete bipartite graph $G=K_{n,n}$
and rank information $\\{r_{i}\\}_{i\in[n]}$, a perfect matching can be
produced by an action sequence if and only if it is Pareto-optimal.

###### Proof.

We prove that a perfect matching $\mu$ can be accepted by Algorithm 2 (by
selecting $i^{*}$ from Top appropriately) if and only if $\mu$ is Pareto-
optimal. Recall that, now, Algorithm 2 takes $(i,\mu_{i})_{i\in[n]}$ as input.

Assume that Algorithm 2 fails for some matching $\mu$. This means that Top is
empty after the execution of line 3 in some iteration of the while loop.
Hence, for every agent $i$ in set $P$, $\mu_{i}\not=\nu_{i}=\textsc{BR}(i,M)$.
Consider the subgraph consisting of the nodes corresponding to the agents in
$P$ and the items they get in $\mu$ and the edges $(i,\mu_{i})$ and
$(i,\nu_{i})$ for $i\in P$. As this subgraph has $2|P|$ nodes and edges, it
has a cycle $C$, which for every edge $(i,\mu_{i})$ it contains, it also has
edge $(i,\nu_{i})$. Now, we define the matching $\mu^{\prime}$ as follows. We
set $\mu^{\prime}_{i}=\nu_{i}$ if node $i$ belongs to the cycle $C$ and
$\mu^{\prime}_{i}=\mu_{i}$ otherwise. By the definition of $\nu_{i}$, every
agent $i$ of $C$ satisfies $r_{i}(\mu^{\prime}_{i})<r_{i}(\mu_{i})$ while
$r_{i}(\mu^{\prime}_{i})=r_{i}(\mu_{i})$ for any agent $i\in[n]\setminus C$.
Hence, $\mu^{\prime}$ Pareto-dominates $\mu$, proving that $\mu$ is not
Pareto-optimal.

Now, consider a matching $\mu$ that is not Pareto-optimal; we will show that
the algorithm will fail. Let $\mu^{\prime}$ be a matching that Pareto-
dominates $\mu$. Let $P_{C}$ be the set of agents who get a different item in
$\mu$ and $\mu^{\prime}$. Also, denote by $R_{C}$ the set of items the agents
of $P_{C}$ get in $\mu$ and $\mu^{\prime}$. Consider an execution of the while
loop in a step with $P_{C}\subseteq P$ (so, no action of the agents in $P_{C}$
has been checked yet). Then, for every agent $i\in P_{C}$, it holds
$r_{i}(\mu^{\prime}_{i})<r_{i}(\mu_{i})$ and, furthermore, as an item of
$R_{C}$, item $\mu^{\prime}_{i}$ is not among the actions that have been
checked so far. Hence, $\textsc{BR}(i,M)\not=\mu_{i}$. This means that no
agent of $P_{C}$ can ever be included in set Top and the algorithm will fail
before set $P$ becomes empty. ∎

To answer Question 3, it suffices to use Theorem 14 and observe that there is
always a maximum-weight perfect matching that is Pareto-optimal. In this way,
we obtain the following corollary.

######  Corollary 15.

The price of serial dictatorship of maximum weight perfect matching in
bipartite graphs is $1$.

##  6 Arborescences in Directed Graphs

We devote this section to OSA; we answer Question 1 using Algorithm 3.

Input: Query access to an $n$-agent OSA instance

Output: An action sequence $\pi$

1: Initialize $\pi\leftarrow\emptyset$; $B\leftarrow\emptyset$;

2: for $i=1$ to $n$ do

3: if $v_{i}(\pi)=v_{i}(\emptyset)$ then

4: Update $\pi\leftarrow\pi||i$;

5: else

6: $C\leftarrow\\{i\\}\cup\\{j\in\pi:v_{i}(\pi\setminus
j)=v_{i}(\emptyset)\\}$;

7: $\ell\leftarrow\operatorname*{arg\,min}_{t\in C}v_{t}(\emptyset)$;

8: Update $\pi\leftarrow(\pi||i)\setminus\ell$; $B\leftarrow B||j$;

9: end if

10: end for

11: Update $\pi\leftarrow\pi||B$;

12: return $\pi$;

ALGORITHM 3 A $2$-approximation algorithm for OSA

Algorithm 3 builds the action sequence $\pi$ gradually. It aims to put at the
beginning of $\pi$ agents who get their maximum value (i.e., equal to
$v_{i}(\emptyset)$) by their action. The actions of these agents form a
directed forest in the underlying directed graph. To do so, the algorithm
considers the agents one by one (in the for loop) and, when an agent does not
get her maximum value (lines 6-8) because the corresponding edge would form a
cycle in the current forest, it detects this cycle (through the queries to
$v_{i}(\pi\setminus j)$ and $v_{i}(\emptyset)$ in line 6) and removes the
agent of lowest value (i.e., the one who has drawn the edge of lowest weight)
in it from $\pi$ (in lines 7 and 8). Agents who are removed during this
process are put in a reserve action subsequence $B$ (line 8). When all agents
have been considered, the final action sequence consists of $\pi$ followed by
$B$ (line 11).

######  Theorem 16.

On input $n$-agent OSA instances, Algorithm 1 uses $O(n^{2})$ queries and
computes a $2$-approximate solution.

###### Proof.

The bound on the running time follows since there are $n$ executions of the
for loop and each execution requires at most $O(n)$ queries. In particular, at
most $n$ queries are enough to compute $C$ in line 6 and, similarly, at most
$n$ queries are enough to compute $\ell$ in line 7.

To prove the bound on the approximation ratio, we will account for the
contribution to the social welfare by the agents in action subsequence $\pi$
that is computed by the for loop (before the update at line 11). By the
definition of the algorithm and due to monotonicity, each of these agents $i$
contributes $v_{i}(\emptyset)$. We use the term top edge to refer to the edge
these agents draw.

Let $N$ be the set of agents that are put to the action subsequence $B$ and
let $P$ the all other agents. For an agent $\ell\in N$, let $i$ be the agent
considered in the for loop when $\ell$ was removed from $\pi$. This removal
happened because the top edges of the agents already in $\pi$ form a cycle $C$
together with the top edge of agent $i$, which has minimum weight among all
edges in $C$.

Let $f(\ell)$ be an arbitrary agent different than $\ell$ in $C$. By the
definition of Algorithm 3, it holds that $v_{\ell}(\emptyset)\leq
v_{f(\ell)}{\emptyset}$. Furthermore, observe that $f(\ell)$ cannot appear in
any cycle formed in later executions. This is due to the fact that the only
nodes that can be reached from $f(\ell)$ through edges already drawn or edges
that will be drawn in later executions are those in the path from $f(\ell)$ to
$\ell$ (whose drawn edge was just removed). Hence, $f(\ell)\in P$ and,
furthermore, $f(\ell)$ is a one-to-one function from $N$ to $P$. Thus,

$\displaystyle\sum_{i\in P}{v_{i}(\emptyset)}$ $\displaystyle\geq\sum_{\ell\in
N}{v_{f(\ell)}(\emptyset)}\geq\sum_{i\in N}{v_{i}(\emptyset)}$

and

$\displaystyle\mathrm{SW}(\pi)$ $\displaystyle\geq\sum_{i\in
P}{v_{i}(\pi^{i})}=\sum_{i\in
P}{v_{i}(\emptyset)}\geq\frac{1}{2}\sum_{i\in[n]}{v_{i}(\emptyset)}\geq\frac{1}{2}\cdot\mathrm{SW}(\widehat{\pi}),$

where $\widehat{\pi}$ denotes the optimal action sequence. ∎

Like OSM, the answer to Question 2 for OSA follows by Theorem 11; recall that
the feasibility constraint of a directed forest is downward closed and
valuations are endogenous.

######  Corollary 17.

Given an instance of OSA and an arborescence $\tau$ in the underlying directed
graph $G$, deciding whether there exists an action sequence $\pi$ that
produces $\tau$ can be done in polynomial time.

We now characterize the arborescences that can be produced by action sequences
using, again, the notion of Pareto-optimality.

######  Definition 18.

Given a complete directed graph $G=([n],E)$ and rank information
$\\{r_{i}\\}_{i\in[n]}$ representing strict preferences of agent $i\in[n]$ for
the edges incident to node $i$, an arborescence $\tau$ is Pareto-optimal if
there is no other arborescencce $\tau^{\prime}$ such that
$r_{i}(\tau^{\prime}_{i})\leq r_{i}(\tau_{i})$ for all $i\in[n]$ and
$r_{i}(\tau^{\prime}_{i^{*}})<r_{i}(\tau_{i^{*}})$ for some agent
$i^{*}\in[n]$.

######  Theorem 19.

Given an instance of OSA consisting of a directed graph $G=([n],E)$ and rank
information $\\{r_{i}\\}_{i\in[n]}$, an arborescence $\tau$ can be produced by
an action sequence if and only if $\tau$ is Pareto-optimal.

###### Proof.

Using Corollary 17, it suffices to show that an arborescence $\tau$ can be
accepted by Algorithm 2 if and only if it is Pareto-optimal.

Assume that Algorithm 2 fails for some arborescence $\tau$. This means that
Top is empty after the execution of line 3 in some iteration of the while
loop. Hence, for every agent $i\in P$, it is $\tau_{i}\not=\textsc{BR}(i,M)$.
Consider a node $k\in P$ that is furthest from the root node in $\tau$. Let
$\nu_{k}=\textsc{BR}(k,M)$ and assume that $\nu_{k}$ belongs to the subtree of
$k$ in $\tau$. Since $\nu_{k}=\textsc{BR}(k,M)$, $M\cup\\{(k,\nu_{k})\\}$ is
feasible. Hence, some edge $(k^{\prime},\tau_{k^{\prime}})$ in the path from
$\nu_{k}$ to $k$ has not been checked yet by the algorithm. Therefore,
$k^{\prime}$ should belong to $P$. This contradicts the assumption that $k$ is
a node that is furthest from the root in $\tau$. Hence, $\nu_{k}$ does not
belong to the subtree of $k$ in $\tau$. By replacing the edge $(k,\mu_{k})$ by
$(k,\nu_{k})$ in $\tau$, we obtain an arborescence that Pareto-dominates
$\tau$ (recall that $r_{k}(\nu_{k})<r_{k}(\tau_{k})$).

Now, consider an arborescence $\tau$ that is not Pareto-optimal; we will show
that Algorithm 2 fails for it. Let $\tau^{\prime}$ be an arborescence that
Pareto-dominates $\tau$ and let $k$ be an agent who uses different actions in
$\tau$ and $\tau^{\prime}$ and is furthest from the root in $\tau$. Consider
the execution of the while loop in a step with $k\in P$. Repeating the
argument in the previous paragraph, we obtain that $\tau^{\prime}_{k}$ cannot
be in the subtree of $k$ in $\tau$. Hence, the collection of actions
$M\cup\\{(k,\tau^{\prime}_{k})\\}$ is feasible and, furthermore,
$r_{k}(\tau^{\prime}_{k})<r_{k}(\tau_{k})$. Thus,
$\textsc{BR}(k,M)\not=\tau_{k}$ and agent $k$ can never be included in Top
before Algorithm 2 fails. ∎

As there is always a maximum-weight arborescence that is Pareto-optimal, we
obtain the following corollary.

######  Corollary 20.

The price of serial dictatorship of maximum weight arborescence in complete
graphs is $1$.

##  7 Satisfiability

OSM and OSA enjoy many similarities; this is evident from our answers to the
three key questions. In contrast, the case of OSS is fundamentally different.

######  Theorem 21.

Any action sequence yields a $2$-approximate solution to OSS.

###### Proof.

Consider an action sequence $\pi$. Then, the quantity
$P(i,C_{\pi^{i}})+N(i,C_{\pi^{i}})$ is the total weight of the clauses in
which variable $x_{i}$ appears and which are unsatisfied when it is the turn
of agent $i$ to act. Hence,
$\sum_{i\in[n]}{\left(P(i,C_{\pi^{i}})+N(i,C_{\pi^{i}})\right)}$ is an upper
bound on the total weight in all clauses. In addition, the value agent $i$
gets is clearly
$v_{i}(\pi^{i})\geq\frac{1}{2}\left(P(i,C_{\pi^{i}})+N(i,C_{\pi^{i}})\right)$.
Thus,

$\displaystyle\mathrm{SW}(\pi)$
$\displaystyle=\sum_{i\in[n]}{v_{i}(\pi^{i})}\geq\frac{1}{2}\sum_{i\in[n]}{\left(P(i,C_{\pi^{i}})+N(i,C_{\pi^{i}})\right)}\geq\frac{1}{2}\sum_{j\in[m]}{w(C_{j})}\geq\frac{1}{2}\mathrm{SW}(\widehat{\pi}),$

where $\widehat{\pi}$ denotes the optimal action sequence for the OSS
instance. ∎

Given Theorem 21, the obvious next step would be to design more sophisticated
algorithms for achieving a better-than-$2$ approximation ratio with
polynomially many queries. However, we believe that there are important
obstacles in doing so for OSS, summarized in the next question:

> Open Question 2: Is there an exponential lower bound on the query complexity
> of (approximating) OSS?

Next, we denote by Sat-AS the problem of deciding whether a given Boolean
assignment for the underlying satisfiability instance of OSS can be produced
by an action sequence. In contrast to the easiness of deciding whether a given
perfect matching or arborescence can be produced by an action sequence, Sat-AS
turns out to be intractable.

######  Theorem 22.

Sat-AS is NP-hard.

###### Proof.

We prove the theorem by presenting a polynomial-time reduction from
Exact-3Cover (X3C). An instance of X3C consists of a universe $\mathcal{U}$ of
$3q$ elements and a collection $\mathcal{T}$ of $t$ sets that each contains
exactly three elements from $\mathcal{U}$. The problem of deciding whether
there exists an exact 3-cover, i.e., a subcollection of $q$ sets from
$\mathcal{T}$ that includes all elements of $\mathcal{U}$, is a well-known NP-
hard problem [GJ79].

For an element $x\in\mathcal{U}$, we write $f(x)=|T\in\mathcal{T}:x\in T|$ to
denote the frequency of $x$ in collection $\mathcal{T}$. We construct a
satisfiability instance which contains one element variable for each element
in $\mathcal{U}$, one set variable for each set in $\mathcal{T}$, and one
auxiliary variable $Q$. Additionally, there are five types of clauses, each of
which contains at most two literals:

  * •

Type A: Clause $(T_{i}\vee T_{j})$ of weight $1$ for each pair of distinct
sets $T_{i},T_{j}\in\mathcal{T}$. There are a total of $t(t-1)/2$ such
clauses.

  * •

Type B: Clauses $(T\vee\overline{x}),(T\vee\overline{y}),$ and
$(T\vee\overline{z})$, each of weight $1$, for each set
$T=\\{x,y,z\\}\in\mathcal{T}$. There are a total of $3t$ such clauses.

  * •

Type C: Clause $(x\vee\overline{Q})$ of weight $f(x)-1/3$ for each element
$x\in\mathcal{U}$. There are a total of $3q$ such clauses.

  * •

Type D: Clauses
$(Q\vee\overline{T_{1}}),(Q\vee\overline{T_{2}}),\dots,(Q\vee\overline{T_{t}})$,
each of weight $t-q+7/3$. There are a total of $t$ such clauses.

  * •

Type E: Clause (with singleton literal) $\overline{Q}$ of weight
$t^{2}-qt+7t/3-1/3$.

Hence, the satisfiability instance consists of $n=3q+t+1$ variables and
$m=t^{2}/2+7t/2+3q+1$ clauses. We now show that there is an action sequence
which assigns the value of True to each variable of the satisfiability
instance if and only if the X3C instance has an exact 3-cover. The next three
lemmas state important properties an action sequence must have so that all
variables are set to True. We use the terms set agent and element agent to
refer to the agents who control the corresponding variables.

######  Lemma 23.

Agent $Q$ should act after all element agents.

###### Proof.

Notice that variable $Q$ appears as positive literal in clauses of total
weight $t^{2}-qt+7t/3$. Denoting by $w_{C}$ the total weight of all type C
clauses, we have that $Q$ appears as negative literal in clauses of total
weight $t^{2}-qt+7t/3-1/3+w_{C}$. Since $w_{C}\geq 2/3$, agent $Q$ can act and
set its variable to True only after all Type C clauses are satisfied, which
implies that all element agents have acted before (and set their variable to
True). ∎

######  Lemma 24.

Element agent $x$ should act after at least one set agent $T$ such that $x\in
T$ has acted.

###### Proof.

Element variable $x$ appears as positive and negative literal in clauses of
total weight $f(x)-1/3$ and $f(x)$, respectively. As literal $\overline{x}$
appears only in type B clauses, the element agent $x$ can set variable $x$ to
True only if at least one set agent $T$ such that $x\in T$ acted before (and
set her variable to True). ∎

######  Lemma 25.

At most $q$ many set agents can act before agent $Q$.

###### Proof.

Consider the time when $q$ set agents have acted; denote them by set $R$.
Every set agent $T$ not belonging to $R$ appears as positive and negative
literal in clauses of total weight $t-q+2$ and $t-q+7/3$, respectively, and
would set their variable to False if they acted before agent $Q$ acts (and
decreases the total weight of unsatisfied clauses that include $T$ as a
negative literal). ∎

Lemmas 23, 24, and 25 establish that the action sequence that assigns each
variable to True must have the following form: it starts with a set $R$ of at
most $q$ set agents corresponding to an exact 3-cover of the X3C instance,
then come all the $3q$ element agents, followed by agent $Q$, and finally the
remaining set agents. We can verify that such a structure works for any $R$
that form an exact 3-cover, completing the proof. ∎

Finally, we show that the price of serial dictatorship for maximum
satisfiability is strictly higher than $1$.

######  Theorem 26.

There exists an OSS instance in which no action sequence produces better than
$3/2$-approximate solution to the underlying satisfiability instance.

###### Proof.

Let $\varepsilon>0$ be a negligibly small value. Consider the OSS instance
defined by three Boolean variables $x_{1},x_{2},x_{3}$ and the following six
clauses: $(x_{1}\vee\overline{x_{2}}\vee\overline{x_{3}})$,
$(\overline{x_{1}}\vee x_{2}\vee\overline{x_{3}})$,
$(\overline{x_{1}}\vee\overline{x_{2}}\vee x_{3})$, each of weight $1$, and
$(x_{1})$, $(x_{2})$, $(x_{3})$, each of weight $1-\varepsilon$. It is easy to
verify that any action sequence sets the first two variables to $0$ and the
third one to $1$, producing an assignment that satisfies clauses of total
weight at most $4-\varepsilon$ while the assignment $x_{1}=x_{2}=x_{3}=1$ has
maximum total weight of $6-3\varepsilon$. ∎

Closing the gap between $3/2$ and $2$ is an important open problem.

> Open Question 3: What is the tight bound on the price of serial dictatorship
> for maximum satisfiability?

Better upper bound on the price of serial dictatorship for maximum
satisfiability should exploit simple greedy algorithms. An algorithm we have
studied considers the agents in monotone non-increasing order in terms of the
total weight in singleton clauses containing their variable. Proving that this
algorithm has an approximation ratio, say, $3/2$, would be enough to close the
PoSD gap. Notice that this would match a known $3/2$ bound from [CFZ97] for a
slightly more complicated greedy algorithm proposed by Johnson [Joh74].

##  8 Truthful Implementation

In this section, we explore truthful implementations of algorithms for
OptimalSequence. A serial dictatorship, that uses a fixed action sequence, is
the simplest truthful mechanism for OptimalSequence. As algorithms exploit
queries to the agents in the computation of action sequences, the agents may
have incentives to misreport their valuations and benefit from the output of
the algorithm. Payments can be used in the design of sophisticated algorithms
to ensure that responses to the queries are sincere.

In this section, we use the terms mechanism and algorithm interchangeably. In
general, a mechanism for OptimalSequence takes as input (part of) the
valuations of the agents and decides an action sequence outcome and payments
that are imposed to the agents. Formally, we write ${\bf
v}=\\{v_{i}\\}_{i\in[n]}$ to denote the valuations of all agents, while ${\bf
v}_{-i}$ is the restriction of ${\bf v}$ to the values of all agents besides
$i$. For a mechanism, we typically use $M({\bf v})$ to denote the action
sequence computed on input (part of) the valuation vector ${\bf v}$.222 Of
course, we assume that any agent $i$ can compute her valuations $v_{i}(S)$ for
any action subsequence $S$. For the specific valuations structures, this
implies that agent $i$ can simulate the actions of agents appearing in $S$,
and thus can decide the best available action for her. That is, we assume a
complete information environment for the agents, as opposed to the mechanism
which relies on queries to elicit information about valuations. As usual, the
notation $M^{i}({\bf v})$ is used to denote the prefix of agent $i$ in the
action sequence $M({\bf v})$. Also, we denote by $p_{i}({\bf v})$ the payment
imposed to agent $i\in[n]$. Then, the quantity $v_{i}(M^{i}({\bf
v}))-p_{i}({\bf v})$ is simply the utility of agent $i$ when agents report the
valuation vector ${\bf v}$. Truthfulness requires that the mechanism returns
the action sequence $M({\bf v})$ and payments $p_{i}({\bf v})$ for $i\in[n]$
so that no agent $i$ has an incentive to misreport any false valuation
$v^{\prime}_{i}$ instead of her true valuation $v_{i}$, for any valuations
${\bf v}_{-i}$ by the other agents, i.e.,

$\displaystyle v_{i}(M^{i}({\bf v}))-p_{i}({\bf v})$ $\displaystyle\geq
v_{i}(M^{i}({\bf v}_{-i},v^{\prime}_{i}))-p_{i}({\bf v}_{-i},v^{\prime}_{i}).$

In other words, truth-telling is a utility-maximizing strategy for agent $i$,
no matter what strategies the other agents use. To adapt this definition to
randomized mechanisms (in which either the action sequence or the payment part
are random), it suffices to use expectations of all terms.

In the following, we would like to explore whether the algorithms for
OptimalSequence we have already designed are truthful for appropriately
defined payments. In other words, we explore whether they have truthful
implementations. A useful tool here might be a well-known cycle monotonicity
characterization result of Rochet [Roc87]. However, the following much simpler
argument is enough to prove negative results.

######  Lemma 27.

An algorithm $M$ has a truthful implementation only if for any valuation
profile ${\bf v}=({\bf v}_{-i},v_{i})$ and an alternative valuation
$v^{\prime}_{i}$ that agent $i$ may report, the following is true:

$\displaystyle v_{i}(M^{i}({\bf v}))+v^{\prime}_{i}(M^{i}({{\bf
v}_{-i}},v^{\prime}_{i}))\geq v_{i}(M^{i}({{\bf
v}_{-i}},v^{\prime}_{i}))+v^{\prime}_{i}(M^{i}({{\bf v}})).$ (5)

###### Proof.

Fix an agent $i\in[n]$. By truthfulness, we know that an agent $i$ has no
incentive to misreport her value from $v_{i}$ to $v^{\prime}_{i}$ and vice
versa. That is, assuming payment $p_{i}$,

$\displaystyle v_{i}(M^{i}({\bf v}))-p_{i}({\bf v})\geq v_{i}(M^{i}({\bf
v}_{-i},v^{\prime}_{i}))-p_{i}({\bf v}_{-i},v^{\prime}_{i})$ $\displaystyle
v^{\prime}_{i}(M^{i}({\bf v}_{-i},v^{\prime}_{i}))-p_{i}({\bf
v}_{-i},v^{\prime}_{i})\geq v^{\prime}_{i}(M^{i}({\bf v}))-p_{i}({\bf v}).$

Summing the inequalities above, we get the desired inequality. ∎

We can now use Lemma 27 to prove some non-implementability results.

######  Theorem 28.

Algorithms 1, 3, and Det do not have truthful implementations.

###### Proof.

We present instances of OSM, OSA, and OptimalSequence for which Algorithms 1,
3, and Det, respectively, do not satisfy the inequality (5) in Lemma 27 and,
thus, cannot be implemented truthfully.

Consider the OSM instance with two agents and two items and the following
weights: $w(1,1)=1+\varepsilon$, $w(1,2)=1$ defining the valuation $v_{1}$ for
agent $1$, and $w(2,1)=1$, $w(2,2)=1-\varepsilon$ defining the valuation
$v_{2}$ for agent $1$. Algorithm 1 (implicitly) matches agent $1$ to item $1$
and agent $2$ to item $2$. Now, consider another valuation profile
$(v^{\prime}_{1},v_{2})$ corresponding to the weights $w(1,1)=1-\varepsilon$,
$w(1,2)=0$, $w(2,1)=1$, $w(2,2)=1-\varepsilon$, and observe that Algorithm 1
matches agent $2$ to item $1$ and agent $1$ to item $2$. Denoting the outcome
of Algorithm 1 by $M$, we have $v_{1}(M^{1}({\bf v}))=1+\varepsilon$ and
$v^{\prime}_{1}(M^{1}({\bf v}_{-1},v^{\prime}_{1}))=0$, while
$v_{1}(M^{1}({\bf v_{-1}},v^{\prime}_{1})=1$ and $v^{\prime}_{1}(M^{1}({\bf
v}))=1-\varepsilon$. These values violate inequality (5).

Next, consider the $4$-agent OSA instance with the following edge-weights:
$w(1,2)=1-\varepsilon$, $w(1,4)=\varepsilon$, $w(2,1)=1$,
$w(3,4)=1-\varepsilon$, and $w(4,3)=1$, with all the remaining edges having
weight $0$. We denote the corresponding valuation profiles of the three agents
by $v_{1}$, $v_{2},v_{3}$ and $v_{4}$. Also, consider the following instance
where the edge-weights are $w(1,2)=1+\varepsilon$, $w(1,4)=1$, $w(2,1)=1$,
$w(3,4)=1-\varepsilon$, and $w(4,3)=1$, with all the remaining edges having
weight $0$. We denote the corresponding valuation profiles of the three agents
by $v^{\prime}_{1}$, $v_{2},v_{3}$ and $v_{3}$. We have $v_{1}(M^{1}({\bf
v}))=0$ and $v^{\prime}_{1}(M^{1}({\bf
v}_{-1},v^{\prime}_{1}))=1+\varepsilon$, while $v_{1}(M^{1}({\bf
v_{-1}},v^{\prime}_{1}))=1-\varepsilon$ and $v^{\prime}_{1}(M^{1}({\bf
v}))=1$, again violating inequality (5).

Finally, consider the instance of OptimalSequence with $n$ agents having the
following valuations: there is a set $C$ of $c$ agents that have $v_{i}(S)=10$
if $|S|<c$ and $v_{i}(S)=8$ otherwise. The rest of the agents have valuation
$v_{i}(S)=9$ for any $S$. So, the action sequence $M({\bf v})$ has the agents
in $C$ in the first $c$ positions, with the agents of $[n]\setminus C$ next.
For some agent $j\in C$, the valuations $v^{\prime}_{j}$ are defined as
$v^{\prime}_{j}(S)=8$ if $|S|<c$ and $v^{\prime}_{j}(S)=0$, otherwise. The
action sequence $M({\bf v_{-j}},v^{\prime}_{j})$ has the agents of
$C\setminus\\{j\\}$ and an additional agent from $[n]\setminus C$ in the first
$c$ positions, and the rest of the agents (including $j$) in the last $n-c$
positions. We have $v_{j}(M^{j}({\bf v}))=10$ and $v_{j}(M^{j}({\bf
v_{-j}},v^{\prime}_{j})=8$, while $v^{\prime}_{j}(M^{j}({\bf v}))=8$ and
$v^{\prime}_{j}(M^{j}({\bf v_{-j}},v^{\prime}_{j}))=0$, again violating
inequality (5). ∎

On the positive side, Rand can be truthfully implemented using VCG payments.
Recall that Rand selects a random set $C$ of $c\leq n$ agents and puts them in
the beginning of the action sequence in such a way that their contribution to
the social welfare is maximized. By adapting the VCG payment scheme, we can
define payments as $p_{i}({\bf v})=0$ if $i$ is not selected in set $C$ and

$\displaystyle p_{i}({\bf v})$ $\displaystyle=\sum_{k\in
C\setminus\\{i\\}}{v_{k}(M^{k}({\bf v}_{-i},{\bf 0}))}-\sum_{k\in
C\setminus\\{i\\}}{v_{k}(M^{k}({\bf v}))}$

otherwise, where $\bf 0$ denotes valuation of zero for agent $i$ for any
action subsequence. In this way, Rand enjoys properties like non-negative
payments and individual rationality (i.e., agents enjoy non-negative
utilities).

We will now show how to use the VCG paradigm in a variation of Det, to get the
truthful mechanism Det+ for OptimalSequence. Like Det, Det+ uses an integer
parameter $c$. It considers all action sequences which have their last $n-c$
agents ordered according to their indices and picks the one of maximum social
welfare (in this way, the outcome of Det+ is at least as good as that of Det).
VCG payments, defined as

$\displaystyle p_{i}({\bf v})$
$\displaystyle=\sum_{k\in[n]\setminus\\{i\\}}{v_{k}(M^{k}({\bf v}_{-i},{\bf
0}))}-\sum_{k\in[n]\setminus\\{i\\}}{v_{k}(M^{k}({\bf v}))},$

lead to a truthful implementation for Det+ (with non-negative payments and
individual rationality). The next statement summarizes the above discussion on
Rand and Det+.

######  Theorem 29.

Algorithms Rand and Det+ have truthful implementations. Also, Det+ achieves
the same approximation guarantee with Det.

We remark that, in the definition of the payments, it is important to consider
agent $i$ with zero valuation. Essentially, the VCG payment of agent $i$ is
equal to the harm that her non-zero valuation (as opposed to her existence,
which is the usual interpretation) causes to the other agents. Furthermore, we
remark that the payments for agents in the last $n-c$ positions of $M({\bf
v})$ is not necessarily $0$.

In addition to the better approximation ratio that Rand achieves compared to
Det+, another advantage is that payments require only polylogarithmically many
queries to compute (when the parameter $c$ is set to
$\Theta\left(\frac{\ln{n}}{\ln\ln{n}}\right)$). On the other hand, the VCG
payments for Det+ require $\Theta(n^{2})$ queries.333In comparison to random
serial dictatorship (RSD), which selects an action sequence from
$\mathcal{S}_{[n]}$ uniformly at random, the truthful algorithms Rand and Det+
achieve sublinear approximation ratio at the expense of using payments. We can
show that this is necessary: any (possibly randomized) mechanism for
OptimalSequence that is truthful without payments has an approximation ratio
of at least $n$.

> Open Question 4: Is there a deterministic algorithm for OptimalSequence that
> uses polynomially many queries, achieves sublinear approximation ratio, and
> has a truthful implementation with payments that can be computed with
> polylogarithmically many queries?

Regarding OptimalSequence instances with specific valuation structures, recall
that OSS has a truthful mechanism that does not use payments at all. Indeed,
any serial dictatorship is truthful and furthermore achieves an approximation
ratio of $2$. We will present a similar result for OSA. In particular, we
develop the randomized algorithm Bit that is truthful without payments and
computes $2$-approximate arborescences. Bit tosses a fair coin and returns the
action sequence $(1,2,...,n)$ on Heads, and the reverse action sequence
$(n,n-1,...,1)$ on Tails.

######  Theorem 30.

Algorithm Bit is truthful and returns $2$-approximate solutions of OSA.444We
remark that the argument in the proof of Theorem 30 can be used to show that
RSD returns a $2$-approximate solution too. Obviously, Bit is superior since
it uses only a single random coin.

###### Proof.

Algorithm Bit is clearly truthful since it does not use any queries. We will
account for the contribution of an agent to the social welfare only if/when
she gets a value of $v_{i}(\emptyset)$. Consider an agent $i\in[n]$ and let
$(i,k)$ be her rank-$1$ edge. Notice that agent $i$ will draw edge $(i,k)$ if
she acts before agent $k$, which happens with probability $1/2$. Hence,
$\mathrm{SW}(\pi)=\sum_{i\in[n]}{v_{i}(\pi^{i})}\geq\frac{1}{2}\sum_{i\in[n]}{v_{i}(\emptyset)}=\frac{1}{2}\mathrm{SW}(\widehat{\pi})$,
where $\widehat{\pi}$ is the optimal action sequence. ∎

> Open Question 5: Is there an OSM algorithm that uses polynomially many
> queries, achieves constant approximation ratio, and has a truthful
> implementation?

Recall that the existence of an algorithm that solves OSM exactly is open. In
such a case, VCG payments would provide a truthful implementation.

Finally, regarding OSS, Theorem 26 implies that any serial dictatorship is a
$2$-aproximate truthful mechanism without payments.

## References

  * [ACMM05] David J. Abraham, Katarína Cechlárová, David F. Manlove, and Kurt Mehlhorn.  Pareto optimality in house allocation problems.  In Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC), pages 3–15, 2005.
  * [ADK+08] Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden.  The price of stability for network design with fair cost allocation.  SIAM Journal on Computing, 38(4):1602–1623, 2008.
  * [AS98] Atila Abdulkadiroğlu and Tayfun Sönmez.  Random serial dictatorship and the core from random endowments in house allocation problems.  Econometrica, 66(3):689–701, 1998.
  * [BBLM10] Allan Borodin, Joan Boyar, Kim S. Larsen, and Nazanin Mirmohammadi.  Priority algorithms for graph optimization problems.  Theorerical Computer Science, 411(1):239–258, 2010.
  * [BFT11] Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis.  The price of fairness.  Operations Research, 59(1):17–31, 2011.
  * [BM01] Anna Bogomolnaia and Hervé Moulin.  A new solution to the random assignment problem.  Journal of Economic Theory, 100(2):295–328, 2001.
  * [BNR03] Allan Borodin, Morten N. Nielsen, and Charles Rackoff.  (incremental) priority algorithms.  Algorithmica, 37(4):295–326, 2003.
  * [CFRF+16] Ioannis Caragiannis, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Kristoffer Arnsfelt Hansen, and Zihan Tan.  Truthful facility assignment with resource augmentation: An exact analysis of serial dictatorship.  In Proceedings of the 12th Conference on Web and Internet Economics (WINE), pages 236–250, 2016.
  * [CFZ97] Jianer Chen, D.K. Friesen, and Hao Zheng.  Tight bound on johnson’s algorithm for max-sat.  In Proceedings of the 12th Annual IEEE Conference on Computational Complexity (CCC), pages 274–281, 1997.
  * [CKKK12] Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, and Maria Kyropoulou.  The efficiency of fair division.  Theory of Computing Systems, 50(4):589–610, 2012.
  * [Cla71] Edward H. Clarke.  Multipart pricing of public goods.  Public Choice, 11:17–33, 1971.
  * [CLRS09] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  Introduction to Algorithms.  The MIT Press, 3rd edition, 2009.
  * [DI04] Sashka Davis and Russell Impagliazzo.  Models of greedy algorithms for graph problems.  In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page 381–390, 2004.
  * [DMS17] Argyrios Deligkas, George B. Mertzios, and Paul G. Spirakis.  The computational complexity of weighted greedy matching.  In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), page 466–472, 2017.
  * [DV12] Shahar Dobzinski and Jan Vondrák.  From query complexity to computational complexity.  In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC), pages 1107–1116, 2012.
  * [FRFZ14] Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, and Jie Zhang.  Social welfare in one-sided matchings: Random priority and beyond.  In Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT), pages 1–12, 2014.
  * [GJ79] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences).  W. H. Freeman, 1979.
  * [GLW21] Laurent Gourvès, Julien Lesca, and Anaëlle Wilczynski.  On fairness via picking sequences in allocation of indivisible goods.  In Proceedings of the 7th International Conference on Algorithmic Decision Theory (ADT), pages 258–272, 2021.
  * [Joh74] David S. Johnson.  Approximation algorithms for combinatorial problems.  Journal of Computer and System Sciences, 9(3):256–278, 1974.
  * [KMRZ19] Piotr Krysta, David F. Manlove, Baharak Rastegari, and Jinshan Zhang.  Size versus truthfulness in the house allocation problem.  Algorithmica, 81(9):3422–3463, 2019.
  * [LLN06] Benny Lehmann, Daniel Lehmann, and Noam Nisan.  Combinatorial auctions with decreasing marginal utilities.  Games and Economic Behavior, 55(2):270–296, 2006.
  * [Man13] David F. Manlove.  Algorithmics of Matching Under Preferences.  World Scientific, 2013.
  * [PSWZ17] Matthias Poloczek, Georg Schnitger, David Williamson, and Anke Zuylen.  Greedy algorithms for the maximum satisfiability problem: Simple algorithms and inapproximability bounds.  SIAM Journal on Computing, 46:1029–1061, 01 2017.
  * [Roc87] Jean-Charles Rochet.  A necessary and sufficient condition for rationalizability in a quasi-linear context.  Journal of Mathematical Economics, 16(2):191–200, 1987.
  * [RS90] Alvin E. Roth and Marilda A. Oliveira Sotomayor.  Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis.  Cambridge University Press, 1990.
  * [Sve99] Lars-Gunnar Svensson.  Strategy-proof allocation of indivisble goods.  Social Choice and Welfare, 16(4):557–567, 1999.
  * [Yao77] Andrew Chi-Chin Yao.  Probabilistic computations: Toward a unified measure of complexity.  In Proceedings and the 18th Annual Symposium on Foundations of Computer Science (FOCS), pages 222–227, 1977.