We study the problem of collaborative machine learning markets where multiple
parties can achieve improved performance on their machine learning tasks by
combining their training data. We discuss desired properties for these machine
learning markets in terms of fair revenue distribution and potential threats,
including data replication. We then instantiate a collaborative market for
cases where parties share a common machine learning task and where parties'
tasks are different. Our marketplace incentivizes parties to submit high
quality training and true validation data. To this end, we introduce a novel
payment division function that is robust-to-replication and customized output
models that perform well only on requested machine learning tasks. In
experiments, we validate the assumptions underlying our theoretical analysis
and show that these are approximately satisfied for commonly used machine
learning models.

more |
pdf
| html
None.

arxivml:
"Collaborative Machine Learning Markets with Data-Replication-Robust Payments",
Olga Ohrimenko, Shruti Tople, Sebas…
https://t.co/xDy2WWIf0c

drahmadbazzi:
RT @DO: Collaborative Machine Learning Markets with Data-Replication-Robust Payments. https://t.co/SuP0AEjy2H

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

The goal of a kidney exchange program (KEP) is to maximize number of
transplants within a pool of incompatible patient-donor pairs by exchanging
donors. A KEP can be modelled as a maximum matching problem in a graph. A KEP
between incompatible patient-donor from pools of several hospitals, regions or
countries has the potential to increase the number of transplants. These
entities aim is to maximize the transplant benefit for their patients, which
can lead to strategic behaviours. Recently, this was formulated as a
non-cooperative two-player game and the game solutions (equilibria) were
characterized when the entities objective function is the number of their
patients receiving a kidney. In this paper, we generalize these results for
$N$-players and discuss the impact in the game solutions when transplant
information quality is introduced. Furthermore, the game theory model is
analyzed through computational experiments on instances generated through the
Canada Kidney Paired Donation Program. These experiments highlighting...

more |
pdf
| html
None.

DO:
Game theoretical analysis of Kidney Exchange Programs. https://t.co/sCvsFsIyiA

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

