Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Fair and Truthful Mechanism with Limited Subsidy   The notion of \emph{envy-freeness} is a natural and intuitive fairness
requirement in resource allocation. With indivisible goods, such fair
allocations are unfortunately not guaranteed to exist. Classical works have
avoided this issue by introducing an additional divisible resource, i.e.,
money, to subsidize envious agents. In this paper, we aim to design a truthful
allocation mechanism of indivisible goods to achieve both fairness and
efficiency criteria with a limited amount of subsidy. Following the work of
Halpern and Shah, our central question is as follows: to what extent do we need
to rely on the power of money to accomplish these objectives? For general
valuations, the impossibility theorem of combinatorial auction translates to
our setting: even if an arbitrarily large amount of money is available for use,
no mechanism can achieve truthfulness, envy-freeness, and utilitarian
optimality simultaneously when agents have general monotone submodular
valuations. By contrast, we show that, when agents have matroidal valuations,
there is a truthful allocation mechanism that achieves envy-freeness and
utilitarian optimality by subsidizing each agent with at most $1$, the maximum
marginal contribution of each item for each agent. The design of the mechanism
rests crucially on the underlying matroidal M-convexity of the Lorenz
dominating allocations.

10
The categories of this paper are: q-bio
26
The categories of this paper are: bayes-an
20
The categories of this paper are: acc-phys
15
The categories of this paper are: nucl-ex
37
The categories of this paper are: supr-con
25
The categories of this paper are: patt-sol
13
The categories of this paper are: quant-ph
17
The categories of this paper are: q-fin
4
The categories of this paper are: cond-mat
31
The categories of this paper are: ao-sci
28
The categories of this paper are: alg-geom
21
The categories of this paper are: adap-org
18
The categories of this paper are: econ
9
The categories of this paper are: nlin
6
The categories of this paper are: astro-ph
3
The categories of this paper are: physics