Top 10 Arxiv Papers Today in Computer Science And Game Theory


2.014 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

2.006 Mikeys
#2. Strongly Budget Balanced Auctions for Multi-Sided Markets
Rica Gonen, Erel Segal-Halevi
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
Figures
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
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11327
Unqiue Words: 2014

2.005 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

2.005 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

2.003 Mikeys
#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
Figures
None.
Tweets
DO: Path Planning Problems with Side Observations-When Colonels Play Hide-and-Seek. https://t.co/JSjdVxhiaD
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

2.003 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

2.002 Mikeys
#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
Figures
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
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 14430
Unqiue Words: 2725

2.001 Mikeys
#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
Figures
None.
Tweets
DO: On the Price of Satisficing in Network User Equilibria. https://t.co/KGfAYeWhgJ
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

2.001 Mikeys
#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
Figures
None.
Tweets
DO: Communication, Distortion, and Randomness in Metric Voting. https://t.co/hUOnvjbbDh
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

2.001 Mikeys
#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
Figures
None.
Tweets
DO: Bidding in Smart Grid PDAs: Theory, Analysis and Strategy (Extended Version). https://t.co/GZIrXcw0ES
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 0
Unqiue Words: 0

About

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
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 225,779 papers.