This paper aims to investigate how a central authority (e.g. a government)
can increase social welfare in a network of markets and firms. In these
networks, modeled using a bipartite graph, firms compete with each other
\textit{\`a la} Cournot. Each firm can supply homogeneous goods in markets
which it has access to. The central authority may take different policies for
its aim. In this paper, we assume that the government has a budget by which it
can supply some goods and inject them into various markets. We discuss how the
central authority can best allocate its budget for the distribution of goods to
maximize social welfare. We show that the solution is highly dependent on the
structure of the network. Then, using the network's structural features, we
present a heuristic algorithm for our target problem. Finally, we compare the
performance of our algorithm with other heuristics with experimentation on real
datasets.

more |
pdf
| html
None.

DO:
Governance of Social Welfare in Networked Markets. https://t.co/KS0ZrWTM2Z

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

Resource allocation games such as the famous Colonel Blotto (CB) and
Hide-and-Seek (HS) games are often used to model a large variety of practical
problems, but only in their one-shot versions. Indeed, due to their extremely
large strategy space, it remains an open question how one can efficiently learn
in these games. In this work, we show that the online CB and HS games can be
cast as path planning problems with side-observations (SOPPP): at each stage, a
learner chooses a path on a directed acyclic graph and suffers the sum of
losses that are adversarially assigned to the corresponding edges; and she then
receives semi-bandit feedback with side-observations (i.e., she observes the
losses on the chosen edges plus some others). We propose a novel algorithm,
EXP3-OE, the first-of-its-kind with guaranteed efficient running time for SOPPP
without requiring any auxiliary oracle. We provide an expected-regret bound of
EXP3-OE in SOPPP matching the order of the best benchmark in the literature.
Moreover, we introduce additional...

more |
pdf
| html
DO:
Path Planning Problems with Side Observations-When Colonels Play Hide-and-Seek. https://t.co/JSjdVxhiaD

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 13626

Unqiue Words: 2776

We consider the dynamics of two-player zero-sum games, with the goal of
understanding when such dynamics lead to equilibrium behavior at a fast rate.
In particular, we study the dynamic known as \emph{fictitious play} (FP) in
which each player simultaneously best-responds to the empirical distribution of
the historical plays of their opponent. Nearly 70 years ago it was shown by
Robinson that FP does converge to the Nash Equilibrium, although the rate she
proved was exponential in the total number of actions of the players. In 1959,
Karlin conjectured that FP converges at the more natural rate of
$O(1/\epsilon^2)$. However, Daskalakis and Pan disproved a version of this
conjecture in 2014, showing that an exponentially-slow rate can occur, although
their result relied on adversarial tie-breaking. In this paper, we show that
Karlin's conjecture is indeed correct in two major instances if you
appropriately handle ties. First, we show that if the game matrix is diagonal
and ties are broken lexicographically, then FP converges at a...

more |
pdf
| html
None.

DO:
Fictitious Play: Convergence, Smoothness, and Optimism. https://t.co/AYlhBYsfe9

timelessdev:
RT @DO: Fictitious Play: Convergence, Smoothness, and Optimism. https://t.co/AYlhBYsfe9

memeticyoga:
RT @DO: Fictitious Play: Convergence, Smoothness, and Optimism. https://t.co/AYlhBYsfe9

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

In two-sided markets, Myerson and Satterthwaite's impossibility theorem
states that one can not maximize the gain-from-trade while also satisfying
truthfulness, individual-rationality and no deficit. Attempts have been made to
circumvent Myerson and Satterthwaite's result by attaining
approximately-maximum gain-from-trade: the double-sided auctions of McAfee
(1992) is truthful and has no deficit, and the one by Segal-Halevi et al.
(2016) additionally has no surplus --- it is strongly-budget-balanced. They
consider two categories of agents --- buyers and sellers, where each trade set
is composed of a single buyer and a single seller.
The practical complexity of applications such as supply chain require one to
look beyond two-sided markets. Common requirements are for: buyers trading with
multiple sellers of different or identical items, buyers trading with sellers
through transporters and mediators, and sellers trading with multiple buyers.
We attempt to address these settings.
We generalize Segal-Halevi et al. (2016)'s...

more |
pdf
| html
None.

DO:
Strongly Budget Balanced Auctions for Multi-Sided Markets. https://t.co/nX2WJrFc5U

Implementation of double-auction and multilateral-auction protocols

Stargazers: 0

Subscribers: 1

Subscribers: 1

Forks: 0

Open Issues: 0

Open Issues: 0

None.

Sample Sizes : None.

Authors: 2

Total Words: 11327

Unqiue Words: 2014

In this paper, we present a machine learning-powered iterative combinatorial
auction (CA). The main goal of integrating machine learning (ML) into the
auction is to improve preference elicitation, which is a major challenge in
large CAs. In contrast to prior work, our auction design uses value queries
instead of prices to drive the auction. The ML algorithm is used to help the
auction decide which value queries to ask in every iteration. While using ML
inside an auction introduces new challenges, we demonstrate how we obtain a
design that is individually rational, has good incentives, and is
computationally practical. We benchmark our new auction against the well-known
combinatorial clock auction (CCA). Our results indicate that, especially in
large domains, our ML-powered auction can achieve higher allocative efficiency
than the CCA, even with only a small number of value queries.

more |
pdf
| html
None.

DO:
Machine Learning-powered Iterative Combinatorial Auctions. https://t.co/PsnmUhbU1z

drahmadbazzi:
RT @DO: Machine Learning-powered Iterative Combinatorial Auctions. https://t.co/PsnmUhbU1z

KaellumEridani:
RT @DO: Machine Learning-powered Iterative Combinatorial Auctions. https://t.co/PsnmUhbU1z

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 18414

Unqiue Words: 3830

In this paper we introduce and study {\em all-pay bidding games}, a class of
two player, zero-sum games on graphs. The game proceeds as follows. We place a
token on some vertex in the graph and assign budgets to the two players. Each
turn, each player submits a sealed legal bid (non-negative and below their
remaining budget), which is deducted from their budget and the highest bidder
moves the token onto an adjacent vertex. The game ends once a sink is reached,
and \PO pays \PT the outcome that is associated with the sink. The players
attempt to maximize their expected outcome. Our games model settings where
effort (of no inherent value) needs to be invested in an ongoing and stateful
manner. On the negative side, we show that even in simple games on DAGs,
optimal strategies may require a distribution over bids with infinite support.
A central quantity in bidding games is the {\em ratio} of the players budgets.
On the positive side, we show a simple FPTAS for DAGs, that, for each budget
ratio, outputs an approximation for the...

more |
pdf
| html
None.

DO:
All-Pay Bidding Games on Graphs. https://t.co/iklbyfiBo0

jus_tinian:
RT @DO: All-Pay Bidding Games on Graphs. https://t.co/iklbyfiBo0

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

In distortion-based analysis of social choice rules over metric spaces, one
assumes that all voters and candidates are jointly embedded in a common metric
space. Voters rank candidates by non-decreasing distance. The mechanism,
receiving only this ordinal (comparison) information, should select a candidate
approximately minimizing the sum of distances from all voters. It is known that
while the Copeland rule and related rules guarantee distortion at most 5, many
other standard voting rules, such as Plurality, Veto, or $k$-approval, have
distortion growing unboundedly in the number $n$ of candidates.
Plurality, Veto, or $k$-approval with small $k$ require less communication
from the voters than all deterministic social choice rules known to achieve
constant distortion. This motivates our study of the tradeoff between the
distortion and the amount of communication in deterministic social choice
rules.
We show that any one-round deterministic voting mechanism in which each voter
communicates only the candidates she ranks in a...

more |
pdf
| html
None.

DO:
Communication, Distortion, and Randomness in Metric Voting. https://t.co/hUOnvjbbDh

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 11891

Unqiue Words: 2619

In this paper we consider a defending problem on a network. In the model, the
defender holds a total defending resource of R, which can be distributed to the
nodes of the network. The defending resource allocated to a node can be shared
by its neighbors. There is a weight associated with every edge that represents
the efficiency defending resources are shared between neighboring nodes. We
consider the setting when each attack can affect not only the target node, but
its neighbors as well. Assuming that nodes in the network have different
treasures to defend and different defending requirements, the defender aims at
allocating the defending resource to the nodes to minimize the loss due to
attack. We give polynomial time exact algorithms for two important special
cases of the network defending problem. For the case when an attack can only
affect the target node, we present an LP-based exact algorithm. For the case
when defending resources cannot be shared, we present a max-flow-based exact
algorithm. We show that the general...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

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 226,496 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible