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

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: 0

Unqiue Words: 0

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

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
None.

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: 0

Unqiue Words: 0

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

As the complexity of real-world systems continues to increase, so does the
need for distributed protocols that are capable of guaranteeing a satisfactory
system performance, without the reliance on centralized decision making. In
this respect, game theory provides a valuable framework for the design of
distributed algorithms in the form of equilibrium efficiency bounds. Arguably
one of the most widespread performance metrics, the price-of-anarchy measures
how the efficiency of a system degrades when moving from centralized to
distributed decision making. While the smoothness framework -- introduced in
Roughgarden 2009 -- has emerged as a powerful methodology for bounding the
price-of-anarchy, the resulting bounds are often conservative, bringing into
question the suitability of the smoothness approach for the design of
distributed protocols. In this paper, we introduce the notion of generalized
smoothness in order to overcome these difficulties. First, we show that
generalized smoothness arguments are more widely applicable, and...

more |
pdf
| html
None.

rahul_chandan_:
Our paper "Optimal mechanisms for distributed resource-allocation" is now available on @arxiv -- https://t.co/ViwztuzuqK

MATLAB® and Python packages for characterizing and optimizing the price-of-anarchy in distributed resource allocation games.

Stargazers: 0

Subscribers: 1

Subscribers: 1

Forks: 0

Open Issues: 0

Open Issues: 0

None.

Sample Sizes : None.

Authors: 3

Total Words: 14430

Unqiue Words: 2725

When network users are satisficing decision-makers, the resulting traffic
pattern attains a satisficing user equilibrium, which may deviate from the
(perfectly rational) user equilibrium. In a satisficing user equilibrium
traffic pattern, the total system travel time can be worse than in the case of
the PRUE. We show how bad the worst-case satisficing user equilibrium traffic
pattern can be, compared to the perfectly rational user equilibrium. We call
the ratio between the total system travel times of the two traffic patterns the
price of satisficing, for which we provide an analytical bound. We compare the
analytical bound with numerical bounds for several transportation networks.

more |
pdf
| html
None.

DO:
On the Price of Satisficing in Network User Equilibria. https://t.co/KGfAYeWhgJ

None.

None.

Sample Sizes : None.

Authors: 2

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: 0

Unqiue Words: 0

Periodic Double Auctions (PDAs) are commonly used in the real world for
trading, e.g. in stock markets to determine stock opening prices, and energy
markets to trade energy in order to balance net demand in smart grids,
involving trillions of dollars in the process. A bidder, participating in such
PDAs, has to plan for bids in the current auction as well as for the future
auctions, which highlights the necessity of good bidding strategies. In this
paper, we perform an equilibrium analysis of single unit single-shot double
auctions with a certain clearing price and payment rule, which we refer to as
ACPR, and find it intractable to analyze as number of participating agents
increase. We further derive the best response for a bidder with complete
information in a single-shot double auction with ACPR. Leveraging the theory
developed for single-shot double auction and taking the PowerTAC wholesale
market PDA as our testbed, we proceed by modeling the PDA of PowerTAC as an
MDP. We propose a novel bidding strategy, namely MDPLCPBS. We...

more |
pdf
| html
None.

DO:
Bidding in Smart Grid PDAs: Theory, Analysis and Strategy (Extended Version). https://t.co/GZIrXcw0ES

None.

None.

Sample Sizes : None.

Authors: 5

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 225,779 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible