# Socially efficient mechanism on the minimum budget

Hirota Kinoshita
The University of Tokyo
<EMAIL_ADDRESS>This research project was conducted at IBM
Research. Takayuki Osogami
IBM Research - Tokyo
<EMAIL_ADDRESS>Kohei Miyaguchi
IBM Research - Tokyo
<EMAIL_ADDRESS>
###### Abstract

In social decision-making among strategic agents, a universal focus lies on
the balance between social and individual interests. Socially efficient
mechanisms are thus desirably designed to not only maximize the social welfare
but also incentivize the agents for their own profit. Under a generalized
model that includes applications such as double auctions and trading networks,
this study establishes a socially efficient (SE), dominant-strategy incentive
compatible (DSIC), and individually rational (IR) mechanism with the minimum
total budget expensed to the agents. The present method exploits discrete and
known type domains to reduce a set of constraints into the shortest path
problem in a weighted graph. In addition to theoretical derivation, we
substantiate the optimality of the proposed mechanism through numerical
experiments, where it certifies strictly lower budget than Vickery-Clarke-
Groves (VCG) mechanisms for a wide class of instances.

##  1 Introduction

We address the ubiquitous problem of getting a group of self-interested
strategic agents to act in the best interests of society. A common approach in
mechanism design is to introduce a broker, who selects the optimal option with
respect to social welfare, maximizing the total benefits for the agents or
minimizing their total costs, and incentivizes the agents to act for social
welfare according to the selected option by paying them or receiving payments
from them. Such mechanisms that can be formally characterized by the
properties of social efficiency (SE), dominant-strategy incentive
compatibility (DSIC), and individually rationality (IR) are considered to be
effective in various applications such as trading networks [25, 29] and
double-sided auction in cloud markets [3, 17, 19]. In particular, a powerful
generic solution is the Vickrey-Clarke-Groves (VCG) mechanism, which has been
analyzed and applied in numerous technical and practical contexts.

However, the prior work establishes impossibility theorems, suggesting that
SE, DSIC, and IR may not be achieved without a budget contributed from the
broker [25, 29]. It would thus be reasonable for the broker to minimize the
budget while achieving the three properties or to maximize revenue (i.e.,
negative budget) if those properties can be achieved without a (positive)
budget, possibly to compensate for the budget needed for other occasions. An
example appears in workforce management, where each labor receives
compensation for their workload from the supervisor (broker) who seeks to
achieve a goal as a result of the collective work; then the supervisor should
minimize the total compensation as long as the goal is achieved with minimal
total workload (negative social welfare is minimized). Related applications
include federated learning [40] and cloud-sourcing [39].

Our primary contribution is a novel algorithm that gives the budget-optimal
solution among all mechanisms that satisfy the desired properties of SE, DISC,
and IR. A key idea in our approach is to exploit discrete and known type
domains of agents to reduce a set of constraints, which are required by the
above properties, into the shortest path problem in a weighted graph. Unlike
the majority of related works, the proposed mechanism lies beyond the
celebrated class of VCG mechanisms. The proposed mechanism outperforms the
best possible VCG mechanism and gives strictly lower budgets for a majority of
random instances in our numerical experiments.

The present work develops upon a general model of mechanism design formally
defined in Section 3. As a baseline, we revisit the VCG mechanism in Section 4
from the perspective of minimizing the budget. In Section 5, we develop a
mechanism that achieves the minimum budget among all mechanisms having the
desired properties, followed by theoretical discussions about the optimality
and the computational complexity. Finally, numerical experiments in Section 6
add empirical analysis of the optimal budget obtained by the proposed
mechanism.

##  2 Related work

#### Maximizing revenue without social efficiency

There have been a number of studies that seek to maximize the revenue just as
we minimize the budget, however, at the expense of SE (thus only guarantee
DSIC and IR). They mostly focus on one-sided auctions, where the agents incur
no costs and hence the broker charges them. The noticeable majority of such
approaches study the class of affine maximizer auction (AMA) [21, 22, 33, 16,
6, 5], which can be seen as a technical variant of the VCG mechanism. While
those studies are clearly distinguished from ours as they no longer require SE
and mostly restrict themselves to auctions and to the specific class of
solutions, we discuss in Appendix D how the proposed mechanism can also be
technically extended along this setting.

#### Balancing budget

A series of studies have sought to control the budget exactly to zero (strong
budget balance; SBB), or suppress it at most zero (weak budget balance; WBB)
instead. On one hand, they have revealed negative facts such as the Myerson-
Satterthwaite theorem [25, 30], the Green-Laffont impossibility theorem [8,
9], and other related or extended results [34, 27, 29]. On the other hand,
when WBB is achievable, instead of maximizing the revenue as we do, the prior
work has investigated ways to distribute the positive revenue back to agents,
which has been an interest in socially efficient mechanism design since the
earliest literature [36, 10, 37, 31, 4, 1]. In a variety of related studies,
they have derived analytical methods for some simple cases [2, 14, 15, 11, 12,
13, 26] and also provided approximately optimal heuristics for more general
difficult settings [7, 24, 35]. Unlike these prior studies, our approach
minimizes the budget in a provably optimal manner when WBB is not achievable,
and maximizes the revenue when it is achievable. The positive revenue achieved
by our approach could also be redistributed to the agents, as we discuss in
Appendix F.

##  3 Model

We start with a common context in mechanism design [28], formally encapsulated
in def:env as an environment. It involves a set of agents $\mathcal{N}$ and a
set of available options $\mathcal{X}$; each agent $i\in\mathcal{N}$ gains
individual value $v_{i}(X)\in\mathbb{R}$ determined upon each option
$X\in\mathcal{X}$ by a type $v_{i}\colon\mathcal{X}\to\mathbb{R}$ drawn from
their type domain $\mathcal{V}_{i}$. As supplementary notations, given an
environment $\mathcal{E}=(\mathcal{N},\mathcal{X},\mathcal{V})$, we let
$\mathcal{V}_{-i}\coloneqq\prod_{j\in\mathcal{N}\setminus\\{i\\}}\mathcal{V}_{j}$
for each agent $i\in\mathcal{N}$ denote the Cartesian product of all agents’
type domains except $i$’s; similarly, for any $v\in\mathcal{V}$ and
$i\in\mathcal{N}$, let
$v_{-i}\coloneqq(v_{j})_{j\in\mathcal{N}\setminus\\{i\\}}\in\mathcal{V}_{-i}$
denote a partial list of $v$ that excludes the $i$’s type $v_{i}$ only.

######  Definition 1 (Environment).

def:env An environment denotes a tuple
$\mathcal{E}=(\mathcal{N},\mathcal{X},\mathcal{V})$, which consists of a non-
empty finite set of agents $\mathcal{N}$, a non-empty (possibly infinite) set
of options $\mathcal{X}$, and the Cartesian product
$\mathcal{V}=\prod_{i\in\mathcal{N}}\mathcal{V}_{i}$ of non-empty finite sets
of types, or type domains, $\mathcal{V}_{i}\subseteq\mathbb{R}^{\mathcal{X}}$
for each agent $i\in\mathcal{N}$.

A mechanism in def:AMD is exercised upon the environment by introducing an
independent party, who we call the broker. It serves as a decision maker on
behalf of agents, while it also compensates or charges them depending on the
types reported by them, which may differ from their true types. The present
model treats the mechanism as a static and public protocol known to all
agents.

######  Definition 2 (Mechanism).

def:AMD For an environment
$\mathcal{E}=(\mathcal{N},\mathcal{X},\mathcal{V})$, a mechanism
$\mathcal{M}=(\phi,\tau)$ consists of an option rule
$\phi:\mathcal{V}\rightarrow\mathcal{X}$ and a payment rule
$\tau:\mathcal{V}\rightarrow\mathbb{R}^{\mathcal{N}}$, which works as follows:

  1. 1.

Each agent $i\in\mathcal{N}$ reports a type $\hat{v}_{i}\in\mathcal{V}_{i}$ to
the broker.

  2. 2.

Based on the list of reported types
$\hat{v}=(\hat{v}_{i})_{i\in\mathcal{N}}\in\mathcal{V}$, the broker selects an
option $\phi(\hat{v})\in\mathcal{X}$ and pays $\tau_{i}(\hat{v})\in\mathbb{R}$
to each agent $i\in\mathcal{N}$.111A negative payment $\tau_{i}(\hat{v})<0$
means the opposite transaction from the agent $i$ to the broker.

  3. 3.

It demands the budget
$B(\hat{v};\mathcal{M})\coloneqq\sum_{i\in\mathcal{N}}\tau_{i}(\hat{v})$ of
the broker, and results in the utilities $u_{i}(\hat{v};\mathcal{M})\coloneqq
v_{i}(\phi(\hat{v}))+\tau_{i}(\hat{v})$ for each agent $i\in\mathcal{N}$,
where $v_{i}$ denotes the true type of the agent $i$.

On designing such a mechanism, a prioritized interest lies in the social
welfare, which amounts to the net benefit that the mechanism produces on the
environment as a whole. A mechanism is thereby expected to always select the
option that maximizes the social welfare on behalf of the environment, when it
is said to satisfy Social Efficiency, or SE (1), in the following def:SE. In
addition, because agents individually seek higher profit, mechanisms are
required to be justified in the sense of def:justified. Namely, they should
satisfy not only SE but also both of two important properties in the following
def:DSIC_IR. Firstly, Dominant-Strategy Incentive Compatibility, or DSIC (4),
incentivizes agents to report their own type truthfully. In other words, DSIC
does not allow any agent to gain by reporting a false type. Secondly,
Individual Rationality, or IR (5), clearly ensures every agent non-negative
utility; they do not want to experience negative utility due to participation.
Note that our formal definitions of SE (1) and IR (5) correctly match the
literal concepts when they are accompanied by DSIC (4). We basically consider
mechanisms that satisfy DSIC hereafter, and thus do not explicitly distinguish
the types reported by agents from their true ones.

######  Definition 3 (SE).

def:SE For an environment $\mathcal{E}=(\mathcal{N},\mathcal{X},\mathcal{V})$,
a mechanism $\mathcal{M}=(\phi,\tau)$, or just an option rule $\phi$, is said
to satisfy Social Efficiency (SE) if and only if

$\displaystyle\phi(v)\in\mathop{\rm argmax}\limits_{X\in\mathcal{X}}S(X;v),$
$\displaystyle\forall v\in\mathcal{V},$ (1)

where we define the social welfare
$S:\mathcal{X}\times\mathcal{V}\to\mathbb{R}$ as

$\displaystyle S(X;v)\coloneqq\sum_{i\in\mathcal{N}}v_{i}(X).$ (2)

The social welfare due to the mechanism $\mathcal{M}=(\phi,\tau)$ is also
expressed as follows:

$\displaystyle
S(\phi(v);v)=\sum_{i\in\mathcal{N}}u_{i}(v;\mathcal{M})-B(v;\mathcal{M}).$ (3)

######  Definition 4 (DSIC, IR).

def:DSIC_IR For an environment
$\mathcal{E}=(\mathcal{N},\mathcal{X},\mathcal{V})$, a mechanism
$\mathcal{M}=(\phi,\tau)$ is said to satisfy Dominant-Strategy Incentive
Compatibility (DSIC) if and only if

$\displaystyle u_{i}(v;\mathcal{M})$ $\displaystyle\geq
v_{i}(\phi(v_{i}^{\prime},v_{-i}))+\tau_{i}(v_{i}^{\prime},v_{-i}),$
$\displaystyle\forall v_{i}^{\prime}\in\mathcal{V}_{i},\forall
i\in\mathcal{N},\forall v\in\mathcal{V};$ (4)

Individual Rationality (IR) if and only if

$\displaystyle u_{i}(v;\mathcal{M})$ $\displaystyle\geq 0,$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V}.$ (5)

######  Definition 5 (Justified mechanism).

def:justified For an environment
$\mathcal{E}=(\mathcal{N},\mathcal{X},\mathcal{V})$, a mechanism
$\mathcal{M}=(\phi,\tau)$ is said to be justified if and only if it satisfies
SE (1), DSIC (4), and IR (5).

Feasibility for a justified mechanism to suppress the budget
$B(v;\mathcal{M})$ in def:AMD at most zero (weak budget balance; WBB), or
exactly equal to zero (strong budget balance; SBB), is known with negative
results even in a wide class of bilateral ($|\mathcal{N}|=2$) environments
[25, 30, 29]. We demonstrate in Section 5 how the proposed justified mechanism
is designed to achieve the minimum budget simultaneously for every type
$v\in\mathcal{V}$, with an arbitrarily specified option rule that satisfies SE
(1).

##  4 Vickrey-Clarke-Groves (VCG) mechanism

In the majority of mechanism design, such an option rule $\phi$ that satisfies
SE (1) often comes with the following payment rule $\tau$ (6) to form the
celebrated VCG family in def:VCG. Then thm:VCG_DSIC claims that any VCG
mechanism satisfies DSIC (4).

######  Definition 6 (VCG mechanism).

def:VCG A mechanism $\mathcal{M}=(\phi,\tau)$ is called the Vickrey-Clarke-
Groves (VCG) mechanism if and only if the option rule $\phi$ satisfies SE (1)
and

$\displaystyle\tau_{i}(v)$
$\displaystyle=S(\phi(v);v)-v_{i}(\phi(v))-h_{i}(v_{-i})$
$\displaystyle=\sum_{j\in\mathcal{N}\setminus\\{i\\}}v_{j}(\phi(v))-h_{i}(v_{-i}),$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V},$ (6)

with some functions
$(h_{i}:\mathcal{V}_{-i}\rightarrow\mathbb{R})_{i\in\mathcal{N}}$.

######  Theorem 1 (Theorem 1.17 in [28]).

thm:VCG_DSIC The VCG mechanism satisfies DSIC (4).

The so-called Clarke pivot rule in def:VCG-Clarke is one reasonable way to
choose $h_{i}$s in def:VCG. Such defined a mechanism, VCG-Clarke,
_conditionally_ guarantees IR (5). It is common in the literature to
implicitly assume environments where the maximum in (7) exists, but replacing
the maximum with the supremum preserves equivalent qualities without the
assumption.

