Top 10 Arxiv Papers Today in Computer Science And Game Theory

#1. Collaborative Machine Learning Markets with Data-Replication-Robust Payments
Olga Ohrimenko, Shruti Tople, Sebastian Tschiatschek
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.
Tweets
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.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

#2. Game theoretical analysis of Kidney Exchange Programs
Margarida Carvalho, Andrea Lodi
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.
Tweets
DO: Game theoretical analysis of Kidney Exchange Programs. https://t.co/sCvsFsIyiA
None.
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

#3. Governance of Social Welfare in Networked Markets
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.
Tweets
DO: Governance of Social Welfare in Networked Markets. https://t.co/KS0ZrWTM2Z
None.
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

#4. Path Planning Problems with Side Observations-When Colonels Play Hide-and-Seek
Dong Quan Vu, Patrick Loiseau, Alonso Silva, Long Tran-Thanh
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
Tweets
DO: Path Planning Problems with Side Observations-When Colonels Play Hide-and-Seek. https://t.co/JSjdVxhiaD
None.
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 13626
Unqiue Words: 2776

#5. Fictitious Play: Convergence, Smoothness, and Optimism
Jacob Abernethy, Kevin A. Lai, Andre Wibisono
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.
Tweets
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.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

#6. Strongly Budget Balanced Auctions for Multi-Sided Markets
Rica Gonen, Erel Segal-Halevi
more | pdf | html
None.
Tweets
DO: Strongly Budget Balanced Auctions for Multi-Sided Markets. https://t.co/nX2WJrFc5U
Github

Implementation of double-auction and multilateral-auction protocols

Repository: auctions
User: erelsgl
Language: Python
Stargazers: 0
Subscribers: 1
Forks: 0
Open Issues: 0
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11327
Unqiue Words: 2014

#7. Machine Learning-powered Iterative Combinatorial Auctions
Gianluca Brero, Benjamin Lubin, Sven Seuken
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.
Tweets
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.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 18414
Unqiue Words: 3830

#8. All-Pay Bidding Games on Graphs
Guy Avni, Rasmus Ibsen-Jensen, Josef Tkadlec
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.
Tweets
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.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

#9. Communication, Distortion, and Randomness in Metric Voting
David Kempe
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.
Tweets
DO: Communication, Distortion, and Randomness in Metric Voting. https://t.co/hUOnvjbbDh
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 11891
Unqiue Words: 2619

#10. Defending with Shared Resources on a Network
Minming Li, Long Tran-Thanh, Xiaowei Wu
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.
Other stats
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.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
Stats
Tracking 226,496 papers.