Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Strategy-Proof Facility Location for Concave Cost Functions   We consider k-Facility Location games, where n strategic agents report their
locations on the real line, and a mechanism maps them to k facilities. Each
agent seeks to minimize his connection cost, given by a nonnegative increasing
function of his distance to the nearest facility. Departing from previous work,
that mostly considers the identity cost function, we are interested in
mechanisms without payments that are (group) strategyproof for any given cost
function, and achieve a good approximation ratio for the social cost and/or the
maximum cost of the agents.
  We present a randomized mechanism, called Equal Cost, which is group
strategyproof and achieves a bounded approximation ratio for all k and n, for
any given concave cost function. The approximation ratio is at most 2 for Max
Cost and at most n for Social Cost. To the best of our knowledge, this is the
first mechanism with a bounded approximation ratio for instances with k > 2
facilities and any number of agents. Our result implies an interesting
separation between deterministic mechanisms, whose approximation ratio for Max
Cost jumps from 2 to unbounded when k increases from 2 to 3, and randomized
mechanisms, whose approximation ratio remains at most 2 for all k. On the
negative side, we exclude the possibility of a mechanism with the properties of
Equal Cost for strictly convex cost functions. We also present a randomized
mechanism, called Pick the Loser, which applies to instances with k facilities
and n = k+1 agents, and for any given concave cost function, is strongly group
strategyproof and achieves an approximation ratio of 2 for Social Cost.

28
The categories of this paper are: alg-geom
16
The categories of this paper are: stat
29
The categories of this paper are: funct-an
12
The categories of this paper are: nucl-th
0
The categories of this paper are: hep-ph
14
The categories of this paper are: math-ph
2
The categories of this paper are: math
18
The categories of this paper are: econ
25
The categories of this paper are: patt-sol
33
The categories of this paper are: plasm-ph
5
The categories of this paper are: gr-qc
36
The categories of this paper are: cmp-lg
30
The categories of this paper are: q-alg
32
The categories of this paper are: atom-ph
31
The categories of this paper are: ao-sci
4
The categories of this paper are: cond-mat