######  Definition 7 (VCG-Clarke).

def:VCG-Clarke The Clarke pivot rule specifies the payment rule (6) by

$\displaystyle h_{i}(v_{-i})=h^{c}_{i}(v_{-i})$
$\displaystyle\coloneqq\max_{X\in\mathcal{X}}\left(S(X;v)-v_{i}(X)\right)$
$\displaystyle=\max_{X\in\mathcal{X}}\sum_{j\in\mathcal{N}\setminus\\{i\\}}v_{j}(X),$
$\displaystyle\forall v_{-i}\in\mathcal{V}_{-i},\forall i\in\mathcal{N},$ (7)

and we call this particular implementation of the VCG mechanism as VCG-Clarke.

######  Lemma 1 (Lemma 1.20 in [28]).

lem:VCG_IR VCG-Clarke $\mathcal{M}^{c}=(\phi,\tau^{c})$ makes every agent pay
to the broker:

$\displaystyle\tau^{c}_{i}(v)$ $\displaystyle\leq 0,$ $\displaystyle\forall
i\in\mathcal{N},\forall v\in\mathcal{V}.$ (8)

It satisfies IR (5) and thus justified if all possible types are non-negative
i.e.,

$\displaystyle v_{i}(X)$ $\displaystyle\geq 0,$ $\displaystyle\forall
v_{i}\in\mathcal{V}_{i},\forall i\in\mathcal{N},\forall X\in\mathcal{X}.$ (9)

The VCG-Clarke mechanism makes each agent $i\in\mathcal{N}$ pay to the broker
the quantity that expresses the negative effect that $i$’s participation has
on the other agents $\mathcal{N}\setminus\\{i\\}$ (see (36) in the proof of
lem:VCG_IR). Hence, agents who have negative valuation on the option $\phi(v)$
result in negative utility; IR may thus be violated in such cases. In order to
retain IR even when (9) does not hold, we introduce an unconditionally
justified VCG mechanism, VCG-budget, in def:VCG-budget. Moreover, this
mechanism achieves the minimum budget that can be obtained by any justified
VCG mechanism, as long as the option rule $\phi$ is fixed.

######  Definition 8 (VCG-budget).

def:VCG-budget VCG-budget is defined as the VCG mechanism implemented by

$\displaystyle h_{i}(v_{-i})=h^{b}_{i}(v_{-i})$
$\displaystyle\coloneqq\min_{v_{i}^{\prime}\in\mathcal{V}_{i}}S(\phi(v_{i}^{\prime},v_{-i});v_{i}^{\prime},v_{-i})$
$\displaystyle=\min_{v_{i}^{\prime}\in\mathcal{V}_{i}}\max_{X\in\mathcal{X}}S(X;v_{i}^{\prime},v_{-i}),$
$\displaystyle\forall v_{-i}\in\mathcal{V}_{-i},\forall i\in\mathcal{N}.$ (10)

######  Lemma 2.

lem:VCG-budget_IR VCG-budget satisfies IR (5); hence it is justified.

######  Theorem 2.

thm:VCG-budget_opt VCG-budget $\mathcal{M}^{b}=(\phi,\tau^{b})$ satisfies,
against any justified VCG mechanism $\mathcal{M}=(\phi,\tau)$,

$\displaystyle\tau^{b}_{i}(v)$ $\displaystyle\leq\tau_{i}(v),$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V}.$ (11)
$\displaystyle B(v;\mathcal{M}^{b})$ $\displaystyle\leq B(v;\mathcal{M}),$
$\displaystyle\forall v\in\mathcal{V}.$ (12)

Proofs of lem:VCG-budget_IR and thm:VCG-budget_opt are straightforward and
provided in Appendix A.

##  5 Proposed mechanism

Beyond the VCG family, the present study explores the entire universe of
justified mechanisms, out of which we identify and propose a budget-optimal
mechanism $\mathcal{M}^{*}=(\phi^{*},\tau^{*})$ in Algorithm 1. It consists of
two functions that respectively represent its option rule $\phi^{*}$ and
payment rule $\tau^{*}$: SelectOption, which takes in a type list
$v\in\mathcal{V}$ and returns an option $\phi^{*}(v)\in\mathcal{X}$, and
ComputePayments, which takes in a type list $v\in\mathcal{V}$ and returns a
list of payments $\tau^{*}(v)\in\mathbb{R}^{\mathcal{N}}$. The option rule
$\phi^{*}$ is arbitrarily specified in advance as long as it satisfies SE (1).
It is verified in Section 5.1 that the proposed mechanism is justified,
followed by detailed discussions in Section 5.2 about minimizing the budget,
with the computational complexity analyzed finally in Section 5.3.

Algorithm 1 The proposed mechanism built with an option rule $\phi^{*}$ that
satisfies SE (1).

SelectOption$v$$\triangleright$ Act as the option rule $\phi^{*}$.

1:$\phi^{*}(v)$. ComputePayments$v$ $\triangleright$ Act as the payment rule
$\tau^{*}$. $i\in\mathcal{N}$ $v_{i}^{\prime}\in\mathcal{V}_{i}$

2:$o(v_{i}^{\prime})\leftarrow\textproc{SelectOption}(v_{i}^{\prime},v_{-i})$
$\triangleright$ Find the options for all possible change of $v_{i}$.

3:$V\leftarrow\mathcal{V}_{i}\cup\\{\star\\}$ $\triangleright$ Define the set
of vertices.

4:$E\leftarrow V\times\mathcal{V}_{i}$ $\triangleright$ Define the set of
directed edges. $v_{i}^{\prime}\in\mathcal{V}_{i}$

5:$c(\star,v_{i}^{\prime})\leftarrow v_{i}^{\prime}(o(v_{i}^{\prime}))$
$\triangleright$ Set the weights of edges from $\star$.
$(v_{i}^{(1)},v_{i}^{(2)})\in\mathcal{V}_{i}^{2}$

6:$c(v_{i}^{(1)},v_{i}^{(2)})\leftarrow
v_{i}^{(2)}(o(v_{i}^{(2)}))-v_{i}^{(2)}(o(v_{i}^{(1)}))$ $\triangleright$ Set
the weights of remaining edges.

7:$\tau^{*}_{i}(v)\leftarrow-\Call{ShortestDistance}{\star,v_{i};(V,E,c)}$
$\triangleright$ Compute the shortest distance.

8:$(\tau^{*}_{i}(v))_{i\in\mathcal{N}}$

In $\Call{ComputePayments}{v}$, the payments
$(\tau^{*}_{i}(v))_{i\in\mathcal{N}}$ is independently computed for each agent
$i\in\mathcal{N}$. First, we build a weighted graph $G_{i}(v)$ that spans the
vertex set $\mathcal{V}_{i}\cup\\{\star\\}$, the agent’s type domain
$\mathcal{V}_{i}$ plus an auxiliary vertex $\star$. Then for every
$v_{i}^{\prime}\in\mathcal{V}_{i}$, a directed edge from $\star$ to
$v_{i}^{\prime}$ is equipped with a weight of
$v^{\prime}_{i}(\phi^{*}(v^{\prime}_{i},v_{-i}))$. We also make
$\mathcal{V}_{i}$, all vertices except $\star$, mutually connected by adding a
directed edge for every ordered pair
$(v_{i}^{(1)},v_{i}^{(2)})\in\mathcal{V}_{i}^{2}$ that weighs
$v_{i}^{(2)}(\phi^{*}(v_{i}^{(2)},v_{-i}))-v_{i}^{(2)}(\phi^{*}(v_{i}^{(1)},v_{-i}))$.
Finally, the oracle $\textproc{ShortestDistance}$ is called to exactly compute
the shortest distance from the source node $\star$ to the destination $v_{i}$
in the graph $G_{i}(v)$. The idea comes from the observation that the
inequalities required by DSIC (4) and IR (5) are seen as a set of dual
constraints for the shortest path problem (cf. Appendix C). ex1 in Section 5.2
helps get a better sense of how the graph $G_{i}(v)$ is constructed and
involved with the payment rule. Further examples are provided in Appendix B.

###  5.1 Correctness

The following lemma guarantees that ShortestDistance successfully computes the
shortest distances in the graph $G_{i}(v)$.

######  Lemma 3.

lem:no-neg-cyc For any $v\in\mathcal{V}$ and $i\in\mathcal{N}$, the weighted
directed graph $G_{i}(v)$ has no negative directed cycle.

###### Proof.

Fix an arbitrary pair of $i\in\mathcal{N}$ and $v\in\mathcal{V}$ for which we
are going to show the claim holds. Note that no directed cycle contains the
auxiliary vertex $\star$, since no edge comes out from it. Consider an
arbitrary sequence $v_{i}^{(1)},\ldots,v_{i}^{(k)}$ in $\mathcal{V}_{i}$, and
let $v_{i}^{(0)}\coloneqq v_{i}^{(k)}$. Let also
$v^{(\ell)}\coloneqq(v_{i}^{(\ell)},v_{-i}),\forall\ell\in\\{0,1,\ldots,k\\}$.
By definition of SelectOption, it follows that

$\displaystyle
v_{i}^{(\ell)}(\phi^{*}(v^{(\ell)}))+\sum_{j\in\mathcal{N}\setminus\\{i\\}}v_{j}(\phi^{*}(v^{(\ell)}))=S(\phi^{*}(v^{(\ell)});v^{(\ell)})$
$\displaystyle\geq
S(\phi^{*}(v^{(\ell-1)});v^{(\ell)})=v_{i}^{(\ell)}(\phi^{*}(v^{(\ell-1)}))+\sum_{j\in\mathcal{N}\setminus\\{i\\}}v_{j}(\phi^{*}(v^{(\ell-1)})),$
$\displaystyle\forall\ell\in\\{1,\ldots,k\\}.$ (13)

Summing up (13) over all $\ell\in\\{1,\ldots,k\\}$ yields

$\displaystyle\sum_{\ell=1}^{k}(v_{i}^{(\ell)}(\phi^{*}(v^{(\ell)}))-v_{i}^{(\ell)}(\phi^{*}(v^{(\ell-1)})))$
$\displaystyle\geq\sum_{\ell=1}^{k}\left(\sum_{j\in\mathcal{N}\setminus\\{i\\}}v_{j}(\phi^{*}(v^{(\ell-1)}))-\sum_{j\in\mathcal{N}\setminus\\{i\\}}v_{j}(\phi^{*}(v^{(\ell)}))\right)=0,$
(14)

where the last equality follows from $v^{(0)}=v^{(k)}$ by definition. Eq. (14)
implies that the sum of the edge weights along any directed cycle in
$G_{i}(v)$ is not negative. ∎

By virtue of lem:no-neg-cyc, $-\tau^{*}_{i}(v)$ is successfully set to the
shortest distance from $\star$ to $v_{i}$ in the graph $G_{i}(v)$. Confirm
that $G_{i}(v)$ does not depend on $i$’s own type $v_{i}$ by definition i.e.,

$\displaystyle G_{i}(v)=G_{i}(v_{i}^{\prime},v_{-i}),\quad\forall
i\in\mathcal{N},\forall v\in\mathcal{V},\forall
v_{i}^{\prime}\in\mathcal{V}_{i}.$ (15)

Hence, $-\tau_{i}^{*}(v)$ and $-\tau_{i}^{*}(v_{i}^{\prime},v_{-i})$ are
obtained from the shortest paths on the same graph. Therefore, the following
inequalities hold by definition:

$\displaystyle-\tau^{*}_{i}(v)$
$\displaystyle\leq-\tau^{*}_{i}(v_{i}^{\prime},v_{-i})+v_{i}(\phi^{*}(v))-v_{i}(\phi^{*}(v_{i}^{\prime},v_{-i})),$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V},\forall
v_{i}^{\prime}\in\mathcal{V}_{i},$ (16)

which is equivalent to DSIC (4), and

$\displaystyle-\tau_{i}(v)$ $\displaystyle\leq v_{i}(\phi^{*}(v)),$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V},$ (17)

which is equivalent to IR (5). Since $\phi^{*}$ satisfies SE (1) by
definition, we obtain thm:justified below.

######  Theorem 3.

thm:justified The proposed mechanism $\mathcal{M}^{*}$ is justified.

###  5.2 Optimality

thm:maximal claims that our mechanism $\mathcal{M}^{*}=(\phi^{*},\tau^{*})$
achieves the minimum budget among all justified mechanisms built with the same
option rule $\phi^{*}$.

######  Theorem 4.

thm:maximal The proposed mechanism $\mathcal{M}^{*}$ satisfies, against any
justified mechanism $\mathcal{M}=(\phi^{*},\tau)$,

$\displaystyle\tau^{*}_{i}(v)$ $\displaystyle\leq\tau_{i}(v),$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V},$ (18)
$\displaystyle B(v;\mathcal{M}^{*})$ $\displaystyle\leq B(v;\mathcal{M}),$
$\displaystyle\forall v\in\mathcal{V}.$ (19)

###### Proof.

Fix an arbitrary pair of $i\in\mathcal{N}$ and $v\in\mathcal{V}$ for which we
will show (18). Now let a sequence of vertices
$(\star,v_{i}^{(0)},v_{i}^{(1)},\ldots,v_{i}^{(k)}\coloneqq v_{i})$ in the
graph $G_{i}(v)$ be one of the shortest paths from the source $\star$ to the
destination $v_{i}$. Again let
$v^{(\ell)}\coloneqq(v_{i}^{(\ell)},v_{-i}),\forall\ell\in\\{0,1,\ldots,k\\}$.
Since the vertex $v_{i}^{(0)}$ is visited right after the source $\star$ along
the shortest path, we have

$\displaystyle-\tau^{*}_{i}(v^{(0)})=v_{i}^{(0)}(\phi^{*}(v^{(0)})).$ (20)

Similarly, since the vertex $v_{i}^{(\ell)}$ follows right after
$v_{i}^{(\ell-1)}$ along the shortest path, we obtain

