We study a game between two firms in which each provide a service based on
machine learning. The firms are presented with the opportunity to purchase a
new corpus of data, which will allow them to potentially improve the quality of
their products. The firms can decide whether or not they want to buy the data,
as well as which learning model to build with that data. We demonstrate a
reduction from this potentially complicated action space to a one-shot,
two-action game in which each firm only decides whether or not to buy the data.
The game admits several regimes which depend on the relative strength of the
two firms at the outset and the price at which the data is being offered. We
analyze the game's Nash equilibria in all parameter regimes and demonstrate
that, in expectation, the outcome of the game is that the initially stronger
firm's market position weakens whereas the initially weaker firm's market
position becomes stronger. Finally, we consider the perspective of the users of
the service and demonstrate that the expected...

more |
pdf
| html
arxiv_in_review:
#IJCAI19 Equilibrium Characterization for Data Acquisition Games. (arXiv:1905.08909v1 [cs\.GT]) https://t.co/kqUqXq5yRy

arxivml:
"Equilibrium Characterization for Data Acquisition Games",
Jinshuo Dong, Hadi Elzayn, Shahin Jabbari, Michael Kearn…
https://t.co/G3MvKmjIqP

arxiv_cs_LG:
Equilibrium Characterization for Data Acquisition Games. Jinshuo Dong, Hadi Elzayn, Shahin Jabbari, Michael Kearns, and Zachary Schutzman https://t.co/tTvOPLw05A

None.

None.

Sample Sizes : None.

Authors: 5

Total Words: 9756

Unqiue Words: 2160

Auction is the common paradigm for resource allocation which is a fundamental
problem in human society. Existing research indicates that the two primary
objectives, the seller's revenue and the allocation efficiency, are generally
conflicting in auction design. For the first time, we expand the domain of the
classic auction to a social graph and formally identify a new class of auction
mechanisms on graphs. All mechanisms in this class are incentive-compatible and
also promote all buyers to diffuse the auction information to others, whereby
both the seller's revenue and the allocation efficiency are significantly
improved comparing with the Vickrey auction. It is found that the recently
proposed information diffusion mechanism is an extreme case with the lowest
revenue in this new class. Our work could potentially inspire a new perspective
for the efficient and optimal auction design and could be applied into the
prevalent online social and economic networks.

more |
pdf
| html
None.

arxivml:
"Diffusion and Auction on Graphs",
Bin Li, Dong Hao, Dengji Zhao, Makoto Yokoo
https://t.co/jAUQiUTg4b

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 7000

Unqiue Words: 1588

We initiate the work on fair and strategyproof allocation of indivisible
chores. The fairness concept we consider in this paper is maxmin share (MMS)
fairness. We consider three previously studied models of information elicited
from the agents: the ordinal model, the cardinal model, and the public ranking
model in which the ordinal preferences are publicly known. We present both
positive and negative results on the level of MMS approximation that can be
guaranteed if we require the algorithm to be strategyproof. Our results uncover
some interesting contrasts between the approximation ratios achieved for chores
versus goods.

more |
pdf
| html
None.

DO:
Strategyproof and Approximately Maxmin Fair Share Allocation of Chores. https://t.co/Y7diRiLziZ

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 6782

Unqiue Words: 1389

We consider the optimization problem of a multi-resource, multi-unit VCG
auction that produces an optimal, i.e., non-approximated, social welfare. We
present an algorithm that solves this optimization problem with
pseudo-polynomial complexity and demonstrate its efficiency via our
implementation. Our implementation is efficient enough to be deployed in real
systems to allocate computing resources in fine time-granularity. Our algorithm
has a pseudo-near-linear time complexity on average (over all possible
realistic inputs) with respect to the number of clients and the number of
possible unit allocations. In the worst case, it is quadratic with respect to
the number of possible allocations. Our experiments validate our analysis and
show near-linear complexity. This is in contrast to the unbounded,
nonpolynomial complexity of known solutions, which do not scale well for a
large number of agents.
For a single resource and concave valuations, our algorithm reproduces the
results of a well-known algorithm. It does so, however,...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 10817

Unqiue Words: 2799

We study the classic mechanism design problem of locating a public facility
on a real line. In contrast to previous work, we assume that the agents are
unable to fully specify where their preferred location lies, and instead only
provide coarse information---namely, that their preferred location lies in some
interval. Given such partial preference information, we explore the design of
robust deterministic mechanisms, where by robust mechanisms we mean ones that
perform well with respect to all the possible unknown true preferred locations
of the agents. Towards this end, we consider two well-studied objective
functions and look at implementing these under two natural solution concepts
for our setting i) very weak dominance and ii) minimax dominance. We show that
under the former solution concept, there are no mechanisms that do better than
a naive mechanism which always, irrespective of the information provided by the
agents, outputs the same location. However, when using the latter, weaker,
solution concept, we show that one can...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

We study how to maximize the broker's (expected) profit in a two-sided
market, where she buys items from a set of sellers and resells them to a set of
buyers. Each seller has a single item to sell and holds a private value on her
item, and each buyer has a valuation function over the bundles of the sellers'
items. We consider the Bayesian setting where the agents' values are
independently drawn from prior distributions, and aim at designing
dominant-strategy incentive-compatible (DSIC) mechanisms that are approximately
optimal.
Production-cost markets, where each item has a publicly-known cost to be
produced, provide a platform for us to study two-sided markets. Briefly, we
show how to covert a mechanism for production-cost markets into a mechanism for
the broker, whenever the former satisfies cost-monotonicity. This reduction
holds even when buyers have general combinatorial valuation functions. When the
buyers' valuations are additive, we generalize an existing mechanism to
production-cost markets in an...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

With the increasing connectivity enabled by the Internet of Things (IoT),
security becomes a critical concern, and the users should invest to secure
their IoT applications. Due to the massive devices in the IoT network, users
cannot be aware of the security policies taken by all its connected neighbors.
Instead, a user makes security decisions based on the cyber risks he perceives
by observing a selected number of nodes. To this end, we propose a model which
incorporates the limited attention or bounded rationality nature of players in
the IoT. Specifically, each individual builds a sparse cognitive network of
nodes to respond to. Based on this simplified cognitive network representation,
each user then determines his security management policy by minimizing his own
real-world security cost. The bounded rational decision-makings of players and
their cognitive network formations are interdependent and thus should be
addressed in a holistic manner. We establish a games-in-games framework and
propose a Gestalt Nash equilibrium (GNE)...

more |
pdf
| html
None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 12573

Unqiue Words: 2526

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 131,277 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible