Computer Science and Game Theory (cs.GT)

  • PDF
    In this work, we aim to create a data marketplace; a robust real-time matching mechanism to efficiently buy and sell training data for Machine Learning tasks. While the monetization of data and pre-trained models is an essential focus of industry today, there does not exist a market mechanism to price training data and match buyers to vendors while still addressing the associated (computational and other) complexity. The challenge in creating such a market stems from the very nature of data as an asset: it is freely replicable; its value is inherently combinatorial due to correlation with signal in other data; prediction tasks and the value of accuracy vary widely; usefulness of training data is difficult to verify a priori without first applying it to a prediction task. As our main contributions we: (i) propose a mathematical model for a two-sided data market and formally define key challenges; (ii) construct algorithms for such a market to function and rigorously prove how they meet the challenges defined. We highlight two technical contributions: (i) a remarkable link between Myerson's payment function arising in mechanism design and the Lovasz extension arising in submodular optimization; (ii) a novel notion of "fairness" required for cooperative games with freely replicable goods. These might be of independent interest.
  • PDF
    Adaptive bitrate (ABR) streaming enables video users to adapt the playing bitrate to the real-time network conditions to achieve the desirable quality of experience (QoE). In this work, we propose a novel crowdsourced streaming framework for multi-user ABR video streaming over wireless networks. This framework enables the nearby mobile video users to crowdsource their radio links and resources for cooperative video streaming. We focus on analyzing the social welfare performance bound of the proposed crowdsourced streaming system. Directly solving this bound is challenging due to the asynchronous operations of users. To this end, we introduce a virtual time-slotted system with the synchronized operations, and formulate the associated social welfare optimization problem as a linear programming. We show that the optimal social welfare performance of the virtual system provides effective upper-bound and lower-bound for the optimal performance (bound) of the original asynchronous system, hence characterizes the feasible performance region of the proposed crowdsourced streaming system. The performance bounds derived in this work can serve as a benchmark for the future online algorithm design and incentive mechanism design.
  • PDF
    A fundamental challenge in imperfect-information games is that states do not have well-defined values. As a result, depth-limited search algorithms used in single-agent settings and perfect-information games do not apply. This paper introduces a principled way to conduct depth-limited solving in imperfect-information games by allowing the opponent to choose among a number of strategies for the remainder of the game at the depth limit. Each one of these strategies results in a different set of values for leaf nodes. This forces an agent to be robust to the different strategies an opponent may employ. We demonstrate the effectiveness of this approach by building a master-level heads-up no-limit Texas hold'em poker AI that defeats two prior top agents using only a 4-core CPU and 16 GB of memory. Developing such a powerful agent would have previously required a supercomputer.
  • PDF
    We develop a model of social learning from overabundant information: Agents have access to many sources of information, and observation of all sources is not necessary in order to learn the payoff-relevant state. Short-lived agents sequentially choose to acquire a signal realization from the best source for them. All signal realizations are public. Our main results characterize two starkly different possible long-run outcomes, and the conditions under which each obtains: (1) efficient information aggregation, where the community eventually achieves the highest possible speed of learning; (2) "learning traps," where the community gets stuck using a suboptimal set of sources and learns inefficiently slowly. A simple property of the correlation structure separates these two possibilities. In both regimes, we characterize which sources are observed in the long run and how often.
  • PDF
    Our work bridges the literature on incentive-compatible mechanism design and the literature on diffusion algorithms. We introduce the study of finding an incentive-compatible (strategy-proof) mechanism for selecting an influential vertex in a directed graph (e.g. Twitter's network). The goal is to devise a mechanism with a bounded ratio between the maximal influence and the influence of the selected user, and in which no user can improve its probability of being selected by following or unfollowing other users. We introduce the `Two Path' mechanism which is based on the idea of selecting the vertex that is the first intersection of two independent random walks in the network. The Two Path mechanism is incentive compatible on directed acyclic graphs (DAGs), and has a finite approximation ratio on natural subfamilies of DAGs. Simulations indicate that this mechanism is suitable for practical uses.
  • PDF
    This article studies the user behavior in non-atomic congestion games. We consider non-atomic congestion games with continuous and non-decreasing functions and investigate the limit of the price of anarchy when the total user volume approaches infinity. We deepen the knowledge on \em asymptotically well designed games \citeWu2017Selfishness, \em limit games \citeWu2017Selfishness, \em scalability \citeWu2017Selfishness and \em gaugeability \citeColini2017b that were recently used in the limit analyses of the price of anarchy for non-atomic congestion games. We develop a unified framework and derive new techniques that allow a general limit analysis of the price of anarchy. With these new techniques, we are able to prove a global convergence on the price of anarchy for non-atomic congestion games with arbitrary polynomial price functions and arbitrary user volume vector sequences. Moreover, we show that these new techniques are very flexible and robust and apply also to non-atomic congestion games with price functions of other types. In particular, we prove that non-atomic congestion games with regularly varying price functions are also asymptotically well designed, provided that the price functions are slightly restricted. Our results greatly generalize recent results. In particular, our results further support the view with a general proof that selfishness need not be bad for non-atomic congestion games.
  • PDF
    The question of how people vote strategically under uncertainty has attracted much attention in several disciplines. Theoretical decision models have been proposed which vary in their assumptions on the sophistication of the voters and on the information made available to them about others' preferences and their voting behavior. This work focuses on modeling strategic voting behavior under poll information. It proposes a new heuristic for voting behavior that weighs the success of each candidate according to the poll score with the utility of the candidate given the voters' preferences. The model weights can be tuned individually for each voter. We compared this model with other relevant voting models from the literature on data obtained from a recently released large scale study. We show that the new heuristic outperforms all other tested models. The prediction errors of the model can be partly explained due to inconsistent voters that vote for (weakly) dominated candidates.

Recent comments

Māris Ozols Oct 21 2016 21:06 UTC

Very nice! Now we finally know how to fairly cut a cake in a finite number of steps! What is more, the number of steps is expected to go down from the whopping $n^{n^{n^{n^{n^n}}}}$ to just barely $n^{n^n}$. I can't wait to get my slice!

https://www.quantamagazine.org/20161006-new-algorithm-solve

...(continued)
Piotr Migdał Apr 18 2014 18:43 UTC

A podcast summarizing this paper, by Geoff Engelstein: [The Dice Tower # 351 - Dealing with the Mockers (43:55 - 50:36)](http://dicetower.coolstuffinc.com/tdt-351-dealing-with-the-mockers), and [an alternative link on the BoardGameGeek](http://boardgamegeek.com/boardgamepodcastepisode/117163/tdt-351

...(continued)