$\displaystyle-\tau^{*}_{i}(v^{(\ell)})-(-\tau^{*}_{i}(v^{(\ell-1)}))$
$\displaystyle=v_{i}^{(\ell)}(\phi^{*}(v^{(\ell)}))-v_{i}^{(\ell)}(\phi^{*}(v^{(\ell-1)})),\quad\forall\ell\in\\{1,\ldots,k\\}.$
(21)

Then (20) and (21) add up to

$\displaystyle-\tau^{*}_{i}(v^{(k)})=v_{i}^{(0)}(\phi^{*}(v^{(0)}))+\sum_{\ell=1}^{k}(v_{i}^{(\ell)}(\phi^{*}(v^{(\ell)}))-v_{i}^{(\ell)}(\phi^{*}(v^{(\ell-1)}))).$
(22)

Next, let $\mathcal{M}=(\phi^{*},\tau)$ be any justified mechanism. Then it
follows from DSIC (4) that

$\displaystyle-\tau_{i}(v^{(\ell)})-(-\tau_{i}(v^{(\ell-1)}))$
$\displaystyle\leq
v_{i}^{(\ell)}(\phi^{*}(v^{(\ell)}))-v_{i}^{(\ell)}(\phi^{*}(v^{(\ell-1)})),\quad\forall\ell\in\\{1,\ldots,k\\},$
(23)

and from IR (5) that

$\displaystyle-\tau_{i}(v^{(0)})$ $\displaystyle\leq
v_{i}^{(0)}(\phi^{*}(v^{(0)})),$ (24)

which are tied together into

$\displaystyle-\tau_{i}(v^{(k)})\leq
v_{i}^{(0)}(\phi^{*}(v^{(0)}))+\sum_{\ell=1}^{k}(v_{i}^{(\ell)}(\phi^{*}(v^{(\ell)}))-v_{i}^{(\ell)}(\phi^{*}(v^{(\ell-1)}))).$
(25)

Finally, the desired inequality (18) follows from (22) and (25) since
$v^{(k)}=v$, and then (18) adds up over $\mathcal{N}$ to (19). ∎

When there is only one option rule that is SE, the proposed mechanism indeed
minimizes the budget among all justified mechanisms, as is formally stated in
the following corollary:

######  Corollary 1.

cor:rev In “proper” environments, where the social welfare $S(X;v)$ is
maximized by a unique option $X\in\mathcal{X}$ for each $v\in\mathcal{V}$, the
proposed mechanism $\mathcal{M}^{*}$ achieves the minimum budget
$B(v;\mathcal{M})$ that can be obtained by any justified mechanism
$\mathcal{M}$. Formally, we claim the following:

$\displaystyle\left|\mathop{\rm
argmax}\limits_{X\in\mathcal{X}}S(X;v)\right|=1,\ \forall
v\in\mathcal{V}\quad\Rightarrow\quad
B(v;\mathcal{M}^{*})=\min_{\mathcal{M}:\,\mathrm{justified}}B(v;\mathcal{M}),\
\forall v\in\mathcal{V}.$ (26)

When multiple option rules satisfy SE, the budget required by the proposed
mechanism may vary depending on which option rule is used, even though it is
minimized for any given option rule.

######  Example 1 (Improper environment).

ex1 This example provides an improper environment where the proposed mechanism
may fail to globally minimize the budget for lack of the assumption in
cor:rev. Let us consider an environment with two agents
$\mathcal{N}\coloneqq\\{A,B\\}$, three options
$\mathcal{X}\coloneqq\\{X_{1},X_{2},X_{3}\\}$, and type domains
$\mathcal{V}_{A}$ and $\mathcal{V}_{B}$ described in Table 1.

We configure the option rule $\phi^{*}$ such that

$\displaystyle\phi^{*}(v_{A}^{(1)},v_{B})\in\mathop{\rm
argmax}\limits_{X\in\mathcal{X}}(v_{A}^{(1)}(X)+v_{B}(X))$
$\displaystyle=\\{X_{1}\\},$ (27)
$\displaystyle\phi^{*}(v_{A}^{(2)},v_{B})\in\mathop{\rm
argmax}\limits_{X\in\mathcal{X}}(v_{A}^{(2)}(X)+v_{B}(X))$
$\displaystyle=\\{X_{2},X_{3}\\}.$ (28)

If $X_{2}$ is selected for $\phi^{*}(v_{A}^{(2)},v_{B})$ in (28), then the
payments on the types $v\coloneqq(v_{A}^{(1)},v_{B})$ would be

$\displaystyle\tau^{*}_{A}(v)=\alpha,\quad\tau^{*}_{B}(v)=0,$ (29)

which are computed as shortest distances in the graph shown in Figure
1LABEL:sub@fig:ex1:case1. Otherwise, if $X_{3}$ is selected as
$\phi^{*}(v_{A}^{(2)},v_{B})$ in (28), then the graph in Figure
1LABEL:sub@fig:ex1:case2 would tell

$\displaystyle\tau^{*}_{A}(v)=-\alpha,\quad\tau^{*}_{B}(v)=0.$ (30)

Therefore, given the types $v$, the proposed mechanism might end up with the
budget $B(v;\mathcal{M}^{*})=\tau^{*}_{A}(v)+\tau^{*}_{B}(v)=\alpha$ due to
(29), which is higher than otherwise possible budget of $-\alpha$ in the case
of (30). Under this environment, expense to guarantee DSIC (4) is intuitively
attributed to difference in valuation between agent A’s two possible types
$\mathcal{V}_{A}=\\{v_{A}^{(1)},v_{A}^{(2)}\\}$, which could be larger with
the option $X_{2}$ than with $X_{3}$.

Table 1: An improper environment parameterized with $\alpha>0$. Agent $A$ can have one of two types $\mathcal{V}_{A}\coloneqq\\{v_{A}^{(1)},v_{A}^{(2)}\\}$, while agent $B$ has only one possible type $\mathcal{V}_{B}\coloneqq\\{v_{B}\\}$.  Type | Option
---|---
$X_{1}$ | $X_{2}$ | $X_{3}$
$v_{A}^{(1)}$ | $\alpha$ | $0$ | $0$
$v_{A}^{(2)}$ | $-3\alpha$ | $-2\alpha$ | $0$
$v_{B}$ | $0$ | $0$ | $-2\alpha$

$\star$$v_{A}^{(1)}$$v_{A}^{(2)}$$v_{B}$$0$$\alpha$$-2\alpha$$\alpha$$\alpha$$G_{A}$$G_{B}$

(a) $\phi^{*}(v_{A}^{(2)},v_{B})=X_{2}$.

$\star$$v_{A}^{(1)}$$v_{A}^{(2)}$$v_{B}$$0$$\alpha$$0$$3\alpha$$\alpha$$G_{A}$$G_{B}$

(b) $\phi^{*}(v_{A}^{(2)},v_{B})=X_{3}$.

Figure 1: The weighted graph $G_{A}(v)$ and $G_{B}(v)$ for the type
$v=(v_{A}^{(1)},v_{B})$, combined at the auxiliary vertex $\star$, for the two
possibilities of (LABEL:sub@fig:ex1:case1) and (LABEL:sub@fig:ex1:case2).

For such improper environments, the following corollary, which we prove in
Appendix A, suggests that we may search for an option rule among the ones that
satisfy SE (1) that optimizes some aggregated metric based on the budgets
$B(v;\mathcal{M})$ across types $v\in\mathcal{V}$:

######  Corollary 2.

cor:nonproper Let $\Phi^{*}$ be the set of all option rules that satisfies SE
(1). Let $\mathcal{M}^{*}[\phi^{*}]$ be the proposed mechanism (Algorithm 1)
built with an option rule $\phi^{*}\in\Phi$. Then, for any non-decreasing
function $f:\mathbb{R}^{\mathcal{V}}\to\mathbb{R}$, we have

$\displaystyle\min_{\phi^{*}\in\Phi^{*}}f((B(v;\mathcal{M}^{*}[\phi^{*}]))_{v\in\mathcal{V}})$
$\displaystyle=\min_{\mathcal{M}:\,\mathrm{justified}}f((B(v;\mathcal{M}))_{v\in\mathcal{V}}).$
(31)

For example, one may let
$f((B(v;\mathcal{M}))_{v\in\mathcal{V}})=\mathbb{E}[B(v;\mathcal{V})]$, where
$\mathbb{E}$ denotes the expectation with respect to an arbitrarily assumed
probability distribution over $\mathcal{V}$, and choose an option rule
$\phi^{*}$ that allows the mechanism $\mathcal{M}^{*}[\phi^{*}]$ to minimize
the expected budget.

###  5.3 Computational complexity

The running time of the proposed mechanism can depend on the size of the
environment as well as the running time of the subroutines such as
SelectOption and ShortestDistance. The following theorem formally
characterizes the computational complexity of the proposed mechanism and
provides a way to reduce the complexity when only a limited number of options
can be selected.

######  Theorem 5.

thm:time ComputePayments runs in $\displaystyle
O\left(\sum_{i\in\mathcal{N}}(|\mathcal{V}_{i}|T_{opt}+|\mathcal{V}_{i}|^{2}T_{eval}+\mathrm{SP}(|\mathcal{V}_{i}|,|\mathcal{V}_{i}|^{2}))\right)$
time, where $T_{opt}$ denotes the worst time complexity of SelectOption,
$T_{eval}$ denotes that of evaluating any single value $v_{i}(X),\forall
v_{i}\in\mathcal{V}_{i},\forall i\in\mathcal{N},\forall X\in\mathcal{X}$, and
$\mathrm{SP}(n,m)$ denotes that of the oracle ShortestDistance given a graph
with $n$ vertices and $m$ edges. Furthermore, a modified implementation
reduces the complexity to $\displaystyle
O\left(\sum_{i\in\mathcal{N}}(|\mathcal{V}_{i}|T_{opt}+n_{i}|\mathcal{V}_{i}|T_{eval}+\mathrm{SP}(n_{i},n_{i}^{2}))\right)$,
with
$n_{i}\coloneqq\displaystyle\max_{v_{-i}\in\mathcal{V}_{-i}}|\\{\phi^{*}(v_{i}^{\prime},v_{-i})\mid
v_{i}^{\prime}\in\mathcal{V}_{i}\\}|,\forall i\in\mathcal{N}$.

###### Proof.

For each $i\in\mathcal{N}$, the first term denotes the complexity of
SelectOption called $|\mathcal{V}_{i}|$ times, followed by the complexity of
computing $|\mathcal{V}_{i}|^{2}+|\mathcal{V}_{i}|$ edge weights, and finally
by the complexity of the oracle ShortestDistance given the graph $G_{i}(v)$.

The improved complexity is obtained by summarizing $G_{i}(v)$ into a smaller
graph $\tilde{G}_{i}(v)$ of at most $n_{i}+1$ vertices,
$\mathcal{X}_{i}(v_{-i})\cup\\{\tilde{\star}\\}$, where we define

$\displaystyle\mathcal{X}_{i}(v_{-i})$
$\displaystyle\coloneqq\\{\phi^{*}(v_{i}^{\prime},v_{-i})\mid
v_{i}^{\prime}\in\mathcal{V}_{i}\\}\subseteq\mathcal{X},$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V}.$ (32)

The graph $\tilde{G}_{i}(v)$ is equipped with directed edges for all pairs in
$(\mathcal{X}_{i}(v_{-i})\cup\\{\tilde{\star}\\})\times\mathcal{X}_{i}(v_{-i})$,
whose weights $\tilde{c}$ are defined as follows:

$\displaystyle\tilde{c}(\tilde{\star},\Phi)$
$\displaystyle\coloneqq\min\\{v_{i}^{\prime}(\Phi)\mid
v_{i}^{\prime}\in\mathcal{V}_{i},\ \phi^{*}(v_{i}^{\prime},v_{-i})=\Phi\\},$
$\displaystyle\forall\Phi\in\mathcal{X}_{i}(v_{-i}),$ (33)
$\displaystyle\tilde{c}(\Phi_{1},\Phi_{2})$
$\displaystyle\coloneqq\min\\{v_{i}^{\prime}(\Phi_{2})-v_{i}^{\prime}(\Phi_{1})\mid
v_{i}^{\prime}\in\mathcal{V}_{i},\
\phi^{*}(v_{i}^{\prime},v_{-i})=\Phi_{2}\\},$
$\displaystyle\forall(\Phi_{1},\Phi_{2})\in\mathcal{X}_{i}(v_{-i})^{2}.$ (34)

From another viewpoint, the graph $\tilde{G}_{i}(v)$ is obtained from
$G_{i}(v)$ by contracting vertices $v_{i}^{\prime}\in\mathcal{V}_{i}$ with the
same option $\phi^{*}(v_{i}^{\prime},v_{-i})\in\mathcal{X}_{i}(v_{-i})$ into a
single vertex labeled with it, while resulting parallel edges in $G_{i}(v)$
are replaced by an aggregated single edge in $\tilde{G}_{i}(v)$ with the
minimum weight among those of the original edges. The desired shortest
distance $-\tau^{*}_{i}(v)$ in $G_{i}(v)$ from $\star$ to $v_{i}$ remains as
the shortest distance in $\tilde{G}_{i}(v)$ from $\tilde{\star}$ to
$\phi^{*}(v)$, because in the original graph $G_{i}(v)$, vertices
$v_{i}^{\prime}\in\mathcal{V}_{i}$ with a common
$\phi^{*}(v_{i}^{\prime},v_{-i})$ are mutually and bidirectionally connected
by zero-weight edges, and thus share an equal shortest distance from $\star$.
∎

Note $n_{i}\leq\min\\{|\mathcal{V}_{i}|,|\mathcal{X}|\\},\forall
i\in\mathcal{N}$ and that $\mathrm{SP}(n,m)=O(nm)$ is guaranteed as the
current best bound by the Bellman-Ford algorithm [23]. The present mechanism
is thus executed in polynomial time with respect to the size of the type
domains $|\mathcal{V}_{i}|$. However, if the number of options $|\mathcal{X}|$
is large compared with $|\mathcal{V}_{i}|$, or even infinite, then $T_{opt}$
would potentially become an intractable bottleneck. In such cases, one may
preferably leverage some analytical properties about types (e.g., concavity)
for specific environments. The above proof of thm:time also implies the
following space complexity.

