Top 7 Arxiv Papers Today in Computer Science And Game Theory


2.011 Mikeys
#1. Equilibrium Characterization for Data Acquisition Games
Jinshuo Dong, Hadi Elzayn, Shahin Jabbari, Michael Kearns, Zachary Schutzman
We study a game between two firms in which each provide a service based on machine learning. The firms are presented with the opportunity to purchase a new corpus of data, which will allow them to potentially improve the quality of their products. The firms can decide whether or not they want to buy the data, as well as which learning model to build with that data. We demonstrate a reduction from this potentially complicated action space to a one-shot, two-action game in which each firm only decides whether or not to buy the data. The game admits several regimes which depend on the relative strength of the two firms at the outset and the price at which the data is being offered. We analyze the game's Nash equilibria in all parameter regimes and demonstrate that, in expectation, the outcome of the game is that the initially stronger firm's market position weakens whereas the initially weaker firm's market position becomes stronger. Finally, we consider the perspective of the users of the service and demonstrate that the expected...
more | pdf | html
Figures
Tweets
arxiv_in_review: #IJCAI19 Equilibrium Characterization for Data Acquisition Games. (arXiv:1905.08909v1 [cs\.GT]) https://t.co/kqUqXq5yRy
arxivml: "Equilibrium Characterization for Data Acquisition Games", Jinshuo Dong, Hadi Elzayn, Shahin Jabbari, Michael Kearn… https://t.co/G3MvKmjIqP
arxiv_cs_LG: Equilibrium Characterization for Data Acquisition Games. Jinshuo Dong, Hadi Elzayn, Shahin Jabbari, Michael Kearns, and Zachary Schutzman https://t.co/tTvOPLw05A
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 9756
Unqiue Words: 2160

2.005 Mikeys
#2. Diffusion and Auction on Graphs
Bin Li, Dong Hao, Dengji Zhao, Makoto Yokoo
Auction is the common paradigm for resource allocation which is a fundamental problem in human society. Existing research indicates that the two primary objectives, the seller's revenue and the allocation efficiency, are generally conflicting in auction design. For the first time, we expand the domain of the classic auction to a social graph and formally identify a new class of auction mechanisms on graphs. All mechanisms in this class are incentive-compatible and also promote all buyers to diffuse the auction information to others, whereby both the seller's revenue and the allocation efficiency are significantly improved comparing with the Vickrey auction. It is found that the recently proposed information diffusion mechanism is an extreme case with the lowest revenue in this new class. Our work could potentially inspire a new perspective for the efficient and optimal auction design and could be applied into the prevalent online social and economic networks.
more | pdf | html
Figures
None.
Tweets
arxivml: "Diffusion and Auction on Graphs", Bin Li, Dong Hao, Dengji Zhao, Makoto Yokoo https://t.co/jAUQiUTg4b
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 7000
Unqiue Words: 1588

2.0 Mikeys
#3. Strategyproof and Approximately Maxmin Fair Share Allocation of Chores
Haris Aziz, Bo Li, Xiaowei Wu
We initiate the work on fair and strategyproof allocation of indivisible chores. The fairness concept we consider in this paper is maxmin share (MMS) fairness. We consider three previously studied models of information elicited from the agents: the ordinal model, the cardinal model, and the public ranking model in which the ordinal preferences are publicly known. We present both positive and negative results on the level of MMS approximation that can be guaranteed if we require the algorithm to be strategyproof. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods.
more | pdf | html
Figures
None.
Tweets
DO: Strategyproof and Approximately Maxmin Fair Share Allocation of Chores. https://t.co/Y7diRiLziZ
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 6782
Unqiue Words: 1389

1.997 Mikeys
#4. Efficient Multi-Resource, Multi-Unit VCG Auction
Liran Funaro, Orna Agmon Ben-Yehuda, Assaf Schuster
We consider the optimization problem of a multi-resource, multi-unit VCG auction that produces an optimal, i.e., non-approximated, social welfare. We present an algorithm that solves this optimization problem with pseudo-polynomial complexity and demonstrate its efficiency via our implementation. Our implementation is efficient enough to be deployed in real systems to allocate computing resources in fine time-granularity. Our algorithm has a pseudo-near-linear time complexity on average (over all possible realistic inputs) with respect to the number of clients and the number of possible unit allocations. In the worst case, it is quadratic with respect to the number of possible allocations. Our experiments validate our analysis and show near-linear complexity. This is in contrast to the unbounded, nonpolynomial complexity of known solutions, which do not scale well for a large number of agents. For a single resource and concave valuations, our algorithm reproduces the results of a well-known algorithm. It does so, however,...
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 10817
Unqiue Words: 2799

1.997 Mikeys
#5. Mechanism Design for Locating a Facility under Partial Information
Vijay Menon, Kate Larson
We study the classic mechanism design problem of locating a public facility on a real line. In contrast to previous work, we assume that the agents are unable to fully specify where their preferred location lies, and instead only provide coarse information---namely, that their preferred location lies in some interval. Given such partial preference information, we explore the design of robust deterministic mechanisms, where by robust mechanisms we mean ones that perform well with respect to all the possible unknown true preferred locations of the agents. Towards this end, we consider two well-studied objective functions and look at implementing these under two natural solution concepts for our setting i) very weak dominance and ii) minimax dominance. We show that under the former solution concept, there are no mechanisms that do better than a naive mechanism which always, irrespective of the information provided by the agents, outputs the same location. However, when using the latter, weaker, solution concept, we show that one can...
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

1.992 Mikeys
#6. Approximately Maximizing the Broker's Profit in a Two-sided Market
Jing Chen, Bo Li, Yingkai Li
We study how to maximize the broker's (expected) profit in a two-sided market, where she buys items from a set of sellers and resells them to a set of buyers. Each seller has a single item to sell and holds a private value on her item, and each buyer has a valuation function over the bundles of the sellers' items. We consider the Bayesian setting where the agents' values are independently drawn from prior distributions, and aim at designing dominant-strategy incentive-compatible (DSIC) mechanisms that are approximately optimal. Production-cost markets, where each item has a publicly-known cost to be produced, provide a platform for us to study two-sided markets. Briefly, we show how to covert a mechanism for production-cost markets into a mechanism for the broker, whenever the former satisfies cost-monotonicity. This reduction holds even when buyers have general combinatorial valuation functions. When the buyers' valuations are additive, we generalize an existing mechanism to production-cost markets in an...
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

1.992 Mikeys
#7. Interdependent Strategic Security Risk Management with Bounded Rationality in the Internet of Things
Juntao Chen, Quanyan Zhu
With the increasing connectivity enabled by the Internet of Things (IoT), security becomes a critical concern, and the users should invest to secure their IoT applications. Due to the massive devices in the IoT network, users cannot be aware of the security policies taken by all its connected neighbors. Instead, a user makes security decisions based on the cyber risks he perceives by observing a selected number of nodes. To this end, we propose a model which incorporates the limited attention or bounded rationality nature of players in the IoT. Specifically, each individual builds a sparse cognitive network of nodes to respond to. Based on this simplified cognitive network representation, each user then determines his security management policy by minimizing his own real-world security cost. The bounded rational decision-makings of players and their cognitive network formations are interdependent and thus should be addressed in a holistic manner. We establish a games-in-games framework and propose a Gestalt Nash equilibrium (GNE)...
more | pdf | html
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 12573
Unqiue Words: 2526

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 131,277 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 131,277 papers.