1,721,111 research outputs found
Computationally Feasible Approaches to Automated Mechanism Design
No full textIn many multiagent settings, a decision must be made based on the preferences of multiple agents, and agents may lie about their preferences if this is to their benefit. In mechanism design, the goal is to design procedures (mechanisms) for making the decision that work in spite of such strategic behavior, usually by making untruthful behavior suboptimal. In automated mechanism design, the idea is to computationally search through the space of feasible mechanisms, rather than to design them analytically by hand. Unfortunately, the most straightforward approach to automated mechanism design does not scale to large instances, because it requires searching over a very large space of possible functions. In this thesis, we adopt an approach to automated mechanism design that is computationally feasible. Instead of optimizing over all feasible mechanisms, we carefully choose a parameterized subfamily of mechanisms. Then we optimize over mechanisms within this family. Finally, we analyze whether and to what extent the resulting mechanism is suboptimal outside the subfamily. We apply (computationally feasible) automated mechanism design to three resource allocation mechanism design problems: mechanisms that redistribute revenue, mechanisms that involve no payments at all, and mechanisms that guard against false-name manipulation.</p
Going Beyond Counting First Authors in Author Co-citation Analysis
No full textThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Eliciting and Aggregating Information for Better Decision Making
No full textIn this thesis, we consider two classes of problems where algorithms are increasingly used to make, or assist in making, a wide range of decisions. The first class of problems we consider is the allocation of jointly owned resources among a group of agents, and the second is the elicitation and aggregation of probabilistic forecasts from agents regarding future events. Solutions to these problems must trade off between many competing objectives including economic efficiency, fairness between participants, and strategic concerns.In the first part of the thesis, we consider shared resource allocation, where we relax two common assumptions in the fair divison literature. Firstly, we relax the assumption that goods are private, meaning that they must be allocated to only a single agent, and introduce a more general public decision making model. This allows us to incorporate ideas and techniques from fair division to define novel fairness notions in the public decisions setting. Second, we relax the assumption that decisions are made offline, and instead consider online decisions. In this setting, we are forced to make decisions based on limited information, while seeking to retain fairness and game-theoretic desiderata. In the second part of the thesis, we consider the design of mechanisms for forecasting. We first consider a tradeoff between several desirable properties for wagering mechanisms, showing that the properties of Pareto efficiency, incentive compatibility, budget balance, and individual rationality are incompatible with one another. We propose two compromise solutions by relaxing either Pareto efficiency or incentive compatibility. Next, we consider the design of decentralized prediction markets, which are defined by the lack of any single trusted authority. As a consequence, markets must be closed by popular vote amongst a group of anonymous, untrusted arbiters. We design a mechanism that incentivizes arbiters to truthfully report their information even when they have a (possibly conflicting) stake in the market themselves.</p
Essays on Identification and Promotion of Game-Theoretic Cooperation
No full textThis dissertation looks at how to identify and promote cooperation in a multiagent system, first theoretically through the lens of computational game theory and later empirically through a human subject experiment. Chapter 2 studies the network dynamics leading to a potential unraveling of cooperation and identify the subset of agents that can form an enforceable cooperative agreement with. This is an important problem, because cooperation is harder to sustain when information of defection, and thus the consequent punishment, transfers slowly through the network structures from a larger community. Chapter 3 examines a model that studies cooperation in a broader strategic context where agents may interact in multiple different domains, or games, simultaneously. Even if a game independently does not give an agent sufficient incentive to play the cooperative action, there may be hope for cooperation when multiple games with compensating asymmetries are put together. Exploiting compensating asymmetries, we can find an institutional arrangement that would either ensure maximum incentives for cooperation or require minimum subsidy to establish sufficient incentives for cooperation. Lastly, Chapter 4 studies a two-layered public good game to empirically examine whether community enforcement through existing bilateral relationships can encourage cooperation in a social dilemma situation. Here, it is found that how the situation is presented matters greatly to real life agents, as their understanding of whether they are in a cooperative or a competitive, strategic setting changes the level of overall cooperation.</p
The Revelation Principle for Mechanism Design with Signaling Costs
No full textThe revelation principle is a key tool in mechanism design. It allows the designer to restrict attention to the class of truthful mechanisms, greatly facilitating analysis. This is also borne out in an algorithmic sense, allowing certain computational prob- lems in mechanism design to be solved in polynomial time. Unfortunately, when not every type can misreport every other type (the partial verification model), or—more generally—misreporting can be costly, the revelation principle can fail to hold. This also leads to NP-hardness results.The primary contribution of this work consists of characterizations of conditions under which the revelation principle still holds when reporting can be costly. (These are generalizations of conditions given earlier for the partial verification case) In fact, our results extend to cases where, instead of being able to report types directly, agents may be limited to sending signals that do not directly correspond to types. In this case, we obtain conditions for when the mechanism designer can restrict attention to a given (but arbitrary) mapping from types to signals without loss of generality. We also study associated computational problems.</p
Game-Theoretically Allocating Resources to Catch Evaders and Payments to Stabilize Teams
No full textAllocating resources optimally is a nontrivial task, especially when multipleself-interested agents with conflicting goals are involved. This dissertationuses techniques from game theory to study two classes of such problems:allocating resources to catch agents that attempt to evade them, and allocatingpayments to agents in a team in order to stabilize it. Besides discussing whatallocations are optimal from various game-theoretic perspectives, we also studyhow to efficiently compute them, and if no such algorithms are found, whatcomputational hardness results can be proved.The first class of problems is inspired by real-world applications such as theTOEFL iBT test, course final exams, driver's license tests, and airport securitypatrols. We call them test games and security games. This dissertation firststudies test games separately, and then proposes a framework of Catcher-Evadergames (CE games) that generalizes both test games and security games. We showthat the optimal test strategy can be efficiently computed for scored testgames, but it is hard to compute for many binary test games. Optimal Stackelbergstrategies are hard to compute for CE games, but we give an empiricallyefficient algorithm for computing their Nash equilibria. We also prove that theNash equilibria of a CE game are interchangeable.The second class of problems involves how to split a reward that is collectivelyobtained by a team. For example, how should a startup distribute its shares, andwhat salary should an enterprise pay to its employees. Several stability-basedsolution concepts in cooperative game theory, such as the core, the least core,and the nucleolus, are well suited to this purpose when the goal is to avoidcoalitions of agents breaking off. We show that some of these solution conceptscan be justified as the most stable payments under noise. Moreover, by adjustingthe noise models (to be arguably more realistic), we obtain new solutionconcepts including the partial nucleolus, the multiplicative least core, and themultiplicative nucleolus. We then study the computational complexity of thosesolution concepts under the constraint of superadditivity. Our result is basedon what we call Small-Issues-Large-Team games and it applies to popularrepresentation schemes such as MC-nets.</p
Approximately Optimal Mechanisms With Correlated Buyer Valuations
No full textCremer and McLean 1985 shows that if buyers valuations are suciently correlated, there is a mechanism that allows the seller to extract the full surplus from the buyers. However, in practice, we do not see the Cremer-McLean mechanism employed. In this thesis, I demonstrate that one reason that the Cremer-McLean mechanismis not implemented in practice is because the mechanism requires very precise assumptions about the underlying distributions of the buyers. I demonstrate that a small mis-estimation of the underlying distribution can have large and signicant effects on the outcome of the mechanism. I further prove that the Cremer-McLean mechanism cannot be approximated by a simple second price auction, i.e. there is no approximating factor when using a second price auction with reserve in either outcome or expectation for the Cremer-McLean mechanism. Further, I show that there is no mechanism that approximates the Cremer-McLean mechanism for bidders withregular distributions in a single item auction if the correlation among buyers is not considered. Finally, I introduce a new mechanism that is robust to distribution mis-estimation and show empirically that it outperforms the Cremer-McLean mechanism on average in cases of distribution mis-estimation and I show that the mechanism canbe determined in polynomial time in the number of types of the buyers.</p
Security Games: Solution Concepts and Algorithms
No full textAlgorithms for finding game-theoretic solutions are now used in several real-world security applications. Many of these applications are based on different but related game-theoretical models collectively known as security games. Much of the research in this area has focused on the two-player setting in which the first player (leader, defender) commits to a strategy, after which the second player (follower, attacker) observes that strategy and responds to it. This is commonly known as the Stackelberg, or leader-follower, model. If none of the players can observe the actions of the others then such a setting is called a simultaneous-move game. A common solution concept in simultaneous-move games is the Nash equilibrium (NE). In the present dissertation, we contribute to this line of research in two ways.First, we consider new ways of modeling commitment. We propose the new model in which the leader can commit to a correlated strategy. We show that this model is equivalent to the Stackelberg model in two-player games and is different from the existing models in games with three or more players. We propose an algorithm for computing a solution to this model in polynomial time. We also consider a leader-follower setting in which the players are uncertain about whether the follower can observe. We describe an iterative algorithm for solving such games.Second, we analyze the computational complexity of computing Stackelberg and NE strategies in security games. We describe algorithms to solve some variants of the security game model in polynomial time and prove NP-hardness of solving other variants of the model. We also extend the family of security games by allowing the attacker have multiple resources. We provide an algorithm for computing an NE of such games in polynomial time, and we show that computing a Stackelberg strategy is NP-hard.</p
Unsupervised Metric Learning with Synthetic Examples
No full textDistance Metric Learning (DML) involves learning an embedding that brings similar examples closer while moving away dissimilar ones. Existing DML approaches make use of class labels to generate constraints for metric learning. In this paper, we address the less-studied problem of learning a metric in an unsupervised manner. We do not make use of class labels, but use unlabeled data to generate adversarial, synthetic constraints for learning a metric inducing embedding. Being a measure of uncertainty, we minimize the entropy of a conditional probability to learn the metric. Our stochastic formulation scales well to large datasets, and performs competitive to existing metric learning methods
- …