######  Corollary 3.

cor:space ComputePayments requires $\displaystyle
O\left(S_{opt}+S_{eval}+\max_{i\in\mathcal{N}}|\mathcal{V}_{i}|^{2}\right)$
space, where $S_{opt}$ denotes the worst space complexity of SelectOption and
$S_{eval}$ denotes that of evaluating any single value $v_{i}(X),\forall
v_{i}\in\mathcal{V}_{i},\forall i\in\mathcal{N},\forall X\in\mathcal{X}$.
Furthermore, the complexity can be reduced to $\displaystyle
O\left(S_{opt}+S_{eval}+\max_{i\in\mathcal{N}}n_{i}^{2}\right)$, with
$n_{i}\coloneqq\displaystyle\max_{v_{-i}\in\mathcal{V}_{-i}}|\\{\phi(v_{i}^{\prime},v_{-i})\mid
v_{i}^{\prime}\in\mathcal{V}_{i}\\}|,\forall i\in\mathcal{N}$.

##  6 Numerical experiments

Here we empirically investigate the quantitative performance of the proposed
mechanism in terms of minimizing the budget. thm:VCG-budget_opt in Section 4
confirms that VCG-budget (def:VCG-budget) is optimal among justified VCG
mechanisms, which motivates us to compare the proposed mechanism with VCG-
budget as a representative of all justified VCG mechanisms. The experiments
are thus focused on whether and how often the proposed mechanism achieves
strictly lower budget than VCG-budget.

Every instance is generated as a pair of an environment
$\mathcal{E}=(\mathcal{N},\mathcal{X},\mathcal{V})$ and a list of types
$v\in\mathcal{V}$ for which the mechanisms are executed. The size of the
environment $\mathcal{E}$ is parametrized by the number of agents
$|\mathcal{N}|\in\\{1,2,\ldots,32\\}$, the number of options
$|\mathcal{X}|\in\\{1,2,\ldots,256\\}$, and the size of type domains
$|\mathcal{V}_{i}|\in\\{1,2,\ldots,16\\},\forall i\in\mathcal{N}$, each of
which is either specified or randomly drawn when the instance is generated.
Then each value $v_{i}(X)$ is drawn independently and identically from the
discrete uniform distribution over the set of consecutive integers from $-100$
to $100$. Now that the environment $\mathcal{E}$ is configured, the list of
types $v$ is finally chosen from the uniform distribution over
$\mathcal{V}=\prod_{i\in\mathcal{N}}\mathcal{V}_{i}$. Both VCG-budget and the
proposed mechanism use a common option rule for each environment. It is
confirmed that either mechanism runs within one second at worst per instance
on a laptop with no GPU, a single Intel Core i7-11850H @ 2.50GHz, and 64GB
RAM.

Figure 2(a) shows the histogram of the difference in the budget required by
the proposed mechanism relative to VCG-budget. Here, we only show the results
with $|\mathcal{N}|=16$ (see Appendix E for other results). The right-most bar
corresponds to the cases where the VCG-budget is also optimal (difference to
the proposed mechanism is zero). It can thus be observed that the proposed
mechanism requires strictly lower budget for 88.3% of the cases in this
setting. While the exact frequency varies depending on the settings, we find
that the proposed mechanism generally achieves strictly lower budget than VCG-
budget for a large fraction of the instances (see also Appendix E).

(a) $|\mathcal{N}|=16$

(b) $1\leq|\mathcal{N}|\leq 32$

(c) $1\leq|\mathcal{X}|\leq 256$

(d) $1\leq|\mathcal{V}_{i}|\leq 16$

Figure 2:  Difference in budget required by the proposed mechanism relative to
VCG-budget, shown as a histogram in (LABEL:sub@fig:exp:hist) as well as the
average against the number of agents $|\mathcal{N}|$ in
(LABEL:sub@fig:exp:plot_vs_n), the number of options $|\mathcal{X}|$ in
(LABEL:sub@fig:exp:plot_vs_m), and the size of type domains
$|\mathcal{V}_{i}|$ in (LABEL:sub@fig:exp:plot_vs_d), where $|\mathcal{N}|=16$
is fixed except in (LABEL:sub@fig:exp:plot_vs_n).

Figure 2(b)-2(d) shows the average difference in the budget when we vary the
number of agents $|\mathcal{N}|$ in (LABEL:sub@fig:exp:plot_vs_n), the number
of options $|\mathcal{X}|$ in (LABEL:sub@fig:exp:plot_vs_m), and the size of
type domain $|\mathcal{V}_{i}|$ in (LABEL:sub@fig:exp:plot_vs_d). Each data
point is the average over 1,000 random instances, and the error bars show
standard deviation. Overall, the proposed mechanism requires significantly
lower budget than VCG-budget for all cases except when $|\mathcal{N}|$,
$|\mathcal{X}|$, or $|\mathcal{V}_{i}|$ is close to one. In this setting, the
relative benefit of the proposed mechanism tends to increase with
$|\mathcal{N}|$ and $|\mathcal{X}|$, but the proposed mechanism gives the
largest improvement at intermediate values of $|\mathcal{V}_{i}|$. See
Appendix E for the results with other settings.

##  7 Conclusion

The present study has identified the budget-optimal mechanism among all the
mechanisms that satisfies SE, DSIC, and IR in a constructive way coupled with
theoretical evaluations. Moreover, through numerical experiments, the proposed
mechanism has proved itself beyond the VCG family and demonstrated strictly
lower budget than any VCG mechanism for a majority of instances. However,
there are limitations to the type domains to which this study can be applied,
and future studies are open around the extension of our approach to continuous
and/or unknown type domains, where it would be impossible to enumerate the set
of inequalities required by DSIC (4) and IR (5).

As we discuss in Appendix D, the proposed mechanism can be extended to work
with the option rule that is an affine maximizer instead of a (unweighted)
social-welfare maximizer. This extended mechanism can minimize the budget
among all the mechanisms that maximize the weighted sum of the agents’
valuations _for given weights_ while satisfying DSIC and IR. It is an
interesting direction of future work to leverage this extended mechanism for
the purpose of maximizing the revenue by optimizing the weights similar to the
affine maximizer auction.

## References

  * [1] Martin J. Bailey.  The demand revealing process: To distribute the surplus.  Public Choice, 91(2):107–126, 1997.
  * [2] Ruggiero Cavallo.  Optimal decision-making with minimal waste: Strategyproof redistribution of VCG payments.  In Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS ’06, pages 882–889, New York, NY, USA, 2006. Association for Computing Machinery.
  * [3] Sergei Chichin, Quoc Bao Vo, and Ryszard Kowalczyk.  Towards efficient and truthful market mechanisms for double-sided cloud markets.  IEEE Transactions on Services Computing, 10(1):37–51, 2017.
  * [4] Robert A. Collinge.  A Creation of Markets for Market Power, Spillovers, and Public Goods.  PhD thesis, University of Maryland, 1983.
  * [5] Michael Curry, Vinzenz Thoma, Darshan Chakrabarti, Stephen McAleer, Christian Kroer, Tuomas Sandholm, Niao He, and Sven Seuken.  Automated design of affine maximizer mechanisms in dynamic settings, 2024\.
  * [6] Zhijian Duan, Haoran Sun, Yurong Chen, and Xiaotie Deng.  A scalable neural network for dsic affine maximizer auction design.  In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 56169–56185. Curran Associates, Inc., 2023.
  * [7] Lachlan Dufton, Victor Naroditskiy, Maria Polukarov, and Nicholas Jennings.  Optimizing payments in dominant-strategy mechanisms for multi-parameter domains.  Proceedings of the AAAI Conference on Artificial Intelligence, 26(1):1347–1354, Sep. 2021.
  * [8] Jerry R. Green and Jean J. Laffont.  Characterization of satisfactory mechanisms for the revelation of preferences for public goods.  Econometrica, 45:427–438, 1977.
  * [9] Jerry R. Green and Jean J. Laffont.  Incentives in public decision-making.  Elsevier North-Holland, 1979.
  * [10] Theodore Groves and John Ledyard.  Some limitations of demand revelaing processes.  Public Choice, 29:107–124, 03 1977.
  * [11] Sujit Gujar and Y. Narahari.  Redistribution mechanisms for assignment of heterogeneous objects.  J. Artif. Int. Res., 41(2):131–154, may 2011.
  * [12] Mingyu Guo.  VCG redistribution with gross substitutes.  Proceedings of the AAAI Conference on Artificial Intelligence, 25(1):675–680, Aug. 2011.
  * [13] Mingyu Guo.  Worst-case optimal redistribution of VCG payments in heterogeneous-item auctions with unit demand.  In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2, AAMAS ’12, pages 745–752, Richland, SC, 2012. International Foundation for Autonomous Agents and Multiagent Systems.
  * [14] Mingyu Guo and Vincent Conitzer.  Worst-case optimal redistribution of VCG payments.  In Proceedings of the 8th ACM Conference on Electronic Commerce, EC ’07, pages 30–39, New York, NY, USA, 2007. Association for Computing Machinery.
  * [15] Mingyu Guo and Vincent Conitzer.  Worst-case optimal redistribution of VCG payments in multi-unit auctions.  Games and Economic Behavior, 67(1):69–98, 2009.  Special Section of Games and Economic Behavior Dedicated to the 8th ACM Conference on Electronic Commerce.
  * [16] Mingyu Guo, Hideaki Hata, and Muhammad Ali Babar.  Optimizing affine maximizer auctions via linear programming: An application to revenue maximizing mechanism design for zero-day exploits markets.  In Prima, 2017.
  * [17] Chunxiao Jiang, Yan Chen, Qi Wang, and K.J. Ray Liu.  Data-driven auction mechanism design in iaas cloud computing.  IEEE Transactions on Services Computing, 11(5):743–756, 2018.
  * [18] Bernhard Korte and Jens Vygen.  Combinatorial Optimization: Theory and Algorithms.  Springer Publishing Company, Incorporated, 6th edition, 2018.
  * [19] Dinesh Kumar, Gaurav Baranwal, Zahid Raza, and Deo Prakash Vidyarthi.  A truthful combinatorial double auction-based marketplace mechanism for cloud computing.  Journal of Systems and Software, 140:91–108, 2018.
  * [20] Ron Lavi, Ahuva Mu’alem, and Noam Nisan.  Towards a characterization of truthful combinatorial auctions.  In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’03, page 574, USA, 2003. IEEE Computer Society.
  * [21] Anton Likhodedov and Tuomas Sandholm.  Methods for boosting revenue in combinatorial auctions.  In Proceedings of the 19th National Conference on Artifical Intelligence, AAAI’04, pages 232–237. AAAI Press, 2004.
  * [22] Anton Likhodedov and Tuomas Sandholm.  Approximating revenue-maximizing combinatorial auctions.  In AAAI Conference on Artificial Intelligence, 2005.
  * [23] Amgad Madkour, Walid G. Aref, Faizan ur Rehman, Mohamed Abdur Rahman, and Saleh M. Basalamah.  A survey of shortest-path algorithms.  arXiv, 1705.02044, 2017.
  * [24] Padala Manisha, C. V. Jawahar, and Sujit Gujar.  Learning optimal redistribution mechanisms through neural networks.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 345–353, July 2018.
  * [25] Roger B. Myerson and Mark A. Satterthwaite.  Efficient mechanisms for bilateral trading.  Journal of Economic Theory, 29(2):265–281, 1983.
  * [26] Victor Naroditskiy, Maria Polukarov, and Nicholas R. Jennings.  Optimal payments in dominant-strategy mechanisms for single-parameter domains.  ACM Trans. Econ. Comput., 1(1), jan 2013.
  * [27] Swaprava Nath and Tuomas Sandholm.  Efficiency and Budget Balance, pages 369–383.  Web and Internet Economics. Springer Berlin Heidelberg, Berlin, Heidelberg, 2016.
  * [28] Noam Nisan.  Introduction to mechanism design (for computer scientists).  In Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors, Algorithmic Game Theory, pages 209–242. Cambridge University Press, 2007.
  * [29] Takayuki Osogami, Segev Wasserkrug, and Elisheva S. Shamash.  Learning efficient truthful mechanisms for trading networks.  In Edith Elkind, editor, Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pages 2862–2869. International Joint Conferences on Artificial Intelligence Organization, 8 2023.  Main Track.
  * [30] Abraham Othman and Tuomas Sandholm.  How pervasive is the myerson-satterthwaite impossibility?  In Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI’09, pages 233–238, San Francisco, CA, USA, 2009\. Morgan Kaufmann Publishers Inc.
  * [31] Rafael Rob.  Asymptotic efficiency of the demand revealing mechanism.  Journal of Economic Theory, 28(2):207–220, 1982.
  * [32] Kevin W. S. Roberts.  The characterization of implementable choice rules.  In Jean-Jacques M. Laffont, editor, Aggregation and revelation of preferences, pages 321–349. North-holland, 1979.
  * [33] Tuomas Sandholm and Anton Likhodedov.  Automated design of revenue-maximizing combinatorial auctions.  Oper. Res., 63:1000–1025, 2015.
  * [34] Urs Schweizer.  Universal possibility and impossibility results.  Games and Economic Behavior, 57(1):73–85, 2006.
  * [35] Andrea Tacchetti, DJ Strouse, Marta Garnelo, Thore Graepel, and Yoram Bachrach.  Learning truthful, efficient, and welfare maximizing auction rules.  In ICLR 2022 Workshop on Gamification and Multiagent Solutions, 2022\.
  * [36] T. Nicolaus Tideman and Gordon Tullock.  A new and superior process for making social choices.  Journal of Political Economy, 84:1145 – 1159, 1976.
  * [37] T. Nicolaus Tideman and Gordon Tullock.  Some limitations of demand revealing processes: Comment.  Public choice, 29(S2):125–128, 1977.
  * [38] William Vickrey.  Counterspeculation, auctions, and competitive sealed tenders.  The Journal of Finance, 16(1):8–37, 1961.
  * [39] Chaolun Xia and Shan Muthukrishnan.  Revenue-maximizing stable pricing in online labor markets.  Proceedings of the AAAI Conference on Human Computation and Crowdsourcing, 5(1):216–225, Sep. 2017.
  * [40] Yufeng Zhan, Jie Zhang, Zicong Hong, Leijie Wu, Peng Li, and Song Guo.  A survey of incentive mechanism design for federated learning.  IEEE Transactions on Emerging Topics in Computing, 10(2):1035–1044, 2022.

