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

##### #3. 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: 0
Unqiue Words: 0

##### #4. 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

##### #5. 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
None.
###### 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: 0
Unqiue Words: 0

##### #6. 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

##### #7. Optimal mechanisms for distributed resource-allocation
###### Rahul Chandan, Dario Paccagnan, Jason R. Marden
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.
###### Tweets
rahul_chandan_: Our paper "Optimal mechanisms for distributed resource-allocation" is now available on @arxiv -- https://t.co/ViwztuzuqK
###### Github

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

Repository: resalloc-poa
User: rahul-chandan
Language: Python
Stargazers: 0
Subscribers: 1
Forks: 0
Open Issues: 0
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 14430
Unqiue Words: 2725

##### #8. On the Price of Satisficing in Network User Equilibria
###### Mahdi Takalloo, Changhyun Kwon
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.
###### Tweets
DO: On the Price of Satisficing in Network User Equilibria. https://t.co/KGfAYeWhgJ
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
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: 0
Unqiue Words: 0

##### #10. Bidding in Smart Grid PDAs: Theory, Analysis and Strategy (Extended Version)
###### Susobhan Ghosh, Sujit Gujar, Praveen Paruchuri, Easwar Subramanian, Sanjay P. Bhat
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.
###### Tweets
DO: Bidding in Smart Grid PDAs: Theory, Analysis and Strategy (Extended Version). https://t.co/GZIrXcw0ES
None.
None.
###### Other stats
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.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 225,779 papers.