##  Appendix A Proofs

Here, we provide full proofs for the theorems, lemmas, and corollaries whose
proofs are omitted in the body of the paper.

###### Proof of thm:VCG_DSIC.

Let $\mathcal{M}=(\phi,\tau)$ be the VCG mechanism implemented with any
$(h_{i})_{i\in\mathcal{N}}$. Then

$\displaystyle u_{i}(v;\mathcal{M})$
$\displaystyle=v_{i}(\phi(v))+\tau_{i}(v)$
$\displaystyle=S(\phi(v);v)-h_{i}(v_{-i})$ $\displaystyle\geq
S(\phi(v_{i}^{\prime},v_{-i});v)-h_{i}(v_{-i})$
$\displaystyle=v_{i}(\phi(v_{i}^{\prime},v_{-i}))+\sum_{j\in\mathcal{N}\setminus\\{i\\}}v_{j}(\phi(v_{i}^{\prime},v_{-i}))-h_{i}(v_{-i})$
$\displaystyle=v_{i}(\phi(v_{i}^{\prime},v_{-i}))+\tau_{i}(\phi(v_{i}^{\prime},v_{-i})),$
$\displaystyle\forall v_{i}\in\mathcal{V}_{i},\forall i\in\mathcal{N},\forall
v\in\mathcal{V},$ (35)

completes the proof. ∎

###### Proof of lem:VCG_IR.

The first claim (8) follows by definition:

$\displaystyle\tau^{c}_{i}(v)$
$\displaystyle=\sum_{j\in\mathcal{N}\setminus\\{i\\}}v_{j}(\phi(v))-\max_{X\in\mathcal{X}}\sum_{j\in\mathcal{N}\setminus\\{i\\}}v_{j}(X)\leq
0,$ $\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V}.$ (36)

It is also observed that

$\displaystyle u_{i}(v;\mathcal{M})$
$\displaystyle=v_{i}(\phi(v))+\tau^{c}_{i}(v)$
$\displaystyle=S(\phi(v);v)-h^{c}_{i}(v_{-i})$
$\displaystyle=\max_{X\in\mathcal{X}}\sum_{j\in\mathcal{N}}v_{j}(X)-\max_{X\in\mathcal{X}}\sum_{j\in\mathcal{N}\setminus\\{i\\}}v_{j}(X)\geq\inf_{X\in\mathcal{X}}v_{i}(X),$
$\displaystyle\forall i\in\mathcal{N},v\in\mathcal{V},$ (37)

which yields IR (5) when (9) holds. ∎

###### Proof of lem:VCG-budget_IR.

VCG-budget $\mathcal{M}^{b}=(\phi,\tau^{b})$ satisfies the following:

$\displaystyle u_{i}(v;\mathcal{M}^{b})$
$\displaystyle=v_{i}(\phi(v))+\tau^{b}_{i}(v)$
$\displaystyle=S(\phi(v);v)-\min_{v_{i}^{\prime}\in\mathcal{V}_{i}}S(\phi(v_{i}^{\prime},v_{-i});v_{i}^{\prime},v_{-i})\geq
0,$ $\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V},$ (38)

which directly gives the claim. ∎

###### Proof of thm:VCG-budget_opt.

Let $\mathcal{M}=(\phi,\tau)$ be any justified VCG mechanism implemented with
$(h_{i})_{i\in\mathcal{N}}$. Then IR gives

$\displaystyle 0\leq u_{i}(v_{i}^{\prime},v_{-i};\mathcal{M})$
$\displaystyle=v_{i}^{\prime}(\phi(v_{i}^{\prime},v_{-i}))+\tau_{i}(v_{i}^{\prime},v_{-i})$
$\displaystyle=S(\phi(v_{i}^{\prime},v_{-i});v_{i}^{\prime},v_{-i})-h_{i}(v_{-i}),$
$\displaystyle\forall v_{i}^{\prime}\in\mathcal{V}_{i},\forall
v_{-i}\in\mathcal{V}_{-i},\forall i\in\mathcal{N},$ (39)

or equivalently summarized with (10) into

$\displaystyle 0$ $\displaystyle\leq h^{b}_{i}(v_{-i})-h_{i}(v_{-i}),$
$\displaystyle\forall v_{-i}\in\mathcal{V}_{-i},\forall i\in\mathcal{N},$ (40)

which leads to (11) and in particular (12). ∎

###### Proof of cor:nonproper.

thm:maximal claims

$\displaystyle B(v;\mathcal{M}^{*}[\phi^{*}])$
$\displaystyle=\min_{(\phi^{*},\tau):\,\mathrm{justified}}B(v;(\phi^{*},\tau)),$
$\displaystyle\forall v\in\mathcal{V},\forall\phi^{*}\in\Phi^{*}.$ (41)

Since $f$ is non-decreasing, the previous equality implies

$\displaystyle f((B(v;\mathcal{M}^{*}[\phi^{*}]))_{v\in\mathcal{V}})$
$\displaystyle=f\left(\left(\min_{(\phi^{*},\tau):\,\mathrm{justified}}B(v;(\phi^{*},\tau))\right)_{v\in\mathcal{V}}\right)$
(42)
$\displaystyle\leq\min_{(\phi^{*},\tau):\,\mathrm{justified}}f((B(v;(\phi^{*},\tau)))_{v\in\mathcal{V}}),$
$\displaystyle\forall\phi^{*}\in\Phi^{*}.$ (43)

By taking the minimum of each side over $\Phi^{*}$, we obtain

$\displaystyle\min_{\phi^{*}\in\Phi^{*}}f((B(v;\mathcal{M}^{*}[\phi^{*}]))_{v\in\mathcal{V}})$
$\displaystyle\leq\min_{\phi^{*}\in\Phi^{*}}\min_{(\phi^{*},\tau):\,\mathrm{justified}}f((B(v;(\phi^{*},\tau)))_{v\in\mathcal{V}})$
(44)
$\displaystyle=\min_{\mathcal{M}:\,\mathrm{justified}}f((B(v;\mathcal{M}))_{v\in\mathcal{V}}).$
(45)

Since
$\\{\mathcal{M}^{*}[\phi^{*}]:\phi^{*}\in\Phi^{*}\\}\subseteq\\{\mathcal{M}:\mathrm{justified}\\}$,
we also have

$\displaystyle\min_{\phi^{*}\in\Phi^{*}}f((B(v;\mathcal{M}^{*}[\phi^{*}]))_{v\in\mathcal{V}})$
$\displaystyle\geq\min_{\mathcal{M}:\,\mathrm{justified}}f((B(v;\mathcal{M}))_{v\in\mathcal{V}}),$
(46)

which together with (45) establishes the corollary. ∎

##  Appendix B Supplementary examples

Examples in this section hopefully provide a clearer view of how the model and
the proposed mechanism are applied specifically.

######  Example 2 (Continuous options).

ex:continuous Let us consider, in a one-dimensional world, that the broker
plans to host an onsite event and invite limited guests there. Suppose that a
guest who lives at the location $b\in\mathbb{R}$ incurs a quadratic (physical
and/or monetary) cost of $a(x-b)^{2}+c$ for a round trip to the venue at
$x\in\mathbb{R}$ by some transportation characterized by the constants
$a\in\mathbb{R}_{>0}$ and $c\in\mathbb{R}$. The broker should locate the venue
so that the total cost of guests is minimized, while he also wants to expense
to the guests as little travel allowance as possible.

This situation can be formulated as an environment
$\mathcal{E}=(\mathcal{N},\mathcal{X},\mathcal{V})$ that consists of the
guests $\mathcal{N}$, a geographic range (closed interval) available for the
venue $\mathcal{X}\coloneqq[x_{min},x_{max}]\subseteq\mathbb{R}$, and type
domains $\mathcal{V}_{i}\coloneqq\left\\{v^{(k)}_{i}:\mathcal{X}\ni
x\mapsto-a^{(k)}_{i}\left(x-b^{(k)}_{i}\right)^{2}-c^{(k)}_{i}\in\mathbb{R}\mid
k\in\\{1,\ldots,d_{i}\\}\right\\}$ of size $d_{i}$ parameterized with
$(a^{(k)}_{i},b^{(k)}_{i},c^{(k)}_{i})_{k=1}^{d_{i}}\in(\mathbb{R}_{>0}\times\mathbb{R}\times\mathbb{R})^{d_{i}}$
for each $i\in\mathcal{N}$. Each guest $i\in\mathcal{N}$ reports his address
and transportation as a type $v_{i}\in\mathcal{V}_{i}$ and receive allowance
$\tau_{i}(v)$ from the broker, who does not want the guest to gain by false
declaration. Given any types
$v=(v^{(k_{i})}_{i})_{i\in\mathcal{N}}\in\mathcal{V}$, the social welfare is
equal to the negative total cost of agents:

$\displaystyle
S(x;v)=\sum_{i\in\mathcal{N}}\left(-a^{(k_{i})}_{i}\left(x-b^{(k_{i})}_{i}\right)^{2}-c^{(k_{i})}_{i}\right),$
(47)

which is maximized by the following unique option:

$\displaystyle
x=\phi^{*}(v)\coloneqq\max\left\\{x_{min},\min\left\\{x_{max},\dfrac{\sum_{i\in\mathcal{N}}a_{i}^{(k_{i})}b_{i}^{(k_{i})}}{\sum_{i\in\mathcal{N}}a_{i}^{(k_{i})}}\right\\}\right\\}.$
(48)

While the broker is obliged to maximize the social welfare (SE), he also has
to incentivize agents to make truthful reports (DSIC) and compensate each
agent $i$ with $\tau_{i}(v)$ at least $i$’s travel cost (IR), hopefully on the
minimum possible budget $\sum_{i\in\mathcal{N}}\tau_{i}(v)$. The proposed
mechanism perfectly succeeds along with it in this proper environment owing to
cor:rev.

######  Example 3 (Vickery auction).

ex:vickrey Here we consider an auction for a single indivisible item, for
which each agent makes a bid out of finite biddable prices. Formally, consider
an environment with $n$ agents $\mathcal{N}\coloneqq\\{1,\ldots,n\\}$ and the
same number of options $\mathcal{X}\coloneqq\\{X_{i}\mid i\in\mathcal{N}\\}$,
each of which $X_{i}\in\mathcal{X}$ represents the allocation where the item
goes to the agent $i\in\mathcal{N}$. Each agent $i\in\mathcal{N}$ has a type
domain $\mathcal{V}_{i}\coloneqq\\{v_{i}^{(1)},\ldots,v_{i}^{(d)}\\}$ of size
$d$ such that

$\displaystyle v_{i}^{(k)}(X_{j})=\begin{cases}p_{k}&\text{if }j=i,\\\
0&\text{otherwise,}\end{cases},$ $\displaystyle\forall
k\in\\{1,\ldots,d\\},\forall j\in\mathcal{N},\forall i\in\mathcal{N},$ (49)

where $p_{1}>p_{2}>\cdots>p_{d}>0$ are all biddable prices regardless of
agent.

Although it is an improper setting since multiple options maximize the social
welfare if more than one agent make the highest bids, we do not lose
generality by defining the option rule $\phi^{*}$ as follows. Given an
arbitrary list of types $v\in\mathcal{V}$, let us define $\phi^{*}(v)$ as
$X_{i}\in\mathop{\rm
argmax}\limits_{X\in\mathcal{X}}\sum_{i\in\mathcal{N}}v_{i}(X)$ with the
minimum $i\in\mathcal{N}$. In other words, tie-breaking among agents who bid
the highest is won by one with the smallest index.

Let $v=(v_{i_{\ell}}^{(k_{\ell})})_{\ell\in\mathcal{N}}\in\mathcal{V}$ be an
arbitrary list of types, where $(i_{\ell})_{\ell\in\mathcal{N}}$ is a
permutation of $\mathcal{N}$ that is sorted in the lexicographical order on
pairs $(k_{\ell},i_{\ell})$. The agent $i_{1}$ makes the highest bid of
$p_{k_{1}}$, followed by $i_{2}$, who makes an equal or less bid of
$p_{k_{2}}$. It follows from (49) and the definition of $\phi^{*}$ that
$\phi^{*}(v)=X_{i_{1}}$, which closes the auction with only $i_{1}$ making a
successful bid of $p_{k_{1}}$.

Now we focus on the payment $-\tau^{*}_{i_{1}}(v)$ from the winner $i_{1}$. It
is equal to the shortest distance from the auxiliary vertex $\star$ to the
vertex $v_{i_{1}}^{(k_{1})}$ in the weighted graph $G_{i_{1}}(v)$. If
$i_{1}<i_{2}$, the agent $i_{1}$ would still win if they bid at least
$p_{k_{2}}$; otherwise, the agent $i_{2}$ would win against $i_{1}$ i.e.,

$\displaystyle\phi^{*}(v_{i_{1}}^{(k)},v_{-{i_{1}}})=\begin{cases}X_{i_{1}}&\text{if
}k\leq k_{2},\\\ X_{i_{2}}&\text{otherwise}.\end{cases}$ (50)

The graph $G_{i_{1}}(v)$ is thus constructed so that each edge from $\star$ to
$v_{i_{1}}^{(k)}$ weighs

$\displaystyle
v_{i_{1}}^{(k)}(\phi^{*}(v_{i_{1}}^{(k)},v_{-{i_{1}}}))=\begin{cases}v_{i_{1}}^{(k)}(X_{i_{1}})=p_{k}&\text{if
}k\leq k_{2},\\\ v_{i_{1}}^{(k)}(X_{i_{2}})=0&\text{otherwise},\end{cases}$
(51)

and each edge from $v_{i_{1}}^{(k^{\prime})}$ to $v_{i_{1}}^{(k)}$ weighs

$\displaystyle
v_{i_{1}}^{(k)}(\phi^{*}(v_{i_{1}}^{(k)},v_{-{i_{1}}}))-v_{i_{1}}^{(k)}(\phi^{*}(v_{i_{1}}^{(k^{\prime})},v_{-{i_{1}}}))=\begin{cases}p_{k}&\text{if
}k\leq k_{2}<k^{\prime},\\\ -p_{k}&\text{if }k^{\prime}\leq k_{2}<k,\\\
0&\text{otherwise}.\end{cases}$ (52)

Hence (see Figure 3(a)), $-\tau^{*}_{i_{1}}(v)$ is the distance along the path
$\star\rightarrow v_{i_{1}}^{(k_{2})}\rightarrow v_{i_{1}}^{(k_{1})}$, which
is equal to $p_{k_{2}}$, the second highest among bid prices. Otherwise, if
$i_{1}>i_{2}$, the agent $i_{2}$ would win against $i_{1}$ also if both bid
the same price; the option rule (50) slightly change to

$\displaystyle\phi^{*}(v_{i_{1}}^{(k)},v_{-{i_{1}}})=\begin{cases}X_{i_{1}}&\text{if
}k<k_{2},\\\ X_{i_{2}}&\text{otherwise}.\end{cases}$ (53)

Hence (see Figure 3(b)), $-\tau^{*}_{i_{1}}(v)$ is the distance along the path
$\star\rightarrow v_{i_{1}}^{(k_{2}-1)}\rightarrow v_{i_{1}}^{(k_{1})}$, which
is equal to $p_{k_{2}-1}$, the lowest among strictly higher biddable prices
than $p_{k_{2}}$.222Note $p_{k_{2}-1}$ becomes closer to $p_{k_{2}}$ as the
set of biddable prices gets denser.

It follows after similar observations that $\tau^{*}_{i}(v)=0,\forall
i\in\mathcal{N}\setminus\\{i_{1}\\}$, so only
$-\tau_{i_{1}}(v)\in\\{p_{k_{2}-1},p_{k_{2}}\\}$ contributes to the revenue
$-B(v;\mathcal{M}^{*})$ at the auction. This example implies how the
celebrated second-price auction [38] can be discretized as a special case of
the proposed mechanism, which realizes the maximum revenue among all justified
mechanisms.

(a) $i_{1}<i_{2}$

(b) $i_{1}>i_{2}$

Figure 3: An example of the weighted graph $G_{i_{1}}(v)$ in ex:vickrey to
compute the payment from the winner $i_{1}=1$, where there are $d=5$ types
(biddable prices) and the agent $i_{2}$ makes the second-highest bid of
$p_{3}$ i.e., $k_{2}=3$. While not all edges are shown, each solid arrow
represents an edge with a positive weight, each dashed arrow represents an
edge with a negative weight, and each dotted arrow represents an edge with a
zero weight. Notice that vertices inside a closed dotted line are mutually
connected by zero-weight edges, hence they have an equal shortest distance
from/to any other vertex. The weight of any positive edge coming into
$v_{1}^{(k)}$ is $p_{k}$, and the weight of any negative edge going out of
$v_{1}^{(k)}$ is $-p_{k}$. In the case (LABEL:sub@fig:second-price-ge)
$i_{1}<i_{2}$, one of the shortest paths from $\star$ to $v_{1}^{(1)}$ could
be $\star\to v_{1}^{(3)}\to v_{1}^{(1)}$, along which the distance is $p_{3}$.
In the other case (LABEL:sub@fig:second-price-gg) $i_{1}>i_{2}$, one of the
shortest paths from $\star$ to $v_{1}^{(1)}$ could be $\star\to v_{1}^{(2)}\to
v_{1}^{(1)}$, along which the distance is $p_{2}$.

##  Appendix C LP duality

Let us fix an option rule $\phi$ according to SE (1). Note that DSIC and IR
allow us to adjust the payment $\tau_{i}(v)$ independently for different
$i\in\mathcal{N}$ and then for different $v_{-i}\in\mathcal{V}_{-i}$. We thus
focus on deciding
$(\pi(v_{i})\coloneqq-\tau_{i}(v_{i},v_{-i}))_{v_{i}\in\mathcal{V}_{i}}$ for
arbitrarily fixed $i\in\mathcal{N}$ and $v_{-i}\in\mathcal{V}_{-i}$. Using the
edge weights $c$ of the graph $G_{i}(v)$ in Section 5, we consider the
following (primal) LP for an arbitrary $v_{i}\in\mathcal{V}_{i}$:

$\displaystyle\max_{\pi}\qquad\pi(v_{i}),$ (54) $\displaystyle\text{subject
to}\qquad\pi(t)-\pi(s)$ $\displaystyle\leq c(s,t),$ $\displaystyle\forall
s\in\mathcal{V}_{i}\cup\\{\star\\},\forall t\in\mathcal{V}_{i},$ (55)
$\displaystyle\pi(\star)$ $\displaystyle=0,$ (56)

where (55) with (56) exactly represents a combination of DSIC (4) and IR (5).
On the other hand, the dual LP is

$\displaystyle\min_{f}\qquad\sum_{s\in\mathcal{V}_{i}\cup\\{\star\\},t\in\mathcal{V}_{i}}c(s,t)f(s,t),$
(57) $\displaystyle\text{subject
to}\qquad\sum_{s\in\mathcal{V}_{i}\cup\\{\star\\}}f(s,u)-\sum_{t\in\mathcal{V}_{i}}f(u,t)$
$\displaystyle=\begin{cases}1&\text{if }u=v_{i},\\\
0&\text{otherwise},\end{cases}$ $\displaystyle\forall u\in\mathcal{V}_{i},$
(58) $\displaystyle f(s,t)$ $\displaystyle\geq 0,$ $\displaystyle\forall
s\in\mathcal{V}_{i}\cup\\{\star\\},\forall t\in\mathcal{V}_{i}.$ (59)

It can be seen as the LP relaxation of the shortest path problem in the graph
$G_{i}(v)$, where $f(s,t)$ represents a fraction of the edge $(s,t)$ that the
path passes through. The primal LP is feasible if and only if the graph
$G_{i}(v)$ has no negative cycle, in which case the shortest distances
$\pi^{*}(v_{i}^{\prime})$ from $\star$ to each
$v_{i}^{\prime}\in\mathcal{V}_{i}$ in $G_{i}(v)$ compose an optimal solution
$\pi=\pi^{*}$ for the primal, while the shortest path represents an optimal
solution for the dual (cf. Section 9.2 in [18]). Note that it is essential in
our method that the optimal solution to the primal does not depend on the
choice of $v_{i}\in\mathcal{V}_{i}$, for which
$\pi(v_{i})=-\tau_{i}(v_{i},v_{-i})$ is maximized (54).

##  Appendix D Relation to the affine maximizer auction (AMA)

With regard to the affine maximizer auction (AMA) mentioned in Section 2, this
section provides how the proposed mechanism can be applied in that context, as
well as a brief introduction of basic concepts about AMA. The environment is
now assumed to allow no negative value (9), as is the case in single-side
auctions, and possibly infinite type domains unlike our model. Then we choose
an affine maximizer in the following def:affine_maximizer as the option rule,
which may not necessarily satisfy SE (1), the stronger requirement than (60).

######  Definition 9 (Affine maximizer).

def:affine_maximizer For an environment
$\mathcal{E}=(\mathcal{N},\mathcal{X},\mathcal{V})$, an option rule $\phi$ of
a mechanism is said to be an affine maximizer if and only if

$\displaystyle\phi(v)$
$\displaystyle\in\arg\max_{X\in\mathcal{X}}\left\\{\sum_{i\in\mathcal{N}}w_{i}v_{i}(X)+\lambda(X)\right\\},$
$\displaystyle\forall v\in\mathcal{V}$ (60)

holds for some agent weights
$w=(w_{i})_{i\in\mathcal{N}}\in\mathbb{R}_{>0}^{\mathcal{N}}$ and some option
weight $\lambda:\mathcal{X}\to\mathbb{R}$.

thm:Roberts states a notable fact that motivates mechanisms to adopt affine
maximizers (60). Moreover, under certain assumptions, even combinatorial
auctions or other restricted environments allow only “almost affine
maximizers” to guarantee DSIC [20].

######  Theorem 6 (Roberts [32]).

thm:Roberts If all type domains are unrestricted i.e.,
$\mathcal{V}_{i}=\mathbb{R}^{\mathcal{X}}$, and if there are at least three
options i.e., $|\mathcal{X}|\geq 3$, then the option rule of any mechanism
$(\phi,\tau)$ that satisfies DSIC (4) must be an affine maximizer for some
weights $(w,\lambda)$.

Such an affine maximizer $\phi$ as the option rule often comes with a payment
rule $\tau$ in the following generic form (61), which actually enjoys DSIC
(4). We thus obtain a weighted extension of the VCG mechanism (def:VCG).

######  Definition 10 (Weighted VCG mechanism).

def:weighted_VCG A mechanism $\mathcal{M}=(\phi,\tau)$ is called the weighted
Vickrey-Clarke-Groves (VCG) mechanism if and only if the option rule $\phi$ is
an affine maximizer for some weights $(w,\lambda)$ and $\mathcal{M}$ satisfies

$\displaystyle\tau_{i}(v)$
$\displaystyle=\frac{1}{w_{i}}\left(\sum_{j\in\mathcal{N}\setminus\\{i\\}}w_{j}v_{j}(\phi(v))+\lambda(\phi(v))\right)-h_{i}(v_{-i}),$
$\displaystyle\forall i\in\mathcal{N}$ (61)

with some functions
$(h_{i}:\mathcal{V}_{-i}\rightarrow\mathbb{R})i\in\mathcal{N}$.

######  Theorem 7 (Proposition 1.31 in [28]).

Every weighted VCG mechanism satisfies DSIC (4).

Furthermore, the following thm:VCG_unique implies that this VCG family is the
unique truthful solution in environments with a wide class of continuous
domains.

######  Theorem 8 (Theorem 1.37 in [28]).

thm:VCG_unique If every participant $i$’s type domain $\mathcal{V}_{i}$ is
connected in the $L^{2}$ space, and if both two mechanism $(\phi,\tau)$ and
$(\phi,\tau^{\prime})$ satisfy DSIC (4), then

$\displaystyle\tau^{\prime}_{i}(v)-\tau_{i}(v)$ $\displaystyle=h_{i}(v_{-i}),$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V},$ (62)

with some functions
$(h_{i}:\mathcal{V}_{-i}\rightarrow\mathbb{R})i\in\mathcal{N}$.

The Clarke pivot rule (Definition LABEL:def:Clarke) is similarly extended as
follows, which provides a mechanism called the affine maximizer auction (AMA).
Most studies about maximizing revenue treat the weights $(w,\lambda)$ as
parameters of AMA and optimize them to increase the revenue in analytical or
heuristic approach.

######  Definition 11 (AMA).

def:Clarke The affine maximizer auction (AMA) specifies the payment rule (61)
of a VCG mechanism as

$\displaystyle h_{i}(v_{-i})$
$\displaystyle=\frac{1}{w_{i}}\max_{X\in\mathcal{X}}\left(\sum_{j\in\mathcal{N}\setminus\\{i\\}}w_{j}v_{j}(X)+\lambda(X)\right),$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V}.$ (63)

######  Lemma 4.

lem:AMA_IR The AMA $\mathcal{M}=(\phi,\tau)$ makes every agent pay to the
broker:

$\displaystyle\tau_{i}(v)$ $\displaystyle\leq 0,$ $\displaystyle\forall
i\in\mathcal{N},\forall v\in\mathcal{V}.$ (64)

It satisfies IR (5) if all possible types are non-negative (9).

###### Proof.

Recall that $w_{i}>0,\forall i\in\mathcal{N}$. The first claim (64) follows by
definition:

$\displaystyle w_{i}\tau_{i}(v)$
$\displaystyle=\sum_{j\in\mathcal{N}\setminus\\{i\\}}w_{j}v_{j}(\phi(v))+\lambda(\phi(v))-\max_{X\in\mathcal{X}}\left(\sum_{j\in\mathcal{N}\setminus\\{i\\}}w_{j}v_{j}(X)+\lambda(X)\right)$
$\displaystyle\leq 0,$ $\displaystyle\forall i\in\mathcal{N},\forall
v\in\mathcal{V}.$ (65)

It is also observed that

$\displaystyle w_{i}u_{i}(v;\mathcal{M})$
$\displaystyle=w_{i}v_{i}(\phi(v))+w_{i}\tau_{i}(v)$
$\displaystyle=\sum_{j\in\mathcal{N}}w_{j}v_{j}(\phi(v))+\lambda(\phi(v))-h_{i}(v_{-i})$
$\displaystyle=\max_{X\in\mathcal{X}}\left(\sum_{j\in\mathcal{N}}w_{j}v_{j}(X)+\lambda(X)\right)-\max_{X\in\mathcal{X}}\left(\sum_{j\in\mathcal{N}\setminus\\{i\\}}w_{j}v_{j}(X)+\lambda(X)\right)$
$\displaystyle\geq\inf_{X\in\mathcal{X}}w_{i}v_{i}(X),$ $\displaystyle\forall
i\in\mathcal{N},v\in\mathcal{V},$ (66)

which yields IR (5) when (9) holds. ∎

We show that the proposed mechanism (Algorithm 1) satisfies DSIC (4) and IR
(5), even when it is built with any affine maximizer (60) as follows. Based on
cor:no-neg-cyc-weighted, an extension of lem:no-neg-cyc,
cor:justified_weighted and cor:maximal_weighted are derived from exactly the
same discussions to obtain thm:justified and thm:maximal, respectively. In
particular, cor:maximal_weighted suggests that the proposed mechanism may
boost the revenue after the optimal weights are found by AMA.

######  Corollary 4.

cor:no-neg-cyc-weighted For any $v\in\mathcal{V}$ and $i\in\mathcal{N}$, the
weighted directed graph $G_{i}(v)$ has no negative directed cycle, if only the
option rule $\phi^{*}$ is an affine maximizer.

###### Proof.

Suppose the proposed mechanism is built with any affine maximizer $\phi^{*}$
for some weights $(w,\lambda)$. Fix an arbitrary pair of $i\in\mathcal{N}$ and
$v\in\mathcal{V}$ for which we are going to show the claim holds. Note that no
cycle contains the auxiliary vertex $\star$, since no edge comes out from it.
Consider an arbitrary sequence $v_{i}^{(1)},\ldots,v_{i}^{(k)}$ in
$\mathcal{V}_{i}$, and let $v_{i}^{(0)}\coloneqq v_{i}^{(k)}$. Let also
$v^{(\ell)}\coloneqq(v_{i}^{(\ell)},v_{-i}),\forall\ell\in\\{0,1,\ldots,k\\}$.
By definition of SelectOption, it follows that

$\displaystyle
w_{i}v_{i}^{(\ell)}(\phi^{*}(v^{(\ell)}))+\sum_{j\in\mathcal{N}\setminus\\{i\\}}w_{j}v_{j}(\phi^{*}(v^{(\ell)}))+\lambda(\phi^{*}(v^{(\ell)}))$
$\displaystyle\geq
w_{i}v_{i}^{(\ell)}(\phi^{*}(v^{(\ell-1)}))+\sum_{j\in\mathcal{N}\setminus\\{i\\}}w_{j}v_{j}(\phi^{*}(v^{(\ell-1)}))+\lambda(\phi^{*}(v^{(\ell-1)})),$
$\displaystyle\forall\ell\in\\{1,\ldots,k\\}.$ (67)

Summing up (67) over all $\ell\in\\{1,\ldots,k\\}$ yields

$\displaystyle
w_{i}\sum_{\ell=1}^{k}(v_{i}^{(\ell)}(\phi^{*}(v^{(\ell)}))-v_{i}^{(\ell)}(\phi^{*}(v^{(\ell-1)})))$
$\displaystyle\geq\sum_{\ell=1}^{k}\left(\sum_{j\in\mathcal{N}\setminus\\{i\\}}w_{j}v_{j}(\phi^{*}(v^{(\ell-1)}))+\lambda(\phi^{*}(v^{(\ell-1)}))\right.$
$\displaystyle\quad\left.-\sum_{j\in\mathcal{N}\setminus\\{i\\}}w_{j}v_{j}(\phi^{*}(v^{(\ell)}))-\lambda(\phi^{*}(v^{(\ell)}))\right)$
$\displaystyle=0,$ (68)

where the last equality follows from $v^{(0)}=v^{(k)}$ by definition. Since
$w_{i}>0$, Eq. (68) implies that the sum of the edge weights along any cycle
in $G_{i}(v)$ is not negative. ∎

######  Theorem 9.

cor:justified_weighted The proposed mechanism built with an affine maximizer
satisfies DSIC (4) and IR (5).

######  Corollary 5.

cor:maximal_weighted The proposed mechanism $\mathcal{M}^{*}$ built with an
affine maximizer $\phi^{*}$ satisfies, against any mechanism
$\mathcal{M}=(\phi^{*},\tau)$ that enjoys DSIC (4) and IR (5),

$\displaystyle\tau^{*}_{i}(v)$ $\displaystyle\leq\tau_{i}(v),$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V},$ (69)
$\displaystyle B(v;\mathcal{M}^{*})$ $\displaystyle\leq B(v;\mathcal{M}),$
$\displaystyle\forall v\in\mathcal{V}.$ (70)

##  Appendix E Additional experiments

In this section, we provide additional results of experiments to confirm that
the observations made with Figure 2 hold with other choices of parameters. We
use the same experimental settings as discussed in Section 6.

$|\mathcal{N}|=8$

$|\mathcal{N}|=16$

$|\mathcal{N}|=32$

(a) $|\mathcal{N}|=8,16,32$

(b) $1\leq|\mathcal{N}|\leq 32$

(c) $1\leq|\mathcal{X}|\leq 256$

(d) $1\leq|\mathcal{V}_{i}|\leq 16$

Figure 4:  Difference in budget required by the proposed mechanism relative to
VCG-budget, shown as a histogram in (LABEL:sub@fig:expn:hist) as well as the
average against the number of agents $|\mathcal{N}|$ in
(LABEL:sub@fig:expn:plot_vs_n), the number of options $|\mathcal{X}|$ in
(LABEL:sub@fig:expn:plot_vs_m), and the size of type domain
$|\mathcal{V}_{i}|$ in (LABEL:sub@fig:expn:plot_vs_d), where $|\mathcal{N}|$
is fixed at 8, 16, or 32, as indicated in each row, except in
(LABEL:sub@fig:expn:plot_vs_n).

In Figure 4, we vary the value of $|\mathcal{N}|$, which is fixed at
$|\mathcal{N}|=16$ in Figure 2. Specifically, we let $|\mathcal{N}|=8$ in the
top row, $|\mathcal{N}|=16$ in the middle row, and $|\mathcal{N}|=32$ in the
bottom row. Hence, the middle row is identical to Figure 2. Also, all of the
three panels in Figure 4(b) are identical to Figure 2(b), since
$|\mathcal{N}|$ is varied identically in these panels. Notice the difference
in the scale of each panel.

Overall, we reconfirm that the proposed mechanism requires strictly lower
budget than VCG-budget for a large fraction of instances in the settings of
Figure 4. Specifically, Figure 4(a) shows that the proposed mechanism strictly
improves upon VCG-budget in 91.1% of the instances with $|\mathcal{N}|=8$, and
88.3% with $|\mathcal{N}|=16$, and 84.9% with $|\mathcal{N}|=32$. In Figure
4(b)-4(d), we can also reconfirm that the relative advantage of the proposed
mechanism with respect to the average difference in the budget tends to
increase with $|\mathcal{N}|$ (observe the changes in the scale from the top
row to the bottom).

$v_{i}(X)\in[-1,1]$

$v_{i}(X)\in[-10,10]$

$v_{i}(X)\in[-100,100]$

$v_{i}(X)\in[-1000,1000]$

(a) $|\mathcal{N}|=16$

(b) $1\leq|\mathcal{N}|\leq 32$

(c) $1\leq|\mathcal{X}|\leq 256$

(d) $1\leq|\mathcal{V}_{i}|\leq 16$

Figure 5:  Difference in budget required by the proposed mechanism relative to
VCG-budget, shown as a histogram in (LABEL:sub@fig:expv:hist) as well as the
average against the number of agents $|\mathcal{N}|$ in
(LABEL:sub@fig:expv:plot_vs_n), the number of options $|\mathcal{X}|$ in
(LABEL:sub@fig:expv:plot_vs_m), and the size of type domain
$|\mathcal{V}_{i}|$ in (LABEL:sub@fig:expv:plot_vs_d), where
$|\mathcal{N}|=16$ is fixed except in (LABEL:sub@fig:expv:plot_vs_n). Here, we
vary the range of $v_{i}(X)$ as indicated in each row.

In Figure 5, we now vary the support of the uniform distribution on
integers333The integer support is chosen to ensure that all numerical data and
computations are handled at unlimited precision. from which $v_{i}(X)$ is
sampled. Note that, although changes in the _scale_ of the support of
$v_{i}(X)$ would equally change the scale of the budgets required by the
proposed mechanism and VCG-budget, changes in the _range of the integers_
would change the number of unique values that $v_{i}(X)$’s can take, which in
turn can affect the relative performance of the mechanisms (recall the
arguments in the proof of thm:time). Specifically, we let the range of the
integers be $[-1,1]$ in the first row, $[-10,10]$ in the second row,
$[-100,100]$ in the third row, and $[-1000,1000]$ in the bottom row. Hence,
the third row is identical to Figure 2. Again, notice the difference in the
scale of each panel.

Overall, we reconfirm that the proposed mechanism requires strictly lower
budget than VCG-budget for a large fraction of instances for all of the ranges
studied in Figure 5. Taking a closer look, we can observe in Figure 5(a) that
there are relatively infrequent opportunities for the proposed mechanism to
improve upon VCG-budget when there are only a few unique values of $v_{i}(X)$
(top row). Specifically, the proposed mechanism strictly improves upon VCG-
budget in 71.6% of the instances when $v_{i}(X)$ can only take an integer
value in $[-1,1]$, while this fraction increases to 86.0%, 88.3%, and 90.2%
when the range changes to $[-10,10]$, $[-100,100]$, and $[-1000,1000]$,
respectively. We can also make analogous observations in Figure 5(b)-5(d).
While some of the error bars contains 0 in the top row, this is simply due to
the skewed distribution of the differences as shown in Figure 5(a) and does
not imply that the average difference may be positive. thm:maximal guarantees
that the proposed mechanism requires no larger budget than VCG-budget _for
every instance_.

##  Appendix F Redistribution of revenue

First, let us formally define the budget balance conditions mentioned in
Section 2, 3 as follows.

######  Definition 12.

def:BB For an environment $\mathcal{E}=(\mathcal{N},\mathcal{X},\mathcal{V})$,
a mechanism $\mathcal{M}=(\phi,\tau)$ is said to satisfy Weak Budget Balance
(WBB) if and only if

$\displaystyle B(v;\mathcal{M})\leq 0,$ $\displaystyle\forall
v\in\mathcal{V};$ (71)

Strong Budget Balance (SBB) if and only if

$\displaystyle B(v;\mathcal{M})=0,$ $\displaystyle\forall v\in\mathcal{V}.$
(72)

With regard to redistribution of revenue mentioned in Section 2, the following
cor:redist constructs one possible algorithm that can adapt the proposed
mechanism to return part of the surplus (negative budget) back to agents while
any positive budget are still minimized.

######  Lemma 5.

lem:redist For any justified mechanism $\mathcal{M}=(\phi,\tau)$, a mechanism
$\mathcal{M}^{\prime}=(\phi,\tau^{\prime})$ is also justified if

$\displaystyle\tau^{\prime}_{i}(v)=\tau_{i}(v)+h_{i}(v_{-i}),\quad\forall
i\in\mathcal{N},\forall v\in\mathcal{V}$ (73)

holds with some function $h_{i}:\mathcal{V}_{-i}\to\mathbb{R}_{\geq 0}$ for
each $i\in\mathcal{N}$.

###### Proof.

The claim straightforwardly follows from def:justified. ∎

######  Corollary 6.

cor:redist For any justified mechanism $\mathcal{M}=(\phi,\tau)$, there exists
a justified mechanism $\mathcal{M}^{\prime}=(\phi,\tau^{\prime})$ that
satisfies the following:

$\displaystyle\tau^{\prime}_{i}(v)$ $\displaystyle\geq\tau_{i}(v),$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V},$ (74)
$\displaystyle B(v;\mathcal{M}^{\prime})$
$\displaystyle\leq\max\\{0,B(v;\mathcal{M})\\},$ $\displaystyle\forall
v\in\mathcal{V},$ (75)
$\displaystyle\max_{v_{i}\in\mathcal{V}_{i}}B(v_{i},v_{-i};\mathcal{M}^{\prime})$
$\displaystyle\geq 0,$ $\displaystyle\forall v_{-i}\in\mathcal{V}_{-i},\forall
i\in\mathcal{N}.$ (76)

###### Proof.

For convenience, let us have agents
$\mathcal{N}\coloneqq\\{1,\ldots,|\mathcal{N}|\\}$ indexed. Given any
justified mechanism $\mathcal{M}\eqqcolon\mathcal{M}^{(0)}=(\phi,\tau^{(0)})$,
we recursively define the mechanism $\mathcal{M}^{(t)}=(\phi,\tau^{(t)})$ as
follows:

$\displaystyle\tau^{(t)}_{i}(v)=\begin{cases}\tau^{(t-1)}_{i}(v)+\max\left\\{0,\displaystyle\min_{v_{i}^{\prime}\in\mathcal{V}_{i}}-B(v_{i}^{\prime},v_{-i};\mathcal{M}^{(t-1)})\right\\}&\text{if
}i=t,\\\ \tau^{(t-1)}_{i}(v)&\text{otherwise,}\end{cases}$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V},\forall
t\in\mathcal{N}.$ (77)

Then every $\mathcal{M}^{(t)}$ is justified because of lem:redist and
satisfies the following:

$\displaystyle\tau^{(t)}_{i}(v)$ $\displaystyle\geq\tau^{(t-1)}_{i}(v),$
$\displaystyle\forall i\in\mathcal{N},\forall v\in\mathcal{V},\forall
t\in\mathcal{N},$ (78) $\displaystyle B(v;\mathcal{M}^{(t)})$
$\displaystyle\leq\max\\{0,B(v;\mathcal{M}^{(t-1)})\\},$ $\displaystyle\forall
v\in\mathcal{V},\forall t\in\mathcal{N},$ (79)
$\displaystyle\max_{v_{i}\in\mathcal{V}_{i}}B(v_{i},v_{-i};\mathcal{M}^{(t)})$
$\displaystyle\geq 0,$ $\displaystyle\forall v_{-i}\in\mathcal{V}_{-i},\forall
i\in\\{1,\ldots,t\\},\forall t\in\mathcal{N}.$ (80)

Therefore, the mechanism
$\mathcal{M}^{\prime}\coloneqq\mathcal{M}^{(|\mathcal{N}|)}$ finally satisfies
all the desired conditions. ∎

Note that the proposed mechanism (Algorithm 1) coupled with some
redistribution technique, the one in cor:redist or other methods, offers a way
to approximately achieve SBB (72) while satisfying SE (1), DSIC (4), and IR
(5). When WBB (71) is unattainable under those three conditions, the proposed
mechanism yields the minimum budget with no redistribution applied (i.e., SBB
is approximated in the best possible manner). Otherwise, if WBB can be
achieved, the proposed mechanism may result in positive revenue, which is then
discounted by the redistribution to better approximate SBB. It remains future
work to establish an optimal redistribution method for the proposed mechanism
just as studied for the VCG mechanisms.

##  Appendix G Broader impacts

Our approach can have positive societal impacts by minimizing the budget
needed to realize socially efficient mechanisms for a number of environments
including trading networks, double-sided auctions in cloud markets, workforce
management, federated learning, and cloud-sourcing, as we have discussed in
Section 1. This however does not mean that all the agents get equally benefit
from our approach, even though our approach guarantees individual rationality.
When our approach is applied, it is thus recommended to carefully assess
whether such fairness needs to be considered and take necessary actions to
mitigate unfairness if needed.


Recovering physical properties from narrow-band photometry
W. Schoenell1,2, R. Cid Fernandes2, N. Benítez1 and N. Vale Asari3,4
1 Instituto de Astrofísica de Andalucía (CSIC)

2 Departamento de Física - CFM - Universidade Federal de Santa Catarina

3 Institute of Astronomy, University of Cambridge

4 CAPES Foundation, Ministry of Education of Brazil

## Abstract

Our aim in this work is to answer, using simulated narrow-band photometry
data, the following general question: What can we learn about galaxies from
these new generation cosmological surveys? For instance, can we estimate
stellar age and metallicity distributions? Can we separate star-forming
galaxies from AGN? Can we measure emission lines, nebular abundances and
extinction? With what precision?

To accomplish this, we selected a sample of about 300k galaxies with good S/N
from the SDSS and divided them in two groups: 200k objects and a template
library of 100k. We corrected the spectra to $z=0$ and converted them to
filter fluxes. Using a statistical approach, we calculated a Probability
Distribution Function (PDF) for each property of each object and the library.
Since we have the properties of all the data from the starlight-SDSS database,
we could compare them with the results obtained from summaries of the PDF
(mean, median, etc).

Our results shows that we retrieve the weighted average of the log of the
galaxy age with a good error margin ($\sigma\approx 0.1-0.2$ dex), and
similarly for the physical properties such as mass-to-light ratio, mean
stellar metallicity, etc. Furthermore, our main result is that we can derive
emission line intensities and ratios with similar precision. This makes this
method unique in comparison to the other methods on the market to analyze
photometry data and shows that, from the point of view of galaxy studies,
future photometric surveys will be much more useful than anticipated.

##  1 Introduction

This paper is essencially motivated due to the J-PAS project http://j-pas.org,
which in a near future will produce 8000 sq degrees of imaging in 56
filterbands of 135Å up to magnitude $i_{AB}\approx 24$. The survey, besides
producing a very high-quality photometric redshift catalog, will provide
highly informative data important to other astronomical communities as galaxy
evolution.

Here we describe a bayesian method to “boost the spectral resolution” of these
kind of photometric data. The idea, which will be described in more detail on
section 3, is basically that if a high-resolution degrated spectra (or a set
of them) is similar to an observed j-spectra111We define a j-spectrum by the
set of photometric measurements on J-PAS filter system. then its physical
properties (and even emission lines) would be similar.

To test the efficiency of this method, we used the starlight-SDSS [2]
http://starlight.ufsc.br/ database as a sandbox. We downloaded the 926246
galaxies where there are measured physical properties and emission lines.

##  2 From SDSS to JPAS

Given a SDSS observed spectra, one can convert its energy distribution
$O_{\lambda}$ to an arbitrary observed photometric filter $l$ defined by its
transmission curve $T_{l,\lambda}$ using the simple conversion
$J_{l}=\frac{\int O_{\lambda}T_{l,\lambda}d\lambda}{\int
T_{l,\lambda}d\lambda}$ and the error on the filter $l$, $\sigma^{2}(J_{l})$,
with the relation
$\sigma^{2}(J_{l})=\Lambda_{l}\langle\sigma(n_{\lambda})^{2}t_{l,\lambda}^{2}\rangle\Delta\lambda$
where $\Lambda_{l}\equiv N_{\lambda,l}\Delta\lambda$ is the effective filter
size and $n_{\lambda}$ is the spectral error in each point.

The filtersystem curves to JPAS considering an airmass of 1.3 and the expected
CCD plus Telescope efficiencies are shown on figure 1. There will be 56
filters, but due to the spectral coverage of SDSS we removed the first one in
the blue and the four last filters giving us an filtersystem of 51 filters
plotted in solid lines. For comparsion, we plotted right below our
filtersystem the SDSS filterset u, g, r, i and z sensitivities through the
same air mass.

Figure 1: JPAS 56 filtersystem sensitivity curves. The 51 solid lines are the
filters used on this work assuming mirror and CCD characteristics and an
airmass of 1.3. We also plotted in solid fill the SDSS u, g, r, i and z
filters in the same conditions.

The main idea of this work is to obtain high precision properties from low
resolution data by taking a shortcut from what we measure from high resolution
spectra. We consider that if an pair object-template j-spectra are similar,
then their measured properties will be similar as well. On fig 2 we show two
examples of matching two objects with their five best matches in respect to
our template library library222In this paper all the galaxies which belongs to
the comparsion sample we call library template galaxies.. In green we plotted
the SDSS object and in blue its four best matches accordingly to their
$\chi^{2}$ calculated over their j-spectrum (plotted as red dots). On the
right panel we have an example of a star-forming galaxy and on the left an
early-type.

This idea is similar to the adopted by [5] and [6] and others, but with an
important difference: Here we do not compare an observed spectrum with a set
of models but we compare it to a set of another observed spectra. This not
only permits us to measure the standard physical properties such as mean age
and stellar masses that can be measured by ohter methodos, but it also allows
us to measure indirectly emission lines on data which we evidently do not have
enough resolution. This is the most relevant advantage of this method.

Figure 2: Two examples of j-spectrum and its 5 best matches based on
$\chi^{2}$. At the top, in green, the two observed spectra examples: an early-
type on left panel and a star-forming galaxy on the the right. In blue, from
top to bottom, the first five best matches. Their j-spectrum is represented by
the connected red dots. Yellow points are flagged as bad pixels and were not
considered. Stars represent the points were j-spectrum is not available.

##  3 Method

To derive the properties $p$ listed down on table 1, we calculated for 100k
objects and two samples of comparsion their likelihood functions ${\cal
L}_{i,j}=e^{-f_{L}\frac{1}{2}\chi^{2}_{i,j}}$. Where
$\chi^{2}_{i,j}=\sum_{l}\frac{1}{N_{\rm
good}}(O_{l,i}-a_{i,j}B_{l,j})^{2}w_{l,i,j}^{2}$ with a scaling factor
$a_{i,j}=\frac{\sum_{l}O_{l,i}B_{l,j}w_{l,i,j}^{2}}{\sum_{l}B_{l,j}^{2}w_{l,i,j}^{2}}$
which is determined by interacting the calculation of $a$ and $\chi^{2}$ until
a convergence critery of $\Delta a_{i,j}<10^{-5}$ is accomplished. In our
simulations, this takes no more than four interactions. The $f_{L}$ term
adjusts the width of the PDF. It can be adjusted to minimize errors, but we
will not treat it here.

The weighting used to the spectra was defined by
$w^{2}_{l,i,j}=\left(\frac{\langle
O^{2}_{l,i}\rangle}{O^{2}_{l,i}}\right)\left(\frac{1}{\sigma^{2}(O_{l,i})+a^{2}_{i,j}\sigma^{2}(B_{l,i})}\right)$.
This was selected to have an unbiased weight in the amplitude of the spectra.
In other words, we would like to give the same importance to the parts with
high fluxes (e.g. emission lines) than that to that regions that have lower
ones (e.g. continuum).

With the likelihood for each object and base, we calculated as the output of
our method a PDF estimator. In our case, to estimate the output, we used the
likelihood-weighted average $\overline{p_{i}}=\frac{\sum_{j}p_{j}{\cal
L}_{i,j}}{\sum_{j}{\cal L}_{i,j}}=p_{out,i}$

Figure 3: Examples of normalized PDF distributions to age, extinction,
H$\alpha$ and [N ii]/H$\alpha$. The left and right boxes corresponds to the
left and right observed galaxaies shown on fig. 2. In blue dashed line we show
the distribution of our base of templates, in magenta the likelihood
distribution (or the posterior) and the horizontal lines represents in solid
black the 16th and 84th percentiles, in red dashed the average and in solid
green the value measured by starlight directly on the spectrum.

##  4 Sample selection

Our main sample was retrieved from the starlight-SDSS database based on very
wide criteria, trying to get all kinds of objects. Firstly, we separated from
the database the galaxies which were in the SDSS main galaxy sample [7], then
we selected those who do not have any bad pixel in intervals of 31Å centered
on the emission lines H$\alpha$, H$\beta$, [N ii]$\lambda$6584, [O
ii]$\lambda$3727 and [O iii]$\lambda$5007 to assure that when we do not
measure an emission line it is because it is too weak to measure and not
because of any observational error. A last selection in redshift ($0.01\leq
z\leq 0.11$) was applied in order to have spectral coverage on the wavelength
interval where JPAS will observe. Those criteria reduced the total number of
galaxies on our sample from 926246 to 299253 galaxies. All these galaxies were
corrected to the rest-frame. As a quick-look test, we will not treat the
redshift as a variable here and all results will be shown to $z=0$.

We then converted all the observed spectra to J-spectra. In case of problems
on the SDSS spectra (e.g. bad pixels), we changed the observed flux to the
best fit from the starlight in the cases where the filters have less bad
pixels than 50% of the filter width. Otherwise, the filter is flagged to be
neglected.

Then, we divided the sample in two sub-samples: one with the galaxies with
$S/N>20$ (113821 galaxies) which we call mother library and other one with
galaxies with $S/N<20$ (185432 galaxies) which we call object sample. All
comparsions made in this paper will be in respect of a set of objects and
their PDFs calculated over a given library which is a set of galaxies from the
mother library. From the mother library, we selected two samples of galaxies
based on two independent diagrams.

The first one, which we call CMD, is based on the physical analog to the
color-magnitude diagram to galaxies, the $\log\ M_{\star}$ – $\langle\log\
t\rangle$ diagram. We chopped this diagram in boxes of 0.1 dex, and on each
box we got 10% of the objects distributed along the $A_{V}$ axis. This gives
us 11952 galaxies on this library.

The second library, which we call WHAN, is based on the WHAN diagnostic
diagram introduced by [3] and divide the galaxies basically between star-
forming, active nuclei and passive or retired galaxies. We did the same cut on
this diagram as we did on CMD library, but here we changed the $A_{V}$ to the
emission line ratio $\log[\rm{N}\,\textsc{ii}]/{\rm H}alpha$. This gives us
27537 galaxies on this library.

##  5 Results

To estimate our method’s precision, we compared the properties derived by our
method (output) on the low-resolution j-spectra with the values derived using
starlight on the high-resolution SDSS spectra (input). So, to do this
comparsion, we evaluate, for each property $p$ and object $i$, the $\Delta
p_{i}=p_{i,\rm output}-p_{i,\rm input}$.

This experiment shows the potential of the proposed method and accomplish with
our initial objective which is to test the precision of galaxy properties with
it. From table 1, we can resume the precision of our method: It can measure
physical properties like age and extinction with typical precision of $0.2$
dex (or mag, in the case of $A_{V}$) and emission lines with $0.3$ dex and our
library selection does not affected the final result, probably because we have
a number of templates which are in both libraries and/or beacause we have
oversampled libraries with $N_{\rm galaxies}$ of about 10k galaxies.

Once more, our main result is that we can measure emission lines without
having sufficient spectral resolution to do it directly on our data.

Table 1: Results Property | $\overline{\Delta p}$ |  $\sigma(\Delta p)$ (CMD) | $\overline{\Delta p}$ |  $\sigma(\Delta p)$ (WHAN)
---|---|---|---|---
$A_{V}$ | 0.023 | 0.106 | 0.023 | 0.101
$\langle\log t_{\star}\rangle_{L}$ | -0.018 | 0.199 | -0.013 | 0.192
$\langle\log Z_{\star}\rangle_{L}$ | -0.021 | 0.144 | -0.020 | 0.141
$\log M/L_{r}$ | -0.045 | 0.114 | -0.040 | 0.110
$\log W_{[O_{II}]}$ | 0.051 | 0.223 | 0.040 | 0.218
$\log W_{H\beta}$ | 0.024 | 0.145 | 0.030 | 0.143
$\log W_{[O_{III}]}$ | 0.046 | 0.245 | 0.029 | 0.232
$\log W_{H\alpha}$ | 0.010 | 0.160 | 0.022 | 0.157
$\log W_{[\rm{N}II]}$ | -0.028 | 0.159 | -0.010 | 0.156
$\log[N_{II}]/H_{\alpha}$ | -0.045 | 0.141 | -0.044 | 0.146
$\log[O_{III}]/H_{\beta}$ | 0.026 | 0.250 | -0.000 | 0.238
$\log H_{\alpha}/H_{\beta}$ | -0.011 | 0.107 | -0.010 | 0.114
$\log S_{II}/H_{\alpha}$ | -0.006 | 0.172 | -0.016 | 0.174
$\log[O_{II}]/H_{\beta}$ | 0.036 | 0.202 | 0.016 | 0.198
$\log[O_{III}]/[N_{II}]$ | 0.075 | 0.265 | 0.044 | 0.252

## Acknowledgments

We thank financial support from CNPq, FAPESP, Instituto de Astronomía de
Andalucía and the CNPq’s Instituto Nacional de Ciência e Tecnologia -
Astrofísica. NVA has been supported by CAPES (proc. no. 6382-10-0). WS has
been supported by Spanish Ministerio de Economía y Competitividad (grant
AYA2010-22111-C03-01) and Brazilian INCT-A. The SEAGal Team wishes to thank
all researchers involved in the Sloan Digital Sky Survey for their dedication
to a project which has made the present work possible.

## References

  * [1] Benítez, N., 2000, ApJ, 536, 571
  * [2] Cid Fernandes R. et al, 2005, MNRAS 358, 363
  * [3] Cid Fernandes R. et al, 2010, MNRAS, 403, 1036
  * [4] Driver, S. P, 2011, arXiv:1112.6244
  * [5] Gallazzi, A. et al, 2005, MNRAS 362, 41
  * [6] Kauffmann, G. et al, D., 2003, MNRAS, 341, 33
  * [7] York, D. G et al, 2000, AJ, 120, 1579